巡回セールスマン問題とは、都市の集合と各都市間の距離が与えられ、全都市をちょうど1回ずつ訪れたのち出発した都市に戻ってくるような経路のうち最も短いものを求める問題です。

正確な値は取得できないのですが、最小全域木を使ってサラリーマン巡回問題の解の近似値を求めることができます。またこの方法は最悪でも最適値の2倍以下の値が得られます。

都市をグラフの頂点とみなし、最小全域木を求めます。そのあと最小全域木の辺を複製して二重にしたグラフを作り、都市を一筆書きで通過します。ただし既に訪れた都市には再度訪れないようにすることで巡回路を求めます。

最小全域木を求める

最初に最小全域木を求めるためのクラスを定義したいのですが、その前提になるNodeクラスとEdgeクラスを定義します。

NodeクラスとEdgeクラスの定義

MinimumSpanningTreeクラスの定義

最小全域木を求めるためのMinimumSpanningTreeクラスを定義します。

Node同士を連結させたときには親をつくります。GetParentメソッドは第一引数のノード番号(0から開始される)の一番上の親を求めます。親を上へ上へとたどっていき、その親が自分自身と同じ場合、それが一番上の親ということになります。

GetSolutionメソッドの引数は都市のX座標とY座標のリストです。重みが小さいものから連結していきます。ただし双方に親がいる場合、その双方の一番上の親が同じ場合は連結すると閉路ができることを意味するので連結させません。グラフが連結であるためには閉路をつくる辺はあってもなくてもグラフが連結であることにかわりはないからです(つまり無くてよい)。

連結するときは親を決めます。双方はまだどことも連結していない場合はどちらかを適当に親にします。片方に親がいる場合はそれが親がいないものの親になります。双方に親がいて一番上の親が異なる場合は、一方の一番上の親が他方の一番上の親の親になります。

このメソッドは連結させるために必要な辺を返します。

最小全域木を構成するために必要な辺のリストが返されたら、最小全域木の辺を複製して二重にしたグラフを作り、既に訪れた都市は飛ばして全都市を一筆書きで通過します。そのためには深さ優先探索すればいいですね。

最小全域木からサラリーマン巡回問題を解く

出力結果

出力は以下のようになります。

本当の最適値は 11.048627177541 なのですが、出力された値はこの2倍以下になっているのがわかります。