質問編集履歴
1
誤字の訂正
title
CHANGED
|
File without changes
|
body
CHANGED
|
@@ -1,13 +1,13 @@
|
|
|
1
1
|
### 前提・実現したいこと
|
|
2
2
|
巡回セールスマン問題においてGREEDY法を用いたプログラミングを作りました。
|
|
3
|
-
実行結果について最短経路が間違っていることが分かりました。
|
|
3
|
+
実行結果についてGREEDY法を用いた結果、最短経路が間違っていることが分かりました。
|
|
4
4
|
|
|
5
5
|
GREEDY法
|
|
6
6
|
①全てのアークを長さ順に並べる
|
|
7
7
|
②空の閉路から始め、アークを短い順に調べ、そのアークが次の条件を満たすならば閉路に付け加える
|
|
8
8
|
条件a.都市の次数が3を越えない
|
|
9
9
|
b.すべての都市を回らないよな閉路を作らない
|
|
10
|
-
この条件の
|
|
10
|
+
この条件の基に以下の最短経路を求めると写真の左の経路になります。
|
|
11
11
|
しかし、完全列挙法で導き出した解は右の経路になりました。
|
|
12
12
|
左の経路距離は258
|
|
13
13
|
左の経路距離は254です。
|