入力は無向循環平面グラフで、各頂点には最大で 8 つのエッジがあります。
2 つの頂点 v_0、v_1 間のすべてのパスを最短から最長の順に列挙する方法は何ですか? 計算複雑度とは
上記が不可能な場合、K 以下の長さのすべてのパスを生成する方法は何ですか?
1 に答える
2
最長パスへの最短パスを取得したい -> BFS を試すことができることを示します。
パスにサイクルを含めることはできません -> パスがどの頂点を通過したかを保存する必要があります (BFS を実行する場合)。
複雑さ: パスにサイクルが含まれていないことがわかります。これは、パスがすべてのノードを 1 回しか通過できないことを意味します。したがって、解空間は O(n!) であり、最悪の場合、BFS は解空間内のすべてのパスを訪問する可能性があります。したがって、複雑さは O(n!) です。
あなたはその結果にがっかりするかもしれません。さて、あなたの問題はよく研究されている有名な問題です。この論文を読むことができます：
Finding the K Shortest Loopless Paths in a Network
Jin Y. Yen
または、K 番目の最短経路問題の直感的なビューについては、ウィキペディアのページを参照してください。
于 2013-04-26T09:41:36.113 に答える