Когда завершается A *

Question

При выполнении поиска A * по дереву с 1 заданным исходным узлом (корнем дерева) и несколькими целевыми узлами, когда алгоритм завершит работу?

Завершается ли он после нахождения первой цели или продолжается до полного посещения дерева

Answer 1

Ни одно из этих условий завершения не является совершенно правильным.

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

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

Затем алгоритм завершается, когда вершина цели отбрасывается из очереди как та, которая имеет минимальную стоимость.