BFS? - найти все пути от й до т, которые имеют не более определенную длиной

Question

Учитывая неориентированный (подключено) граф, я хочу список всех путей от s к t, которые используют в большинстве k края.

Наивный подход, конечно, просто взять BFS и остановить его после k шагов от s (или ДФСА, где мы отрезаны после k шагов), сообщая любые пути в конечном итоге в t.

Мне было интересно, был ли более сложный способ сделать это?

Answer 1

Я не вижу, как вы можете использовать BFS или DFS здесь. Поскольку вам нужно перечислить все возможные пути от s до t, тогда вы не сможете решить проблему без какого-либо рекурсивного поиска. Более того, обычно количество путей будет экспоненциальным в k, поэтому не надейтесь на какие-либо значительные улучшения асимптотической сложности.

На мой взгляд, только обрезка может немного помочь вам. Вот два способа подрезки стоит упомянуть:

---

Первый является встречаются в-середине подход.

Вместо того, чтобы искать для всех вершин, находящихся на расстоянии <= k от вершины s, найти две группы вершин: на расстоянии <= k/2 от s и на расстоянии <= k/2 от t. Просто запустите два запроса (BFS или рекурсивный), чтобы получить их. Наконец, объедините результаты: для каждой общей вершины v в этих двух наборах возьмите все пары путей от s до v и пути от t до v (с обратной связью) и выведите объединенный путь.

Точный подход, описанный выше, будет перечислять несколько путей несколько раз. Чтобы исправить это, сохраните пути каждой конкретной длины в отдельном списке. Затем объедините пути каждой длины отдельно. Обратите внимание, что если вы хотите получить только простые пути (т. Е. Повторяющиеся вершины), то подход MitM равен , а не.

---

Второй способ заключается в использовании оценки расстояния, подобно тому, как это делает A* search algorithm. Предположим, что вы гарантировали нижние границы на расстоянии от любой вершины v до конечной вершины t. Затем вы можете удалить любой частичный путь от s до v, если он, безусловно, не может быть продолжен до достаточно короткого полного пути от s до t.

Answer 2

На самом деле это не bfs, потому что для того, чтобы получить все пути, вы должны держать соседние вершины, которые вы уже посетили.

со следующим графиком:

• 0-> 1
• 0-> 0
• 1-> 1

Все пути от 0 до 1, которые содержат 2 шага [0,0,1], [0,1,1]

Наивное решение состоит в том, чтобы вести список узлов, активных на каждом шаге (с дубликатами). Чтобы перейти от стека i к i + 1, создайте новый список со всеми соседними вершинами для каждой вершины (не удаляйте дубликаты).