プログラムの実行結果は以下の通り。
1=> 1 : 183.053 秒 1=> 2 : 184.735 秒 1=> 3 : 189.132 秒 1=> 4 : 183.244 秒 1=> 5 : 183.564 秒 1=> 6 : 187.63 秒 1=> 7 : 191.795 秒 1=> 8 : 189.593 秒 1=> 9 : 185.737 秒 1=>10 : 183.504 秒 1=>11 : 182.853 秒 1=>12 : 183.574 秒 1=>13 : 183.634 秒 1=>14 : 182.953 秒 1=>15 : 182.803 秒 1=>16 : 183.614 秒 1=>17 : 183.824 秒 1=>18 : 184.005 秒 2=> 2 : 183.614 秒 2=> 3 : 183.604 秒 2=> 4 : 185.026 秒 2=> 5 : 183.414 秒 2=> 6 : 184.545 秒 2=> 7 : 184.425 秒 2=> 8 : 184.285 秒 2=> 9 : 184.105 秒 2=>10 : 184.585 秒 2=>11 : 183.774 秒 2=>12 : 184.275 秒 2=>13 : 184.346 秒 2=>14 : 183.994 秒 2=>15 : 183.654 秒 2=>16 : 187.49 秒 2=>17 : 185.627 秒 2=>18 : 192.997 秒 3=> 3 : 191.345 秒 3=> 4 : 185.327 秒 3=> 5 : 184.345 秒 3=> 6 : 181.671 秒 3=> 7 : 180.69 秒 3=> 8 : 181.361 秒 3=> 9 : 180.67 秒 3=>10 : 187.419 秒 3=>11 : 181.962 秒 3=>12 : 180.87 秒 3=>13 : 180.66 秒 3=>14 : 180.439 秒 3=>15 : 180.399 秒 3=>16 : 184.906 秒 3=>17 : 192.277 秒 3=>18 : 183.033 秒 4=> 4 : 174.22 秒 4=> 5 : 174.451 秒 4=> 6 : 174.321 秒 4=> 7 : 174.07 秒 4=> 8 : 180.31 秒 4=> 9 : 178.747 秒 4=>10 : 179.598 秒 4=>11 : 178.807 秒 4=>12 : 180.68 秒 4=>13 : 180.019 秒 4=>14 : 178.667 秒 4=>15 : 178.616 秒 4=>16 : 179.859 秒 4=>17 : 183.274 秒 4=>18 : 177.495 秒 5=> 5 : 131.158 秒 5=> 6 : 122.006 秒 5=> 7 : 128.374 秒 5=> 8 : 122.456 秒 5=> 9 : 126.472 秒 5=>10 : 125.11 秒 5=>11 : 123.678 秒 5=>12 : 124.389 秒 5=>13 : 129.346 秒 5=>14 : 127.603 秒 5=>15 : 127.173 秒 5=>16 : 124.389 秒 5=>17 : 132.35 秒 5=>18 : 121.515 秒 6=> 6 : 128.605 秒 6=> 7 : 129.096 秒 6=> 8 : 128.414 秒 6=> 9 : 129.166 秒 6=>10 : 130.658 秒 6=>11 : 131.84 秒 6=>12 : 134.353 秒 6=>13 : 131.008 秒 6=>14 : 134.171 秒 6=>15 : 139.26 秒 6=>16 : 129.116 秒 6=>17 : 129.096 秒 6=>18 : 129.186 秒 7=> 7 : 188.16 秒 7=> 8 : 197.294 秒 7=> 9 : 186.558 秒 7=>10 : 187.179 秒 7=>11 : 186.008 秒 7=>12 : 187.319 秒 7=>13 : 187.48 秒 7=>14 : 186.758 秒 7=>15 : 190.644 秒 7=>16 : 191.105 秒 7=>17 : 188.241 秒 7=>18 : 188.04 秒 8=> 8 : 159.319 秒 8=> 9 : 159.9 秒 8=>10 : 160.01 秒 8=>11 : 160.02 秒 8=>12 : 161.172 秒 8=>13 : 168.102 秒 8=>14 : 168.933 秒 8=>15 : 162.784 秒 8=>16 : 163.956 秒 8=>17 : 165.387 秒 8=>18 : 169.504 秒 9=> 9 : 128.795 秒 9=>10 : 125.521 秒 9=>11 : 125 秒 9=>12 : 125.52 秒 9=>13 : 125.39 秒 9=>14 : 125.611 秒 9=>15 : 124.92 秒 9=>16 : 126.271 秒 9=>17 : 125.14 秒 9=>18 : 127.243 秒 10=>10 : 135.625 秒 10=>11 : 135.675 秒 10=>12 : 136.166 秒 10=>13 : 136.636 秒 10=>14 : 135.776 秒 10=>15 : 137.277 秒 10=>16 : 137.227 秒 10=>17 : 138.079 秒 10=>18 : 151.187 秒 11=>11 : 154.432 秒 11=>12 : 130.368 秒 11=>13 : 129.386 秒 11=>14 : 133.161 秒 11=>15 : 141.414 秒 11=>16 : 129.856 秒 11=>17 : 131.97 秒 11=>18 : 129.496 秒 12=>12 : 192.067 秒 12=>13 : 195.451 秒 12=>14 : 194.499 秒 12=>15 : 191.005 秒 12=>16 : 191.425 秒 12=>17 : 191.616 秒 12=>18 : 192.346 秒 13=>13 : 191.576 秒 13=>14 : 192.026 秒 13=>15 : 193.478 秒 13=>16 : 195.451 秒 13=>17 : 195.021 秒 13=>18 : 202.23 秒 14=>14 : 139.02 秒 14=>15 : 136.607 秒 14=>16 : 132.59 秒 14=>17 : 134.153 秒 14=>18 : 133.572 秒 15=>15 : 122.777 秒 15=>16 : 120.463 秒 15=>17 : 118.46 秒 15=>18 : 120.023 秒 16=>16 : 193.829 秒 34, 41 : 16 11 6 2 1 3 4 5 1 2 7 12 11 10 5 6 7 12 16 15 10 9 4 3 8 13 14 9 8 13 17 14 15 18 17 <=これが解 16=>17 : 195.271 秒 16=>18 : 194.529 秒 17=>17 : 195.331 秒 17=>18 : 195.421 秒 18=>18 : 211.254 秒 合計探索時間 : 28062 秒
34の道を通り,経路長は41,始点は16で,終点が17。これを図示すると以下のようになる。
プログラムのソースは以下の通り。
#include "puzutl.h" int s=0; // 出発点 int g=0; // 終点 #define S 18 // 交差点の数 int P[S+1][S+1]; // 交差点間の距離 int L[S+1][S+1]; // 道を通過した回数 int once[1000]; int visit[1000]; int minLength = 9999; void dump( int level, int length) { ps( "%2d, %3d : ", level, length); for( int i=0; i<= level; i++) { ps( "%2d ", visit[i]); } ps( "\n"); } void findGoal( int level, int p) { visit[level] = p; if( once[p] > 1) return; // 2回までは同じ地点を通るのを許す 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]--; } int main( int argc, const char* argv[]) { P[1][2] = 1; // 交差点間の距離 P[1][3] = 3; P[1][5] = 1; P[2][6] = 1; P[2][7] = 2; P[3][4] = 1; P[3][8] = 1; P[4][5] = 1; P[4][9] = 1; P[5][6] = 1; P[5][10] = 1; P[6][7] = 1; P[6][11] = 1; P[7][12] = 1; P[8][9] = 1; P[8][13] = 1; P[9][10] = 1; P[9][14] = 1; P[10][11] = 1; P[10][15] = 1; P[11][12] = 1; P[11][16] = 1; P[12][16] = 4; P[13][14] = 1; P[13][17] = 2; P[14][15] = 1; P[14][17] = 1; P[15][16] = 1; P[15][18] = 1; P[17][18] = 1; for( int i=0; i<= S; i++) for( int j=0; j<= S; j++) if( P[i][j]) P[j][i] = P[i][j]; double totalTime = 0; // 合計処理時間 for( s=1; s<= S; s++) { // 全ての始点,終点の組合せを試す for( g=s; g<= S; g++) { // 終点→始点は始点→終点で求まっているはず ProcTime pt; pt.start(); // 各組合わせの処理時間 findGoal( 0, s); pt.end(); ps( "%2d=>%2d : %g 秒\n", s, g, pt.sec()); totalTime += pt.sec(); } } ps( "合計探索時間 : %g 秒\n", totalTime); return 0; }