Рекурсивный поиск всех жизнеспособных путей в графе по длине ребра - PullRequest
Новая
       50

Рекурсивный поиск всех жизнеспособных путей в графе по длине ребра

0 голосов
/ 23 октября 2018

У меня есть школьное задание на создание программы, которая получает график и обнаруживает минимальное остовное дерево с условием, что путь между двумя точками (которые предварительно выбраны при запуске) будет кратчайшим на КОЛИЧЕСТВО КРАЙ междуих.

Сама задача в порядке, но я борюсь за оптимизацию.Когда я нахожу свой путь между A и B (предварительно выбранные точки), я пытаюсь рекурсивно найти все другие возможные варианты по DFS, а затем делаю MST и выбираю наименьшее.Поскольку путь должен иметь наименьшее количество ребер, и я нашел один из этих путей по первой BFS, я знаю, что могу обрезать свой поиск в DFS после X рекурсий, где X - это число ребер между A в B, найденных в BFS.Он работает очень быстро в определенных типах графиков (где число ребер в 3 раза больше числа вершин), но когда ребра, например, в 10 раз больше, они просто работают без остановки.

Я попросил у моего друга подсказкуи он сказал мне, что он использует BFS для рекурсивного поиска других путей, и он в порядке, но в чем разница в производительности?Сначала DFS попытается сбежать и остановится, когда достигнет определенной точки или потеряет доступный прыжок, BFS сначала расширяется, а затем заканчивает все пути на одном и том же шаге глубины, но все равно я делаю то же самое количество прыжков правильно?

Чтоя здесь скучаю?Или я его неправильно понял?Спасибо за любые идеи.

РЕДАКТИРОВАТЬ: я пытался проверить, какие ребра я уже посетил в конкретном прогоне DFS, чтобы избежать перехода в противоположном направлении, обратно к точке, где я был и так далее, но это только генерируетсязадержка на определенной группе графиков, но не помогает заметно с другими.

EDIT2: количество переставленных ребер и вершин (не может быть больше вершин, чем ребер)

1 Ответ

0 голосов
/ 24 октября 2018

Итак, я закончил задание и при поиске других путей / всех путей между двумя точками A / B, DFS и BFS, насколько я понял, получает тот же результат.

Ключом для меня была правильная оптимизация решения.Мое окончательное решение сочетает в себе расширение и углубление и работает так (возможно, это можно сделать быстрее, но я сомневаюсь в этом):

  1. Мы знаем длину (в количестве ребер) между точками A / B(мы запустили BFS один раз, чтобы выяснить путь).
  2. Мы запускаем что-то вроде BFS из конечной точки B, и в каждой вершине мы отмечаем, сколько прыжков мы сделали с конца, и вызываем это снова на всех исходящих ребрах (мы останавливаемся, когда прыжки == lengthOfPath (A, B)).
  3. Затем мы делаем DFS из исходной точки A и объединяем все вершины, которые содержат правильное значение прыжка, в путь путем рекурсии.

Другими словами, мы помечаем все точки их достижимостью из B, а затем из A мы проходим через доступные (с заданным значением, отличным от значения по умолчанию и с правильным значением прыжков из A) и объединяем все возможные пути вместе.

Есть наши пути.(Я оставил это смутное намеренно, потому что задача все еще активна).Если кому-то понадобится лучшее объяснение в будущем, оставьте комментарий, и я уточню.Если кто-то найдет лучшее решение, опубликуйте его как свой ответ, а если правильно, я поставлю галочку как правильный.

...