Можем ли мы решить проблему 4 ферзей, используя поиск Best first?

Question

Я знаю, что мы можем решить эту проблему n ферзя, используя возврат, но мой преподавательский состав попросил меня решить проблему 4 ферзей, используя лучший алгоритм первого поиска. Я пытался решить это, но я не могу понять подход. Можем ли мы принять недопустимое состояние и переместить шаги блока ферзей для достижения действительного состояния?

Answer 1

Не уверен, что вы подразумеваете под Лучший первый поиск . Из руководства пользователя OptaPlanner я вижу 3 варианта, объясненных на 4 королевах:

1. Грубая сила , которая похожа на Поиск в ширину :

2. Ветвь и граница , что аналогично Поиск в глубину :

3. Первая посадка (уменьшение) :

Как говорится, N-Queens можно обмануть , так что вам лучше просто использовать это.

Answer 2

Да, Вы можете.
Вы можете использовать A * как лучший первый алгоритм. Функция стоимости для вашего A * должна быть числом атакованных ферзей. А пока используйте это же значение как эвристическое (т.е. число атакованных ферзей).
Позже вы можете попробовать и другую эвристику.