Манхэттенское расстояние переоценивает и сводит меня с ума

Question

Я реализую a-star алгоритм с Манхэттенским расстоянием , чтобы решить 8-головоломку (в C).Кажется, что он работает очень хорошо и проходит множество модульных тестов, но не может найти кратчайший путь в одном случае (он находит 27 шагов вместо 25).

Когда я изменяю эвристическую функцию на Расстояние Хэмминга находит в 25 шагах.Также в 25 шагах находит, когда я делаю функцию расстояния Манхэттена, чтобы вернуть половину фактической стоимости.

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

Я действительнопутаница, потому что эвристическая функция, кажется, единственная точка отказа, и она кажется правильной одновременно.

Вы можете попробовать этот решатель и разместите порядок плиток как "2,6,1,0,7,8,3,5,4". Выберите алгоритм Манхэттенское расстояние , и он найдется за 25 шагов.Теперь измените его на Манхэттенское расстояние + линейный конфликт и он найдет 27 шагов.

Но мое Манхэттенское расстояние (без линейного конфликта) находит в 27 шагах.

Вот мой общийАлгоритм:

manhattan_distance = 0
iterate over all tiles
if the tile is not the blank tile:
find the coordinates of this tile on the goal board
manhattan_distance += abs(x - goal_x) + abs(y - goal_y)

Я думаю, что если бы что-то очень не так с какой-то важной частью, оно не прошло бы все 25+ предыдущих тестов, так что это может быть своего рода крайний случай.

Вот прокомментированная функция расстояния Манхэттена в C:

int ManhattanDistance(Puzzle p, State b){
   State goal = getFinalState(p);
   int size = getSize(b);
   int distance = 0;
   if (getSize(goal) == size){ // both states are the same size
      int i, j;
      for(i=0; i<size; i++){
         for(j=0; j<size; j++){ // iterate over all tiles
            int a = getStateValue(b, i, j); // what is the number on this tile?
            if (a != 'B'){ // if it's not the blank tile
               int final_cordinates[2];
               getTileCoords(goal, a, final_cordinates); // find the coordinates on the other board
               int final_i = final_cordinates[0];
               int final_j = final_cordinates[1];
               distance +=  abs(i - final_i) + abs(j - final_j);
            }
         }
      }
   }
   return distance;
}

Пожалуйста, помогите мне.

РЕДАКТИРОВАТЬ: Как обсуждалось в комментариях, код, предоставленный для открытия узлов, может быть найден здесь

Answer 1

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

Читая код, который вы предоставили [в комментариях], мне кажется, я понял, в чем проблема, в строке 20:

if(getG(current) + 1 < getG(children[i])){

Это неправильно!Вы проверяете, если g(current) + 1 < g(children[i]), вы действительно хотите проверить: f(current) + 1 + h(children[i]) < g(children[i]), так как вы хотите проверить это значение с эвристической функцией children[i], а не current!
Обратите внимание, что он идентичен установке f(children[i]) = min{f(children[i]),f(current)+1} и добавлению h(children[i]) для получения значения g.