Когда обрезка прекращает быть эффективной при поиске глубины? Я работал над эффективным методом решения проблемы N-Queens, и я смотрю на обрезку в первый раз. Я реализовал его для первых двух строк, но когда он перестает быть эффективным? Как далеко я должен обрезать?Обрезка: когда остановиться?
Проблема N-Queens обычно рекурсивна. Реализация обрезки на одной глубине должна означать ее реализацию на любой глубине.
Ответ будет зависеть от того, что вы делаете. Если вы обрезаете симметричные ходы, тогда это не стоит обрезать, когда стоимость проверки больше, чем стоимость оценки всей ветви, чем вероятность того, что ветвь будет симметричной. Для проблемы N-Queens симметрия, вероятно, не очень плодотворная процедура обрезки после первых двух строк.
Я как-то увидел цитату, касающуюся этого: «Обрезайте рано, часто обрезайте». И еще: «Не делай ничего глупого, ничего не делай дважды».
Я думаю, что количество обрезки, что вы должно быть определен вашими целями для задачи, или ваших границ на N.
Я думаю, вы должны описать ваш алгоритм более подробно. Я не уверен, что именно вы подразумеваете под обрезкой. Это никогда не перестает быть эффективным, чтобы отвергать пути, которые, как вы знаете, наверняка приведут к тупику. – IVlad