алгоритм - поиск пути по заданной c вершине - PullRequest
Новая
       41

алгоритм - поиск пути по заданной c вершине

0 голосов
/ 17 января 2020

Я ищу способ найти путь без петель (желательно кратчайший, но не обязательно) от исходной вершины (S) до вершины назначения (D), которая проходит через другую указанную c вершину (X) где-то на графике.

Теперь, прежде чем указать мне на Нахождение кратчайшего пути между проходом через заданную c вершину Я хочу сказать, что это решение игнорирует случай, когда кратчайший путь от S до X уже включает D, что является возможным сценарием, в котором я применяю этот алгоритм. Как бы вы решили эту проблему в этом случае?

Я попытался найти наивную попытку найти такие пути в результатах алгоритма K кратчайших путей Йена. Но я надеюсь, что есть более эффективный и определенный способ сделать это.

Опять же, просто чтобы указать на это, я не обязательно ищу кратчайший путь от S до D через X, но просто любой цикл без петель путь, хотя кратчайший путь будет лучше.

1 Ответ

3 голосов
/ 17 января 2020

Основа c концепция довольно проста; затем вы можете адаптироваться к случаям, когда l oop входит и выходит из X по их кратчайшим оставшимся путям.

  • Удалите D из графика.
  • Find P1, кратчайший путь от S до X.
  • Восстановление D на графике.
  • Удаление всех узлов в P1.
  • Найти P2, кратчайший путь от X до D.
  • return P1 + P2.

Вот суть решения.

ПРИМЕЧАНИЕ : вы можете обнаружить, что удаление P1 приводит к подграфу без оставшегося пути к D. В этом случае вам понадобится динамическое c программное решение, которое ищет идею выше, но с возвратом и другим методом для поиска P1 кандидатов.

Когда вы впервые найдете P1, убедитесь, что используемый вами узел не изолирует X от D на втором этапе поездки. Это даст вам гораздо более быстрый алгоритм поиска.

Достаточно ли начала?

Необходимость адаптации возникает в случае, подобном этому, - рассмотрите график 

src  dst
 S    1, 2
 1    X, D
 2    D
 X    1

Ваши частичные пути 

S -> 1 -> X
S -> 2 -> 3 -> X
X -> 1 -> D
and, incidentally,
S -> 1 -> D

Когда вы выполняете поиск по кратчайшему пути, вы получаете путь S 1 X 1 D, отклоненный из-за l oop. Когда вы реализуете мою первую модификацию - удалите узел 1, когда пытаетесь найти путь X to D, оставшегося пути нет.

Алгоритм нуждается в резервном копировании, отклоняя путь X 1 D найти X 2 3 D. Это код, который не сразу очевиден из описания.

Вот умственное упражнение для вас: возможно ли построить график, в котором каждый кратчайший путь (S to X и X to D) изолирует другой конечный узел от X? В моем примере выше вы можете просто переключить процесс: когда путь S to X изолирует D, а затем начать сначала: сначала найдите X to D, удалите узел 1 и , затем найдите S to X на оставшемся графике. Можете ли вы найти график, где этот переключатель не работает?

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

...