回溯法解题思路
(1)针对所给问题,定义问题的解空间;
(2)确定易于搜索的解空间结构;
(3)以深度优先方式搜索解空间,并在搜索过程中用剪枝函数避免无效搜索。
回溯就是让计算机自动的去搜索,碰到符合的情况就结束或者保存起来,在一条路径上走到尽头也不能找出解,就回到原来的岔路口,选择一条以前没有走过的路继
续探测,直到找到解或者走完所有路径为止。就这一点,回溯和所谓的DFS(深度优先搜索)是一样的。那现在的关键是,怎么实现搜索呢?回溯既然一般使用递
归来实现,那个这个递归调用该如何来写呢?我现在的理解就是,进行回溯搜索都会有一系列的步骤,每一步都会进行一些查找。而每一步的情况除了输入会不一样
之外,其他的情况都是一致的。这就刚好满足了递归调用的需求。
通过把递归结束的条件设置到搜索的最后一步,就可以借用递归的特性来回溯了。因
为合法的递归调用总是要回到它的上一层调用的,那么在回溯搜索中,回到上一层调用就是回到了前一个步骤。当在当前步骤找不到一种符合条件情况时,那么后续
情况也就不用考虑了,所以就让递归调用返回上一层(也就是回到前一个步骤)找一个以前没有尝试过的情况继续进行。当然有时候为了能够正常的进行继续搜索,
需要恢复以前的调用环境。
阅读(11767) | 评论(0) | 转发(2) |