实现目标状态的一种方法是“在最左边的空列中的任何方格中添加一个皇后，这样它就不会受到任何其他皇后的攻击”。这种方法的状态空间为 2057（也想知道如何计算这个？）
如果我使用深度优先搜索算法（我认为这是最合适的算法），时间复杂度是多少？空间复杂度如何？
我很困惑，因为搜索树的早午餐在深入时大大减少。O(8**8) 对于时间复杂度来说看起来太高了，即使在最坏的情况下也是如此。
谢谢
问问题
388 次
1 回答
0
深度优先搜索的时间取决于算法决定首先调查哪个分支的智能程度。
N 皇后有一个作弊：它有一个启发式（参见维基百科上的描述），它在多项式时间内给出了一个完美的解决方案。如果您的深度优先搜索的决策只是模仿启发式的决策，那么您的深度优先搜索也是多时间。
于 2014-02-24T07:54:19.540 回答