Блог

Я недавно изучаю поиск по графу и поиск по дереву, и я вижу, что во многих примерах упоминается что-то вроде «путь, возвращаемый поиском по графику xxx,…» Однако поиск по графу-это метод обхода, как он может возвращать путь?

Мы знаем, что при поиске по дереву каждый узел соответствует определенному пути, и, посетив узел, мы узнаем соответствующий путь. Я достаточно хорошо знаком с поиском по деревьям, но при поиске по графам цель состоит в том, чтобы посетить пункт назначения, а не найти путь к месту назначения. Тогда как мы можем определить путь, возвращаемый поиском по графику?

Например, ниже приведен график.

 Graph
       B
      / 
     /   
Start     Destination
        /
       /
       C
 

Когда мы делаем BFS на старте, последовательность посещений- Start-B-C-Destination или Start-C-B-Destination . Тогда каким должен быть обратный путь? Если мы используем очередь, мы можем сказать, что мы ставим в очередь Destination при посещении B (или C ), поэтому возвращаемый путь Start-B-Destination (или Start-C-Destination ), тогда как насчет следующего графика?

 Graph
       B
      / 
     /   
Start-----D-----Destination
        /
       /
       C
 

Очевидно, D что при посещении ставится Start в очередь , поэтому единственным возможным путем должен быть Start-D-Destination ?

В поиске* возникает больше проблем. Если узел посещается не по кратчайшему пути (из-за плохой эвристической функции), то каким должен быть конечный возвращаемый путь? Например, на приведенном ниже графике последовательность посещений такова Start-B-D-C-Destination , то каким должен быть возвращаемый путь? Start-B-D-Destination или Start-C-D-Destination ? Мы посетили D , когда B находимся на окраине, однако, когда мы рассчитываем стоимость от Start до D , мы рассчитываем Start-C-D , и стоимость должна быть 2, а не 3.

 Graph
        B
       / 
      1   2
     /     
Start       D--5--Destination
          /
      1   1
        /
        C

h(B) = 2, h(C) = 4, h(D) = 1
 

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

Спасибо за ваше терпение, и я буду очень признателен, если кто-нибудь сможет дать мне ответ.

Я буду использовать ваш пример:

         B
       / 
      1   2
     /     
Start       D--5--Destination
          /
      1   1
        /
        C
 

Обратите внимание, что чистый поиск по ширине не обращает внимания на вес ребер (или стоимость). В этом случае первым путем, который приведет его к месту назначения, может быть Start->B->D->Destination .

Он помечает каждый узел, который он посещает, логическим флагом, чтобы указать, что узел был посещен, чтобы он не преследовал Start->B->Start->C->Start->... , чтобы запомнить успешный путь, мы должны где-то хранить немного больше информации. Один из простых подходов состоит в том, чтобы пометить каждый узел не только visited флагом, но и ссылкой на узел , с которого он был посещен. Поэтому, если порядок посещения был Start, B, C, D, Destination , график будет выглядеть следующим образом:

         B(Start)
       / 
      1   2
     /     
Start       D(B)--5--Destination(D)
          /
      1   1
        /
        C(Start)
 

Тогда мы сможем вернуться назад. Как мы до этого добрались Destination ? От D . Как мы до этого добрались D ? От B . Как мы до этого добрались B ? От Start .

Поиск по ширине сначала следует за первым ребром в очереди и находит кратчайший путь (в смысле наименьшего числа ребер). Если нам нужен путь с наименьшим весом (самый дешевый), мы изменяем поиск, чтобы отслеживать стоимость доступа к этому узлу, и следуем по краю, который достигает нового узла наиболее дешево. (Это одна из версий алгоритма Дейкстры.) Тогда в этом случае порядок посещения будет таким же, но мы будем посещать D с C , а не с B , и получим путь Start->C->D->Destination .

С помощью A*, используя h(B) = 2, h(C) = 4, h(D) = 1, порядок посещения Start, B, D, C, D, Destination и путь Start->C->D->Destination .

Для BFS есть два варианта:

1. Когда вы ставите узел в очередь, отметьте, от какого соседа вы исходите. Затем в конце каждый узел на лучшем пути будет иметь ссылку на «предыдущий» узел на пути, поэтому вы можете вернуться непосредственно от пункта назначения к началу, чтобы найти путь.
2. Когда вы ставите узел в очередь, отметьте лучший путь к этому узлу, который является просто лучшим путем к его соседу, плюс край, который вы выбрали.

Вариант 1-это то, что обычно делается, потому что это более эффективно.

Для Дейкстры (BFS для взвешенных графов), то же самое верно, за исключением того, что когда тебя поставит узел в очереди и отмечают, что сосед пришел, ты не должен нашли лучший путь к этому узлу. Если в дальнейшем вы столкнулись с такой же узел с другого соседа, вы должны сравнить суммарные расстояния обоих вариантов, и выбрать более короткий-как «назад» узел.

Это сделано в строках 18-20 псевдокода в Википедии

 18  if alt < dist[v]:              
19    dist[v] ← alt
20    prev[v] ← u
 

Как только вы развернете узел (удалите его из очереди приоритетов), вы гарантированно найдете лучший путь к узлу.

Для A* ситуация такая же, как у Дейкстры, если эвристика непротиворечива. Однако, если эвристика допустима только в этом случае, то вы не гарантируете, что нашли наилучший путь к узлу при его первом развертывании. В этом случае вам может потребоваться поставить в очередь и развернуть один и тот же узел несколько раз.

По этой причине на самом деле не очень часто используется* с несогласованной эвристикой.