Перечислите первые 2^20 путей, которые не включают циклы между двумя вершинами

Question

Входные данные представляют собой ненаправленный циклический планарный граф с каждой вершиной, имеющей не более 8 ребер.

Как можно перечислить по всем путям между двумя вершинами v_0, v_1 ​​в порядке от самой короткой до самой длинной? Что такое вычислительная сложность?

Если вышеприведенное невозможно, то как можно сгенерировать все пути длиной не более K.

Answer 1

Вы хотите получить кратчайший путь к самому длинному пути -> означает, что вы можете попробовать BFS.

Путь не может включать цикл -> вы должны хранить путь, который прошел какие вершины (когда вы делаете BFS).

Сложность: вы видите, что путь не включает цикл, что означает, что путь может проходить каждый узел только один раз. Таким образом, пространство решений равно O(n!), И в худшем случае BFS может посещать все пути в пространстве решений. Таким образом, сложность O(n!).

Вы можете быть разочарованы этим результатом. Хорошо, ваша проблема - известная проблема, которая хорошо изучена. Вы можете прочитать эту статью:

Finding the K Shortest Loopless Paths in a Network
Jin Y. Yen

Или страницы википедии для интуитивно понятного просмотра проблем кратчайшего пути.