* Оптимальность расширенного узла

Question

Предположим, у меня есть допустимая и последовательная эвристика.

Правда ли, что когда я расширяю узел, я гарантировал, что путь, который я нашел к этому узлу, является оптимальным?

Посмотрите на этот псевдокод из Википедии:

function A*(start,goal)
 closedset := the empty set    // The set of nodes already evaluated.
 openset := {start}    // The set of tentative nodes to be evaluated, initially containing the start node
 came_from := the empty map    // The map of navigated nodes.

 g_score[start] := 0    // Cost from start along best known path.
 // Estimated total cost from start to goal through y.
 f_score[start] := g_score[start] + heuristic_cost_estimate(start, goal)

 while openset is not empty
     current := the node in openset having the lowest f_score[] value
     if current = goal
         return reconstruct_path(came_from, goal)

     remove current from openset
     add current to closedset
     for each neighbor in neighbor_nodes(current)
         tentative_g_score := g_score[current] + dist_between(current,neighbor)
         if neighbor in closedset
             if tentative_g_score >= g_score[neighbor]
                 continue

         if neighbor not in openset or tentative_g_score < g_score[neighbor] 
             came_from[neighbor] := current
             g_score[neighbor] := tentative_g_score
             f_score[neighbor] := g_score[neighbor] + heuristic_cost_estimate(neighbor, goal)
             if neighbor not in openset
                 add neighbor to openset

 return failure

Я полагаю, это должно быть правдой. Из-за этого:

if current = goal
     return reconstruct_path(came_from, goal)

Если это не так, то этот тест не гарантирует меня, что решение оптимально, верно?

Чего я не понимаю, и причина, по которой я задаю этот вопрос, заключается в следующем:

if neighbor in closedset
         if tentative_g_score >= g_score[neighbor]
             continue

Если сосед находится в закрытом списке, это означает, что он уже расширен. Почему они тестируют результаты тогда? Почему не сработает следующее состояние?

if neighbor in closedset
         continue

Answer 1

Пожалуйста, позвольте мне внести свой вклад в этот вопрос с некоторыми наблюдениями. Большинство из них ссылаются на ответ Шаулл.

Во -первых, и, прежде всего, я обнаружил, что ответ предоставил На вопрос указал на Шолл немного странно. Собственность монотонности определяется там странным образом, и, действительно, я опубликовал вопрос-обратите внимание, что я не говорю, что это неправильно, но просто странно для меня, и не очень распространен и откровенно говоря, я немного подозрительно, что это может быть неправым.

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

Первый, последовательность обычно определяется следующим образом [Pearl, 1984]: эвристика $ h (n) $ является последовательным, если и только если $ h (n) leq c (n, n ') + h (n') $ для каждой пары узлы $ n $ и $ n '$ в государственном пространстве, где $ c (n, n') $ стоит за стоимость кратчайшего пути, присоединяющегося к $ n $ и $ n '$. Я думаю, что ясно, что приемлемость (то есть $ h (n) <h^*(n) $, где $ h^*(n) $ является истинной оптимальной стоимостью узла $ n $) сразу подразумевается от согласованности, если $ h (t) = 0 $, где $ t $ - узел цели. Об этом и других определениях см. "Общие заблуждения, касающиеся эвристического поиска".

Пока не нужно говорить "Предположим, у меня есть приемлемый и последовательный эвристика«. Достаточно сказать, что« предположим, что у меня последовательная эвристика ».

Теперь, относительно вашего первого вопроса. Если у вас есть последовательная эвристика, нет необходимости вновь открывать узлы или, эквивалентно, каждый раз, когда узел $ n $ расширяется на $^*$, путь, обнаруженный к нему, обязательно оптимальный.

Доказательство: Давайте предположим, что это не правда, и после расширения узла $ n $ по пути $ pi langle s, n_1, n_2, ldots, n_k, n rangle $ был другой путь $ pi ' langle s, n'_1, n'_2, ldots, n'_l, n rangle $ такой, что $ g _ { pi} (n)> g _ { pi '} (n) $. Обратите внимание, что $ f (n) = g (n)+h (n) $, так что из нашего предположения $ f _ { pi} (n)> f _ { pi '} (n) $, так как $ h (n) $ берет ту же ценность, несмотря на путь, за которым следует узел $ n $. Но это невозможно, поскольку $ n $ была расширена как преемник или путь $ pi $, так что $ f _ { pi} (n) leq f _ { pi '} (n) $. Конечно, вы можете сказать, что ошибка была совершена где -то по пути $ pi '$ , но это невозможно по определению последовательности.

Отсюда должно быть очевидно, что условие:

if current = goal return reconstruct_path(came_from, goal)

Работает гладко, так как после того, как цель будет расширена, гарантируется, что обнаруженный путь к нему оптимальный.

Что касается вашего второго вопроса, причина вашего поста, Шаулл уже ответил в сносах своего ответа: если эвристическая функция является последовательной, то узлы никогда не открываются, а ваше состояние:

if neighbor in closedset continue

достаточно. Однако на практике это просто заменено другим условием: при расширении узела их дети добавляются только для открытия, если он никогда не был расширен (не в закрытом месте), а также он еще не открыт (не на открытом воздухе ) С соответствующими структурами для управления открытым и закрытым списком это можно сделать очень быстро. Этот трюк делает его ненужным использовать это утверждение.

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

Надеюсь это поможет,

Перл, 1984] Иудея Перл. Эвристика. Аддисон-Уэсли. 1984

Answer 2

Алгоритм A* представляет собой не исчерпывающий алгоритм поиска, он не проверяет все возможности, но опирается на гипотезу о том, что эвристика последовательно предоставит точные оценки стоимости достижения целевого узла из данного узла на графике. Алгоритм пропустит определенные возможности из -за их затрат, но если оценка неверна, может быть лучший путь, проходящий через этот список пропущенных узлов. Таким образом, Гарандеи зависит от Heursitic Garantee.

Что касается представленного алгоритма, действительно, тест неверен. Любой узел в замкнутом списке существует, потому что он был полностью изучен и не может закричать какой -либо новый путь.

Answer 3

Это будет зависеть от эвристики. Рассмотрим график, в котором $ запустить до to d to gan $, а также $ start to b to c to d to Cond $. Теперь предположим, что у вас плохая эвристика, которая предпочитает, что дает $ B, C, D $ намного более высокие оценки, чем $ A $, тогда вы достигнете конца $ в не оптимальном пути. В частности, когда вы открываете $ D $, вы находитесь на не оптимальном пути.