Q&A
最長経路問題は一般にNP-hardです。ダイクストラ法では解けないと思います。頂点数、辺数は具体的にどのぐらいか、何か別の制約はないのか（例えば、１辺の最大長が決まっているとか、小数点第３位以下は常に０とか）、どのぐらいの時間で求めたいのかを書いた方が良いと思います。
皆様のアイデアを頂戴したいです。
仕事上の目的で、下のような有向グラフの最長経路を求めたい
と考えております。
実際のグラフはもっと複雑です。
最初ダイクストラ法を用いようと考えましたが
①ダイクストラ法は最小経路を求めるので、そのままでは最長経路
が求められない。
②負の重みがある。
ため断念しました。
上手くこの問題をダイクストラ法で解く方法、あるいはダイクストラ法
に限らず解く方法はないでしょうか。
同一頂点を複数回含むような経路は考えますか？
早速の回答ありがとうございます。制約について、1辺は３～－3の間です。同一頂点を複数回含むような経路は考えておらず、できれば一筆書きで行きたいです。
頂点数はどのくらいですか？
19点です。
それはすごく小さいですね。辺の数はどのくらいですか？
81×2＝162です。
同一頂点を複数回含まないようなパスのみを考えるのなら、dp[ i ][ s ] = 頂点集合sに含まれる頂点のみをたどって頂点 i に到達する最長経路の長さという配列を用意して、動的計画法をすると、始点ｓを固定したときの各頂点への最長経路が1秒ぐらいで求まると思います。
状態数が2^19 * 19個あり、各状態について、遷移が各状態について19個あるので、2^19 * 19 * 19 = 189267968回ぐらいの計算ですね
回答ありがとうございます。しかしながら、当方こういったアルゴリズムなどについてはほとんど初心者でございまして、できれば類似問題や参考になる問題などを例示していただけるとありがたいです。わがままで申し訳ないですがよろしくお願いします。
回答4件
0
まず同じ辺は通らないという制約をもうけた上で、与えた始点と終点を結ぶすべての「パス」を列挙する必要があると思います。
パスを列挙するには、単純に深さ優先で探索すると組み合わせ爆発が起こり現実的でないので、ある程度効率的にパスを列挙できる Simpath アルゴリズムというのがあるようです。
日本語の資料を以下に貼っておきます。
- [フロンティア法 - 組合せ問題の解を列挙
索引化するZDD構築アルゴリズム](http://www-lsm.naist.jp/~jkawahara/frontier/frontier_lec.pdf)
これを使ってパスを列挙したあとに、各パスの重みの総和を計算し、一番値が大きいパスが「最長経路問題 (longest path problem)」の答えとなるのではないでしょうか。
追記
同じ頂点は通らないと仮定する必要があると書いていたのですが、同じ頂点は通っても同じ辺を通らなければ、上記のアルゴリズムは適用できます。
間違っていたので回答を修正しました。
こちら の Python 実装を試したら、80頂点ぐらいだと1秒程度で終わりましたので、19頂点なら一瞬で終わると思います。
投稿2018/09/26 05:50
編集2018/10/02 15:26
総合スコア21956
回答ありがとうございます。参考にさせていただきます。
回答に一部誤りがあったので訂正しました。同じ辺を通らないという制約さえあれば、上記のアルゴリズムは適用できます。同じ頂点は複数回通っても大丈夫です。
http://neonev01.blog.fc2.com/blog-entry-54.html に Python 実装がありました。
0
一般的に解法として、重みを単純に足すだけであれば、負の重みは、オフセットすればいいのです。とりあえず重みに全部１０足す、みたいな乱暴な方法で修正して結果を得たときに、通過点の数ｘ１０を引けばいいのです。
重みの積で評価するとか、通過可能な回数が、各ノード毎に異なる場合には使えません。「積で評価」というのは、面倒そうな気がします。正の数だけだけならlog(重み)の和で評価できますが、負の重みを含むと、負の重みを含む回数が偶数・奇数で２回計算するのかもしれないです。
投稿2018/10/03 02:47
編集2018/10/03 02:58
総合スコア580
0
以前javascriptで似たようなことをやられている方がいらっしゃいました。
http://d.hatena.ne.jp/shspage/20110528/1306550314
反対に最小経路問題ですと、Voronoi Stipplerというソフトがかつてあったようですが。
http://d.hatena.ne.jp/shspage/20110606
今確認してないのでわかりません。プログラム読める方であれば、何らかのヒントが読みとけるのかと。
投稿2018/09/26 06:27
総合スコア466
0
19頂点以下かつ同一頂点を複数回含まないようなパスのみを考えるのなら、
dp[ i ][ s ] = 頂点集合sに含まれる頂点のみをたどって頂点 i に到達する最長経路の長さ
という配列を用意して、動的計画法をすると、始点ｓを固定したときの各頂点への最長経路が1秒ぐらいで求まると思います。
状態数が2^19 * 19個あり、各状態について、遷移が各状態について19個あるので、2^19 * 19 * 19 = 189267968回ぐらいの計算ですね
類似問題としては、巡回セールスマン問題はどうでしょうか？（http://www.prefield.com/algorithm/dp/tsp.html）
投稿2018/09/24 13:06
編集2018/09/24 13:08総合スコア284
あなたの回答
tips
プレビュー
