代价树深度优先搜索及优化

Depth First Search for Cost Tree and Its Optimization

代价树深度优先搜索算法是代价树搜索的常用方法之一,但在没有限制条件的情况下,可能陷入死循环或者大量无效搜索,存在搜索不完备以及所找的解未必是最优解的问题。针对深度优先搜索的缺点,在搜索过程中设计一定的剪枝条件,以提高搜索效率避免陷入死循环,并尽量返回代价更低的解。

The depth first search algorithm for cost tree is one of the common methods of cost tree search.It may fall into an endless loop or a large number of invalid searches in the case of no constraints.The depth first search may be not complete and the solution may be not optimal.Aiming to solve the shortcomings of depth first search,some pruning conditions are designed in the search process to improve the search efficiency and avoid falling into the dead loop and return the solution with lower.