Вопросы Теги

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

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

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

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

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

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

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

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

24
задан amit 24 October 2011 в 17:11
поделиться

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.

6
ответ дан 29 November 2019 в 00:30
поделиться
Другие вопросы по тегам:

Похожие вопросы: