最短経路が変わってしまう。

Question

前提・実現したいこと

巡回セールスマン問題においてGREEDY法を用いたプログラミングを作りました。
実行結果についてGREEDY法を用いた結果、最短経路が間違っていることが分かりました。

GREEDY法
①全てのアークを長さ順に並べる
②空の閉路から始め、アークを短い順に調べ、そのアークが次の条件を満たすならば閉路に付け加える
条件a.都市の次数が3を越えない
b.すべての都市を回らないよな閉路を作らない
この条件の基に以下の最短経路を求めると写真の左の経路になります。
しかし、完全列挙法で導き出した解は右の経路になりました。
左の経路距離は258
左の経路距離は254です。

GREEDY法のルールに基づくと、アークの短い0-2間の長さ45が先に決定しまい、
正しい解と合わなくなってしまうことが分かりました。
本来は0-3間の55を選択することが正解ですが、
この場合
GREEDY法のルールでは0-2よりも0-3を優先して選択することはこのルールだけでは解けないでしょうか

該当のソースコード

5//点の数
0 1 14
0 2 45
0 3 55
0 4 100
1 2 65
1 3 87
1 4 99
2 3 67
2 4 87
3 4 33

Answer 1

巡回セールスマン問題におけるGREEDY法（例えば質問文に挙がっているものなど）はあくまでも近似的な解を求めるものであって、最適解が常に求まるとは限りません。
なので、

正しい解と合わなくなってしまうことが分かりました。

については、「そんなこともある」が回答になります

全列挙以外のアルゴリズムで一般的なグラフにおける巡回セールスマン問題の最適解を求めることは非常に困難と言われています。

Comments

[Jhon_McClane]

maaiさん、解答ありがとうございます。
てっきりGREEDY法も最適解を求めることが出来ると思っていたため、
そうでないことを知りすっきりしました。