常用算法笔记 > 回溯法
回溯法思想

回溯法是一种搜索算法,从根节点出发,按照深度优先搜索的策略进行搜索,到达某一节点后 ,探索该节点是否包含该问题的解,如果包含则进入下一个节点进行搜索,若是不包含则回溯到父节点选择其他支路进行搜索。

 

回溯法的设计步骤:

1)针对所给的原问题,定义问题的解空间

2)确定易于搜索的解空间结构

3)以深度优先方式搜索解空间,并在搜索过程中用剪枝函数除去无效搜索。

示例:0-背包问题、旅行商问题、八皇后问题