Модифицированный эвристический дизайн поиска пути - PullRequest
Новая
       6

Модифицированный эвристический дизайн поиска пути

2 голосов
/ 09 февраля 2012

FIRST, идеальный путь был (в порядке важности): 

1. shortest

Моя эвристика (f) была: 

manhattan distance (h) + path length (g)

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

ВТОРОЙ, идеальный путь был: 

1. shortest
2. approaches the destination from the same y coordinate (if of equal length)

Моя эвристика осталась прежней.Я проверил второй критерий в конце, после достижения цели.Эвристика была сделана немного неэффективной (чтобы исправить проблему поворота), что также привело к тому, что всегда находились необходимые соседние координаты.

THIRD, идеальный путь: 

1. shortest
2. approaches the destination from the same y coordinate (if of equal length)
3. takes the least number of turns

Теперь я попыталсяэвристика (f): 

manhattan distance (h) + path length (g) * number of turns (t)

Это, конечно, работает для критериев № 1 и № 3 и по существу устраняет проблему отклонения.К сожалению, теперь это настолько эффективно, что тестирование по критерию №2 в конце не работает, поскольку набор исследуемых узлов недостаточно велик, чтобы восстановить оптимальное решение.

Может кто-нибудь посоветовать мне, как вписать критерии №2 вмой эвристический (f), или как еще решить эту проблему?

КРИТЕРИИ 2 пример: Если цель (4,6) и пути к (3,6) и (4,5) имеютравной длины, то идеальное решение должно пройти через (3,6), потому что оно приближается из плоскости Y вместо (4,5), которая исходит из плоскости X.Однако, если длина не идентична, то предпочтительнее выбирать кратчайший путь независимо от того, к какой плоскости он приближается.

Ответы [ 2 ]

3 голосов
/ 09 февраля 2012

Вы, кажется, путаете эвристику A *, которую Russell & Norvig называют h , с частичной стоимостью пути g .Вместе они составляют приоритет f = g + h .

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

Однако ваш критерий 2 должен идти по стоимости пути г , не в ч .Я не уверен, что именно вы подразумеваете под «приближается к пункту назначения с той же координатой y», но вы можете запретить / оштрафовать вход в узел цели, предоставив всем другим подходам бесконечную или очень высокую стоимость пути.Строго не нужно изменять эвристику h .

Количество пройденных поворотов также должно указываться в частичной стоимости пути g .Возможно, вы захотите включить в h (оптимистичную) оценку того, сколько оборотов осталось сделать, если вы можете вычислить такую ​​цифру дешево.

1 голос
/ 09 февраля 2012

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

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

dy = min(absolute_value(dy), absolute_value(dy-1));

Тогда при построении эвристики (f): 

h = hacked_manhattan_distance();
if (h < 2)
   // we are beside close to the goal
   // switch back to real distance
    h = real_manhattan_distance();
...