以下のような街並みがある。全ての道を歩くには出発点と終点をどこにしたらよいか？
但し同じ道を歩いてもよく，歩いた経路が最短になるようにする。
うーん，コンピュータで解くには難しい「問題」が潜んでいる。
ちょっとパズルパーク2004年12月15日の問題に雰囲気が似ている。いわゆる迷路問題なので以下のように交差点に番号を振って，交差点間の移動と見なすか，
以下のように経路に番号を振って経路間の移動と見なすか。
何れも簡単には行かない。
ちょっと頭で考えてみる。ありゃ，それらしきものが見つかってしまった。同じ道を通るのは４回。
マズイなー。こういう問題は是非プログラムで解きたいんだけど。
頭で考えると戦略がはっきりしているので割と解きやすい問題だけど，プログラミングするには難しい。
悔しい！
ということで今回はプログラムは無し。
と思ったが，やはり悔しいのでプログラムすることにした。
迷路問題のテンプレートプログラムをコピーしてきて，データを作成する。データは交差点間の距離とする。
P[1][2] = 1; P[1][3] = 3; P[1][5] = 1; P[2][6] = 1; P[2][7] = 2; P[3][4] = 1; ………
始点と終点を適当に定めて実行すると解が沢山出力される。しかし，これは単に始点から終点までの経路を表示するだけで，全ての道を少なくとも一回通るという制約を付けていない。
全ての道を１回以上通るという制約を加えるには，以下のような変数を用意し，
int L[S+1][S+1]; // 道を通過した回数
ゴールの判定で全ての道が通過されたかどうかを判定する文を追加する。
YesNo ynFind = YES;
for( int i=0; i<= S; i++) for( int j=i; j<= S; j++) if( P[i][j] && !L[i][j] && !L[j][i]) { ynFind = NO; break;}
if( ynFind) {
// 全ての道を通過した
}
探索が爆発しないように，以下のような制約も付けた。この制約に掛からない解が存在するかも知れないが，これでプログラムを作ることにした。
こうすると，findGoal( )は以下のようになる。
void findGoal( int level, int p)
{
visit[level] = p;
if( once[p] > 1) return; // ２回までは同じ地点を通るのを許す
if( p == g && level >= 34) { // level >= 34 は全ての道を通過してなければ条件をクリア出来ない
YesNo ynFind = YES;
for( int i=0; i<= S; i++) for( int j=i; j<= S; j++) if( P[i][j] && !L[i][j] && !L[j][i]) { ynFind = NO; break;}
if( ynFind) {
// 今までの経路より短いことを確認する。
int length = 0;
for( i=0; i< level; i++) {
length += P[visit[i]][visit[i+1]];
}
if( length < minLength) { // 以前より短い経路のみ表示する
dump( level, length);
minLength = length;
}
return;
}
}
once[p]++; // 通過回数
for( int next=1; next<= S; next++) { // pから到達可能な全ての地点を調べる
if( !P[p][next]) {
continue; // 到達出来ない地点は無視する
}
if( level > 0 && visit[level-1] == next) {
continue; // 直前に戻ることはしない(多分こういうルートは無いはず)
}
if( once[next] && P[p][next] > 1 && (L[p][next]+L[next][p]) > 0) {
continue; // 長さ2以上の道は二度通らない
}
L[p][next]++;
findGoal( level+1, next);
L[p][next]--;
}
once[p]--;
}
交差点は全部で18あるので，全ての組合せを調べる。
for( s=1; s<= S; s++) { // 全ての始点,終点の組合せを試す
for( g=s; g<= S; g++) { // 終点→始点は始点→終点で求まっているはず
findGoal( 0, s);
}
}
大体一つの始点，終点の組合せで3分弱。全ての組合せを実行したら約8時間掛かった。
プログラムを実行したら，頭で考えた解が一つだけ出力された。
解速度
約８時間(Celeron 1.2GHz)