![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
gxachaturovВ нем участвует "функция эвристической оценки расстояния от рассматриваемой вершины к конечной (обозначается как h(x))".
Допустим, я хочу с помощью А* решать "головоломку в 15" (или 8).
Предлагается два варианта такой функции h(x):
-- дистанция Xемминга (число фишек не на своем родном поле по отношению к целевой конфигурации)
-- сумма по всем фишкам их манхеттенской дистанций до соответсвующих целевых позиций.
Вопрос: какой из двух вариантов будет лучше?
no subject
Date: 17 Aug 2020 15:54 (UTC)Я стартовую позицию для поиска задаю как перетасованную целевую с помощью серии случайных ходов. Так вот, если этих ходов мало (10), то Хемминг в разумное время все же находит обратный путь. А если много (100), то я не дождался. В отличии от манхетена.
Что забавно, так это прямой перебор (без А*) оказывается лучше, чем Хемминг, хотя в разы хуже, чем манхеттен. Скорее всего, это из-за накладных расходов на манипуляции с очередью-с-приоритетом, когда эта очередь становится слишком длинной.