Эвристика в A *, когда точный вес состояния цели неизвестен

Question

Итак, вот проблема, над которой я работал: Вам дается случайная сетка nxn с весами в каждой ячейке сетки, а также набор колышков p <= n. Ваша цель - разместить колышки на сетке так, чтобы сумма весов на сетке, где колышки были размещены, была максимальной. Ограничение состоит в том, что позиции колышков также должны соответствовать позициям не-атакующей королевы. </p>

Моя первая попытка состояла в том, чтобы начать с поля сетки максимального количества баллов и следовать расположению n-ферзя. Тем не менее, это не работает, так как в конце пропускается максимальное значение.

Я пытался решить эту проблему с помощью A *, но изо всех сил пытался найти эвристику.

Answer 1

Обычно * поиск используется для поиска кратчайшего пути, а не для поиска максимального значения, но вы также можете использовать его для максимизации. В обычной версии минимизации ваша эвристика всегда должна быть нижней границей длины. Чтобы максимизировать, эвристика должна быть верхней границей, которую не сложно вычислить. И вам нужна максимальная куча, а не минимальная куча, чтобы создать следующего лучшего кандидата.

Еще одна проблема заключается в том, что есть много разных заказов, чтобы выбрать лучшее размещение. С доской n x n таких заказов будет n!. Вы значительно ускорите свой поиск, если будете делать что-то вроде настаивания на выборе от наибольшего до наименьшего пина.

Поэтому я бы предложил в качестве эвристики сумму самых больших пинов, которые еще не атакованы и не превышают наименьшего пина, который вы в настоящее время выбрали без , пытаясь проверить, что он не атакующий. , Это легко вычисляемая верхняя граница, и вы начнете с очевидного жадного выбора - попытаться захватить самый большой из доступных пинов.