Является ли Евклидово расстояние в квадрате допустимой эвристикой?

Question

У меня есть сетка, как показано на рисунке. До сих пор я реализовал функции ниже как мои эвристические функции. Итак, цель этой игры - собрать все числа, размещенные на этой сетке. Начальная точка А.

1. Манхэттенское расстояние, а затем взять его максимальное значение для расчета эвристики.

    distance = abs(A_x-x_i)+abs(A_y-y_i)
    if distance > manhMax:
       manhMax = distance

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

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

Мне пришла в голову идея расчета квадрата евклидова расстояния между расстояниями между расстояниями от А до 2, а затем до 1, а затем до 3 и 0. Как такового порядка не существует для сбора чисел. Однако проблема заключается только в евклидовом расстоянии, расширяющем слишком много состояний, хотя это допустимо. Не могли бы вы помочь мне с подходящим расстоянием или методом для достижения моей задачи.

Спасибо!

Answer 1

Я подозреваю, что у вас возникли проблемы с интерпретацией вашего подхода, потому что в этой задаче нет простой единой цели, используемой для определения «допустимого». Скорее, у вас есть небольшой TSP (Задача коммивояжера), в котором вы можете собирать предметы в любом из 4! заказы. Вы не описали , какое расстояние вы использовали в своем подходе, но упрощенные вычисления не подойдут. Добавление всех 10 расстояний (для n = 5 узлов; 5x4 / 2) - это просто перерасход, так как вы пройдете только 4 из этих ребер. Точно так же неверно добавлять расстояния от A до каждого элемента.

Вместо этого вам нужно использовать эвристику на каждом ребре пути, добавить, а затем сгенерировать эвристическую оценку для рассматриваемого пути с четырьмя ребрами. Для этой обработки евклидово расстояние допустимо, но его квадрат - нет: оно серьезно переоценивается и находится в неправильных единицах (площадь, а не расстояние). Манхэттенское расстояние, вероятно, будет лучше для вас.

Обратите внимание, что у вас есть проблемный случай в этом примере, так как преимущество 3-0 будет недооценено в 4-5 раз, в зависимости от вашей эвристики.