回答編集履歴
1
修正
test
CHANGED
|
@@ -1,4 +1,4 @@
|
|
|
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
|
|
|
4
4
|
|
|
@@ -8,7 +8,9 @@
|
|
|
8
8
|
|
|
9
9
|
|
|
10
10
|
|
|
11
|
+
* [フロンティア法 - 組合せ問題の解を列挙
|
|
12
|
+
|
|
11
|
-
|
|
13
|
+
索引化するZDD構築アルゴリズム](http://www-lsm.naist.jp/~jkawahara/frontier/frontier_lec.pdf)
|
|
12
14
|
|
|
13
15
|
* [ZDD によるパスの列挙](https://www-erato.ist.hokudai.ac.jp/html/php/symposium3_docs/zddpath_poster.pdf)
|
|
14
16
|
|
|
@@ -17,3 +19,17 @@
|
|
|
17
19
|
|
|
18
20
|
|
|
19
21
|
これを使ってパスを列挙したあとに、各パスの重みの総和を計算し、一番値が大きいパスが「最長経路問題 (longest path problem)」の答えとなるのではないでしょうか。
|
|
22
|
+
|
|
23
|
+
|
|
24
|
+
|
|
25
|
+
## 追記
|
|
26
|
+
|
|
27
|
+
|
|
28
|
+
|
|
29
|
+
同じ頂点は通らないと仮定する必要があると書いていたのですが、同じ頂点は通っても同じ辺を通らなければ、上記のアルゴリズムは適用できます。
|
|
30
|
+
|
|
31
|
+
間違っていたので回答を修正しました。
|
|
32
|
+
|
|
33
|
+
|
|
34
|
+
|
|
35
|
+
[こちら](http://neonev01.blog.fc2.com/blog-entry-54.html) の Python 実装を試したら、80頂点ぐらいだと1秒程度で終わりましたので、19頂点なら一瞬で終わると思います。
|