#algorithm #search #tree #path-finding #a-star
#алгоритм #Поиск #дерево #поиск пути #a-star
Вопрос:
При выполнении поиска A * в дереве с 1 заданным исходным узлом (корень дерева) и большим количеством узлов назначения, когда завершится алгоритм?
Завершается ли это после нахождения первой цели или продолжается до тех пор, пока дерево не будет полностью посещено
Ответ №1:
Ни одно из этих условий завершения не является вполне правильным.
A * завершается, когда стоимость наилучшего пути к цели, который вы фактически нашли, меньше или равна наилучшей возможной стоимости любого другого пути.
Поскольку допустимая эвристическая функция никогда не переоценивает стоимость, это достигается простым помещением целевой вершины в очередь приоритетов, когда вы ее находите, с ее предполагаемой стоимостью, равной ее фактической стоимости.
Затем алгоритм завершается, когда целевая вершина удаляется из очереди как вершина с минимальной стоимостью.
Комментарии:
1. Но как он узнает, что существует больше путей к цели, если дерево посещено не полностью, возможно, последний узел, который следует посетить, является целью с наименьшим путем, и поиск может никогда не достичь его?
2. A * требует допустимой эвристики. Это означает, что стоимость каждой вершины в очереди, которая включает начальную вершину, равна <= стоимости каждого пути через эту вершину к цели. Поэтому, когда цель выходит из очереди, вы точно знаете, что не существует более коротких неоткрытых путей.
3. В случае постоянной эвристики для данного узла (т. Е. X-> Y = Z-> Y), можем ли мы завершить, когда мы найдем цель, а не когда мы всплываем цель?