Вопрос про поиск методом А*

[gxachaturov]

В нем участвует "функция эвристической оценки расстояния от рассматриваемой вершины к конечной (обозначается как h(x))". 

 

Допустим, я хочу с помощью А* решать "головоломку в 15" (или 8).

 

Предлагается два варианта такой функции h(x): 

 

-- дистанция Xемминга (число фишек не на своем родном поле по отношению к целевой конфигурации)

 

-- сумма по всем фишкам их манхеттенской дистанций до соответсвующих целевых позиций.

 

Вопрос: какой из двух вариантов будет лучше?

Comments

[juan_gandhi]

Я бы второе брал. Чисто по человечески.

[gxachaturov]

мне тоже так кажется. Ладно, забабахаю оба, потом доложу, что вышло.

[gxachaturov]

Да, конечно манхеттен лучше, чем Хемминг.

Я стартовую позицию для поиска задаю как перетасованную целевую с помощью серии случайных ходов. Так вот, если этих ходов мало (10), то Хемминг в разумное время все же находит обратный путь. А если много (100), то я не дождался. В отличии от манхетена.

Что забавно, так это прямой перебор (без А*) оказывается лучше, чем Хемминг, хотя в разы хуже, чем манхеттен. Скорее всего, это из-за накладных расходов на манипуляции с очередью-с-приоритетом, когда эта очередь становится слишком длинной.