またまた,横道に逸れてしまう.FBグループの黒木氏がコメントで紹介しているグラフの距離行列生成アルゴリズムに疑義があり,動作を調べなくてはならないことになってしまった.「フロイド・ライブネッツアルゴリズム」というのを紹介している記事だが,わたしの推測ではコードとしては不完全なものであるように見える.「動的計画法」を用いているというのだが,さっぱり「動的」には見えない.単純にループを3回回しているだけなので,グラフが大きくなると解けないサンプルが出てくるのではないかという気がする.ただし,断定することはできないので,とりあえずプログラムを起こして走らせてみるしかない.
プログラムはすでに出来上がって,動いているので,後は適当なサンプルを食わせて試すだけという段階だ.その前に「距離」ではなく「離心数」を計算するように改造して試してみた.離心数というのはグラフ上の2点をつなぐ最長パスの長さを意味するので,この問題が解ければハミルトンパス問題が解けたことになる.ハミルトンパス問題はハミルトン閉路問題と等価なので,これが解ければ100万ドルが入ってくる.さすがに,こちらの方は最短パスの長さを計算するほど易しくはないが,この線で解ける可能性はゼロではない.手元の問題が片付いたら,調べてみる価値はあるだろう.
▲Test.txtを読み込ませてEccentricGraphを実行すると,処理後に「Input the first data file name」に出てしまう.これはFileComparisonの冒頭にある.case 文でbreakが墜ちていた.
▲動作が少しおかしい.以下のサンプルで
1 2 3 4
1: 1 1 1 1
2: 1 1 1 1
3: 1 1 0 1
4: 0 1 1 1
距離行列に∞が表示されている.
1 2 3 4
1: 0 1 3 3
2: 1 0 2 2
3: 3 3 0 2
4: * 1 3 0
最初の隣接行列からすでに間違っている.
#1 > 2 3
#2 > 1 3 4
#3 > 1 2
#4 > 2
MatはVnというパラメータを持っている.これが決まらないと正しく動作しないというのはまずいと思う.clearmatではMAXNを与えている.引数のnの範囲を初期化するようにした.これで隣接行列は正しくなったが,距離行列はまだおかしい.初期状態で①ー④と③ー④の間には∞が入っている,ここまでは正しい.⇒修正ミスだ.ECCENTRICITYのところをINFINITDISTANCEで書換えていた.⇒動作するようになった.