DFSID迭代加深搜索

具体原理很简单，先搜索1..K层搜索树，若无解，则继续搜索1..K+1层搜索树。 时间复杂度分析： 设：节点度数为c，完整搜索一个深度为d的树（这里d的定义:根的深度为1)。 总搜索次数： \(c^0\)+(\(c^0+c^1\))+(\(c^0+c^1+c^2\))+…+(\(c^0+c^1+c^2+...+c^{d-1}\)) =\({1-c^1+1-c^2+1-c^3+...+1-c^d}/{1-c}\) =\({d-(c^1+c^2+c^3+...+c^d)}/{1-c}\) =\({d-c(d-c^d+1)}/{(1-c)^2}\) 时间复杂度为O(\(c^{d-1}\))，空间复杂度O(\(c^{d-1}\))。 总结： 解可能离根比较近，需要用BFS，但没有足够的空间时用DFSID。

__