Как определить производительность эвристики для 16-головоломки?

Question

Для 16-Puzzle , скажем, у меня есть 3 эвристики: h1, h2, h3

h1 возвращает количество неуместных плиток
h2 возвращает сумму расстояний на Манхэттене
h3 возвращает сумму инвертированных пар

Стоимость каждого действия установлена ​​так, что все они недопустимы (это не тот случай, когда для всех n, h (n) <= h * (n)).Я хотел бы знать, как их ранжировать на основе скорости для любого узла / состояния.</p>

Я пытался проверить свой код.Мои результаты были (как и ожидалось): h3> h2> h1

Поскольку они не являются оптимальными, скорость, кажется, зависит от убывания размера возвращаемых значений h.Тем не менее, я не могу знать наверняка, что этот шаблон действует для ВСЕХ узлов / состояний.Я хотел бы знать, если кто-то может помочь мне знать навернякаЯ пытался найти ресурсы в поисках общего правила для этого типа шаблона, но ничего не смог найти.

Я также хотел бы знать, как сравнивать характеристики допустимой и недопустимой эвристики.

Answer 1

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

solution length: 6
number of state transitions: 15
ratio solution length / state transitions: 0.4
minimum branching degree: 2
average branching degree: 3.13333
maximum branching degree: 4
time: 0.02

Статистика собирается с использованием производительности monitor для событий (чтение, сообщения для открытого предиката)которые используют эвристику (в частности, предикат, который вычисляет следующие состояния кандидата для данного состояния).Полный исходный код примера можно найти по адресу:

https://github.com/LogtalkDotOrg/logtalk3/tree/master/examples/searching

Аналогичное решение должно быть возможно в вашем случае.