#algorithm #a-star #heuristics #search-tree
#алгоритм #a-star #эвристика #поиск-дерево
Вопрос:
Рассмотрим три эвристики для 8-головоломки:
h1(n) = number of misplaced tiles
h2(n) = total Manhattan distance
h3(n) = max(h1, h2)
В 8-головоломке я выполнял разные головоломки и заметил, что эвристическая функция h3 (max), похоже, обеспечивает то же решение, что и эвристика общего расстояния Манхэттена. Для этого используется алгоритм поиска по звездам.
Мне было интересно, всегда ли эвристическая функция общего расстояния Манхэттена доминирует над количеством неуместных плиток?
Ответ №1:
Да, потому что вы получите то же значение только в том случае, если все неуместные плитки находятся рядом с их правильным местом (т.е. Расстояние до Манхэттена = 1). Во всех остальных случаях манхэттенское расстояние для неуместно размещенной плитки равно > 1.
Комментарии:
1. Другими словами, эвристика «неуместных плиток» в основном
sum(min(1, manhatten(x)) for x in tiles)2. Будет ли когда-нибудь случай, когда эвристическое количество неуместных плиток больше, чем манхэттен?
3. @Lebronfan23 каждая неуместная плитка находится на расстоянии не менее 1 в соответствии с Манхэттеном. Таким образом, количество неуместных плиток всегда меньше или равно сумме расстояния Манхэттена.