ИИ дерево поиска. Временная сложность 8-королевы, размещая по одному без атаки

Question

Один из подходов к достижению состояния цели состоит в том, чтобы "добавить ферзь к любому квадрату в крайнем левом пустом столбце, чтобы он не подвергался атаке со стороны любой другой королевы". И этот подход будет иметь пространство состояний 2057 (также интересно, как это вычислить?)

Какова временная сложность, если я использую алгоритм поиска Depth First (который я считаю наиболее подходящим)? Как насчет сложности пространства?

Я озадачен, потому что когда дерево углубляется, количество поисковых запросов значительно уменьшается. O(8**8) выглядит слишком много для сложности времени, даже в худшем случае.

Спасибо

Answer 1

Время поиска в глубину зависит от того, насколько умным является алгоритм, чтобы решить, какую ветвь исследовать в первую очередь.

У N queens есть чит: у него есть эвристика ( см. Описание в Википедии), которая дает идеальное решение за полиномиальное время. Если решения вашего первого поиска в глубине просто имитируют решения эвристики, то ваш первый поиск в отделе также является многократным.