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

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

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

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

Q&A

解決済

2回答

4868閲覧

n個のノード全て網羅する時の最短経路選択アルゴリズムを教えてください

umasem

総合スコア5

アルゴリズム

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

2グッド

0クリップ

投稿2016/11/16 12:28

###前提・実現したいこと
n個のノードがあります。
各ノードは全て他のn-1個のノードに繋がっています。
各ノード間のコストがわかっています。

ある始点ノードから出発し、同じノードを経由しないで、
全てのノードを網羅するとして最小のコストになる
経路を探すためのアルゴリズムで「試したこと」よりも
軽いものがあれば、教えてください。

例えばノードA、B、Cがあったとして、

A - B のコスト 1
A - C のコスト 2
B - C のコスト 3

始点がAならA->B->C
始点がBならB->A->C

###試したこと
全ての移動の組み合わせを計算して、その各組み合わせの
コストを比較して最小のものを見つけた

e-cube, ynakano👍を押しています

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

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

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

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

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

guest

回答2

0

ベストアンサー

最短経路問題を解くためには、いろいろな解法が知られていますが、
どれもたいてい「試したこと」の全探索よりは、探索時間が短くなると思います。
(ただし、巡回セールスマン問題のようにNP困難の場合は、近似解になります)

その中で分かりやすいものを紹介すると、たとえば「ダイクストラ法」があります。
ただし、ダイクストラを使うときは、移動コストの非負条件に注意してください。


それから、現実のビジネスの問題を解くときは、条件がはるかに複雑になります。
たとえば、高速道路は通行料がかかるとか。そうして条件が複雑になればなるほど、
遺伝的アルゴリズム」のようなヒューリスティックな解法が便利になります。

ヒューリスティックな解法だと、全探索のように最善の解が得られる保証はありません。
が、ノード数が増えていくと、全探索では実時間ですべて探しきれなくなってきます。
そこで、ビジネスでは効率が大事なので、ベストでなくてもベターな解で満足します。

投稿2016/11/16 13:19

編集2016/11/16 13:21
LLman

総合スコア5592

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

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

umasem

2016/11/16 13:47

回答ありがとうございます。 終点ノードが決まってない、経由しなければならないノードがある、経由しなければならないノードの順序は問わない、このような場合にダイクストラ法が使えるのでしょうか? あとこれは書いていなかったのですが、ベストな結果じゃないとだめなのです。 Nが小さいときにベターな解だとベストをユーザ(顧客)にバレてしまうと困る状況ので・・・。 できるだけユーザを不快にしない方法を探していました。 後だしの条件で申し訳ありません。 色々勉強になりました。ありがとうございました。
LLman

2016/11/16 14:26

>終点ノードが決まってない それでしたら、少なくともダイクストラは向かないと思います。 >ベストな結果じゃないとだめ ベストな結果が得られる保証はないので、 そこは何らかの形で妥協が必要だと思います。 たとえば、探索数が小さいときだけ全探索するとか、 必ずしもベストな結果ではないと注意書きをするとか。
umasem

2016/11/16 14:49

なるほど・・・ そういう方法(悪知恵・・・失礼・・・ちゃんと注意書きするんですよね)は思いつきませんでした。 その方針で実装してみようかと思います。 ありがとうございました。
guest

0

見つかりそうにない、が答えです。

https://ja.m.wikipedia.org/wiki/巡回セールスマン問題

もし見つかったら、(論文出してフィールズ賞とってから)こっそり教えます(笑)

まあ半分は冗談として、近似解を探したほうが無難だと思います。

投稿2016/11/16 13:12

majiponi

総合スコア1720

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

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

umasem

2016/11/16 13:37

そんな名前がついていたんですね。 悩む時間を省略できただけでも助かりました。 回答ありがとうございます。
guest

あなたの回答

tips

太字

斜体

打ち消し線

見出し

引用テキストの挿入

コードの挿入

リンクの挿入

リストの挿入

番号リストの挿入

表の挿入

水平線の挿入

プレビュー

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

ただいまの回答率
85.50%

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

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

質問する

関連した質問