Skip to main content

次の項目のタイムライン: 負の重みを含んだ最長経路の求め方

現在のライセンス: CC BY-SA 4.0

8 件のイベント
日時 書式を切り替える 内容 ユーザー ライセンス コメント
2018年10月2日 15:06 回答 追加済み 涼子津雲 タイムライン スコア: 0
2018年9月25日 4:05 回答 追加済み Yuki Inoue タイムライン スコア: 4
2018年9月25日 1:30 コメント 追加済み OOPer にわかで仕込んだ知識ですがあれこれ。『ダイクストラ法は重み≧0かつ最短経路にしか使えない』(「ダイクストラ法で解く方法」はあり得ない。)『「ベルマン-フォード法」は重みの総和が負になるような閉路を含む場合解を出せない』(正負入れ替えると、重みの総和が正になる閉路を含む例示のグラフには使えない、そのような閉路が存在しないと言う条件が成立していない限り使えない)、『正閉路を避けるため同じ頂点を二度訪問してはいけないと言う制限をつけると、一般化された最長単純道問題となりNP完全、多項式時間で解けるようなアルゴリズムは見つからないと信じられている』(見つけたらフィールズ賞他数々の世界的数学賞を総なめにできるでしょう)。なんらかの現実的制約(「総当たり」と同じ計算量で良いからちょっとでも速く、とか)を付けられないとプログラミング上の課題とは言えないですね
2018年9月24日 15:00 履歴 ツイート済み twitter.com/jaStackOverflow/status/1044240191374983168
2018年9月24日 14:36 コメント 追加済み mjy 当たり前かも知れませんが、全ての重みに -1 を掛けて重みを逆転させた上での最短経路が最長経路だと思いますので、負の重みが使えるアルゴリズムでさえあれば、最短経路を求めるものとして紹介されているものでも、そのまま使えるのではないかと思います。 ちょっと調べると、「ベルマン-フォード法」が負の重みを扱えるようです。 ただ負の重みがあれば、 Hideki さんのコメントにある「ループを永遠に回るというケース」が最短経路になり得ますので、結局その点の考慮が必要ですね。
2018年9月24日 13:57 コメント 追加済み Hideki 途中にループがあるときは、最長経路は無限、つまりループを永遠に回るというケースもあり得ますが、それはどうするのでしょうか。例えば、上の図の場合、1から2に行くとして、1->4->3->5->4->3->5->... というケースが考えられます。一度通った経路は、二度と通らないなどの条件があるのでしょうか。
2018年9月24日 12:05 レビュー 初めての投稿
2018年9月24日 15:33
2018年9月24日 12:04 履歴 質問を投稿 涼子津雲 CC BY-SA 4.0