Обрезка: когда остановиться?

Question

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

Answer 1

Проблема N-Queens обычно рекурсивная. Реализация обрезки на одной глубине должна означать реализацию на любой глубине.

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

Answer 2

Однажды я увидел цитату по этому поводу: «Чернослив рано; часто чернослив». И другой: «Не делай глупостей; не делай ничего дважды».

Я думаю, что количество сокращений, которое вы делаете, должно определяться вашими целями проблемы или вашими границами на N.