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

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

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

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

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

8-puzzle start goal

Вы можете попробовать этот решатель и поставить порядок черепицы как "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 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;
}

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

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

Ответы

Ответ 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.