тормозящей критерии, как я понимаю, для поиска двунаправленного Дейкстры (с одним стартом и терминальным состоянием) заключается в следующемОстановочных критериев двунаправленной Дейкстры (или равномерного поиск затрат) алгоритм
Начинайте с переменной мю = бесконечность Начать поиск с начала (ов) и состояний терминалов (t) Когда эти два пересекаются (либо узел, который мы сейчас просматриваем при прямом поиске, находится в обратном поиске, либо наоборот) в узле w, затем пересчитываем mu должно быть
mu = distance(s,w) + distance(w,t)
Затем вы проверяете, находятся ли верхние два узла (n внутр те, которые будут рассмотрены) имеют комбинированную расстояние> = мю, и если они делают, прекратить
if distance(s, top_forward_node) + distance(top_reverse_node, t) >= mu, stop
Но если бы я попробовать это на простом треугольнике, он терпит неудачу. Скажем, у меня есть треугольник (a, b, c) с ab = 10, bc = 6 и ac = 7. Начальное состояние = a и состояние терминала = b. Ясно, что кратчайшее расстояние равно ab = 10. Но передний проход начинается с a и смотрит как на b (10), так и на c (7), а обратный проход начинается с b и смотрит на (10) и c (6). Поскольку c - узел с наименьшей стоимостью, передний проход смотрит на c, но поскольку он не находится в обратных узлах, которые уже смотрели, он сохраняет его и перемещается в обратный проход. Обратный проход смотрит на c и видит, что он находится в узлах, на которые смотрит передний проход, и обновляет значение mu от бесконечности до 7 + 6. Следующие узлы, на которые нужно смотреть, - b и a, с стоимостью пути 10 каждый, но тогда, если я просто добавлю два (10 + 10), я получаю значение 20, которое составляет> = 7 + 6, поэтому мой алгоритм неправильно завершает путь acb. Где я иду не так?
forward pass explored nodes = [a(0)]
reverse pass explored nodes = [b(0)]
forward pass frontier nodes = [c(7), b(10)]
reverse pass frontier nodes = [c(6), a(10)]
изучить c (7) от передних переходов. Является ли это в обратном проходе исследованных узлов? № Перемещение по
forward pass explored nodes = [a(0), c(7)]
forward pass frontier nodes = [b(10)]
исследовать c (6) с пограничных переходов. Это в передовых проверенных узлах? Да. Перерасчет му
mu = distance(a,c) + distance(c,b) = 6 + 7 = 13
reverse pass explored nodes = [b(0), c(6)]
reverse pass frontier nodes = [a(10)]
проверка завершение
top_node(forward pass frontier nodes) + top_node(reverse pass frontier nodes) >= mu
10 + 10 > 13?
да. Обратный канал-с-б
Ссылка: Slide 10 на http://www.cs.princeton.edu/courses/archive/spr06/cos423/Handouts/EPP%20shortest%20path%20algorithms.pdf
Этот ответ мне не помогает: Termination Criteria for Bidirectional Search