回答編集履歴
1
修正
answer
CHANGED
|
@@ -1,10 +1,18 @@
|
|
|
1
|
-
まず同じ
|
|
1
|
+
まず**同じ辺**は通らないという制約をもうけた上で、与えた始点と終点を結ぶすべての「[パス](https://ja.wikipedia.org/wiki/%E9%81%93_(%E3%82%B0%E3%83%A9%E3%83%95%E7%90%86%E8%AB%96))」を列挙する必要があると思います。
|
|
2
2
|
|
|
3
3
|
パスを列挙するには、単純に深さ優先で探索すると[組み合わせ爆発が起こり](http://neonev01.blog.fc2.com/blog-entry-54.html)現実的でないので、ある程度効率的にパスを列挙できる Simpath アルゴリズムというのがあるようです。
|
|
4
4
|
日本語の資料を以下に貼っておきます。
|
|
5
5
|
|
|
6
|
+
* [フロンティア法 - 組合せ問題の解を列挙
|
|
6
|
-
|
|
7
|
+
索引化するZDD構築アルゴリズム](http://www-lsm.naist.jp/~jkawahara/frontier/frontier_lec.pdf)
|
|
7
8
|
* [ZDD によるパスの列挙](https://www-erato.ist.hokudai.ac.jp/html/php/symposium3_docs/zddpath_poster.pdf)
|
|
8
9
|
* [同じところを2度通らない経路の数を数えるアルゴリズム](http://www-erato.ist.hokudai.ac.jp/docs/img/main.pdf)
|
|
9
10
|
|
|
10
|
-
これを使ってパスを列挙したあとに、各パスの重みの総和を計算し、一番値が大きいパスが「最長経路問題 (longest path problem)」の答えとなるのではないでしょうか。
|
|
11
|
+
これを使ってパスを列挙したあとに、各パスの重みの総和を計算し、一番値が大きいパスが「最長経路問題 (longest path problem)」の答えとなるのではないでしょうか。
|
|
12
|
+
|
|
13
|
+
## 追記
|
|
14
|
+
|
|
15
|
+
同じ頂点は通らないと仮定する必要があると書いていたのですが、同じ頂点は通っても同じ辺を通らなければ、上記のアルゴリズムは適用できます。
|
|
16
|
+
間違っていたので回答を修正しました。
|
|
17
|
+
|
|
18
|
+
[こちら](http://neonev01.blog.fc2.com/blog-entry-54.html) の Python 実装を試したら、80頂点ぐらいだと1秒程度で終わりましたので、19頂点なら一瞬で終わると思います。
|