人力検索はてな
モバイル版を表示しています。PC版はこちら
i-mobile

辺に重み付けされたグラフが与えられている。
任意のN点を順番に通過する最短の経路を求めたい。
ただし、各頂点、各辺は一度しか通過できない。

上記のような問題を解く際に有効なアルゴリズムを探しています。
単純に最短経路を求める場合ならダイクストラ法で良いのですが、「ただし、・・・」以下の条件をうまく解決する方法が見つかりません。
ヒントとなるようなアルゴリズムや、類似の問題があれば教えていただけるとありがたいです。

●質問者: kaminami
●カテゴリ:コンピュータ 科学・統計資料
✍キーワード:アルゴリズム グラフ ダイクストラ
○ 状態 :終了
└ 回答数 : 2/2件

▽最新の回答へ

1 ● くない / あしけ
●35ポイント

パッと見で思いついたのが巡回セールスマン問題ですが、N点の順番が指定されていること、逆に通らなくていい頂点があること、などだいぶ違いますね。

ただ、巡回セールスマン問題のいくつかある解法の中には応用可能なアルゴリズムがあると思います。

例えば、厳密解を求めたいのであれば、分枝限定法 というのがあります。

分枝限定法の説明は省略しますが、ここでは

まず「各辺、各頂点が一度しか通過できない」(これを点素かつ辺素といいます)という条件を無視して最適解を求め、その結果例えばパスA-B-CとD-B-Eが頂点Bを共有するようであれば、「B-Cを使わない」「B-Cを使いかつB-Eは使わない」という二つの問題に分割する

という方法で「分枝」を行う方法があります。

近似解を求めるのであれば、蟻コロニー最適化 や 焼きなまし法 などの方法はこの問題に応用できます。

◎質問者からの返答

ありがとうございます。

有限時間で厳密解というのはちょっと難しそうですね。


2 ● cappin
●35ポイント

Nノードをめぐる順番が所与であって、ノード間のアークが複数あるような問題ということであれば、それぞれの最小距離(重み)のアークをたどるルートが最短のルートでしょうが、そういう意味ではないでしょうね。

で、Nノードを1回ずつめぐるが順番は自由、ということであれば、巡回セールスマン問題になると思います。

◎質問者からの返答

「順番が所与」「重みの合計が最少のルート」のほうでお願いします。

関連質問


●質問をもっと探す●



0.人力検索はてなトップ
8.このページを友達に紹介
9.このページの先頭へ
対応機種一覧
お問い合わせ
ヘルプ/お知らせ
ログイン
無料ユーザー登録
はてなトップ