辺に重み付けされたグラフが与えられている。

任意のN点を順番に通過する最短の経路を求めたい。
ただし、各頂点、各辺は一度しか通過できない。

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

回答の条件
  • 1人2回まで
  • 登録:2010/01/07 14:04:20
  • 終了:2010/01/14 14:05:02

回答(2件)

id:qnighy No.1

くない / あしけ回答回数19ベストアンサー獲得回数12010/01/07 15:00:30

ポイント35pt

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

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

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

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

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

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

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

id:kaminami

ありがとうございます。

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

2010/01/09 12:56:24
id:cappin No.2

cappin回答回数89ベストアンサー獲得回数32010/01/09 01:39:33

ポイント35pt

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

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

id:kaminami

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

2010/01/09 12:50:25

コメントはまだありません

この質問への反応(ブックマークコメント)

トラックバック

  • JGeek Log - Twitter 2010-01-08 19:20:03
    Twitter なんかこのへんに書きなぐったりしてます。アカウント名はMHP2Gのティガレックス Tigarexから。あ、寅年にいいね。 http://twitter.com/itarex 考え中: スペースコロニー内部で回転する半径4
「あの人に答えてほしい」「この質問はあの人が答えられそう」というときに、回答リクエストを送ってみてましょう。

これ以上回答リクエストを送信することはできません。制限について

絞り込み :
はてなココの「ともだち」を表示します。
回答リクエストを送信したユーザーはいません