Почему в алгоритме A-звезды h (x) вычитается, если эвристическая функция h монотонна?

Question

Может быть, я упускаю что-то очень простое и очевидное.

Но я не понимаю, почему оценочная стоимость исходной вершины вычитается из общей оценочной стоимости, если эвристическая функция h является монотонной (последовательной):

Монотонная функция: f(x) = g(x) + h(x) Немонотонная функция: d'(x, y) = d(x, y) + h(y) − h(x)

UPD :

Я был смущен и совершенно не понял монотонную / немонотонную эвристику. @ ответ david-aisenstat помог мне внести исправления в вопрос:

Алгоритм * может использоваться как расширение алгоритма Дейкстры. На каждой итерации своего основного цикла он выбирает вершину с минимальной оценочной стоимостью плюс стоимость пути к этой вершине:

Для вершины u и ее преемника v общая стоимость вычисляется по формуле f(u, v) = d(u, v) + h(v) с использованием некоторой эвристической функции h. Где:

• d(u,v) стоимость пути от u до v
• h(v) оценка стоимости от v до целевой вершины t

Если для любых смежных вершин u и v верно, что h(u) <= d(u, v) + h(v), то h является монотонным. Другими словами, граф содержит свойство треугольника .

Это указано на вики-странице A * алгоритма :

Если эвристика h удовлетворяет дополнительному условию h (x) ≤ d (x, y) + h (y) для каждого ребра (x, y) графа (где d обозначает длину этого ребра), то h называется монотонным или последовательным. В таком случае A * может быть реализован более эффективно - грубо говоря, ни один узел не должен обрабатываться более одного раза (см. Закрытый набор ниже) - и A * эквивалентно выполнению алгоритма Дейкстры с уменьшенной стоимостью d '(x, y) = d (x, y) + h (y) - h (x).

Мои вопросы:

и A * эквивалентно выполнению алгоритма Дейкстры с уменьшенной стоимостью d '(x, y) = d (x, y) + h (y) - h (x).

Есть ли доказательства этой эквивалентности?

Понятно, что 0 <= d(x, y) + h(y) - h(x), и это выполнимо. Но:

• Почему эта формула выбрана в качестве новой функции расстояния?
• Есть ли формальное доказательство того, что это работает?
• Почему недостаточно запустить Дейкстру с d '(x, y) = d (x, y) + h (y)?
• Что за этим стоит математика?

Answer 1

Условие, которое вы пометили как «Не монотонный», на самом деле является условием того, чтобы быть монотонным. Уравнение в «Монотонном» - это то, как вывести новую функцию расстояния, d', которая включает в себя согласованную эвристику h в d. Затем вы можете запустить Dijkstra на d', который не смотрит на h, кроме как через значение d'.

Псевдокод для A * в Википедии опускает вычитание, поскольку речь идет об общем допустимом эвристическом случае, в котором f(n) = g(n) + h(n) используется в качестве нижней границы стоимости решения, использующего узел n через путь, который стоит * 1011. *.