質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

新規登録して質問してみよう
ただいま回答率
85.35%
アルゴリズム

アルゴリズムとは、定められた目的を達成するために、プログラムの理論的な動作を定義するものです。

Q&A

解決済

1回答

1213閲覧

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

Jhon_McClane

総合スコア48

アルゴリズム

アルゴリズムとは、定められた目的を達成するために、プログラムの理論的な動作を定義するものです。

0グッド

1クリップ

投稿2020/07/23 14:07

編集2020/07/23 14:09

前提・実現したいこと

巡回セールスマン問題において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

気になる質問をクリップする

クリップした質問は、後からいつでもMYページで確認できます。

またクリップした質問に回答があった際、通知やメールを受け取ることができます。

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

guest

回答1

0

ベストアンサー

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

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

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

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

投稿2020/07/23 14:29

maai

総合スコア463

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

Jhon_McClane

2020/07/23 14:35

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

あなたの回答

tips

太字

斜体

打ち消し線

見出し

引用テキストの挿入

コードの挿入

リンクの挿入

リストの挿入

番号リストの挿入

表の挿入

水平線の挿入

プレビュー

15分調べてもわからないことは
teratailで質問しよう!

ただいまの回答率
85.35%

質問をまとめることで
思考を整理して素早く解決

テンプレート機能で
簡単に質問をまとめる

質問する

関連した質問