浅谈深搜框架

· · 个人记录

一.搜索与回溯

搜索与回溯是计算机解题中常用的算法，很多问题无法根据某种确定的计算法则来求解，但是可以利用搜索与回溯的技术求解。

回溯是搜索算法中的一种控制策略。它的基本思想是:为了求得问题的解，先选择某一种可能情况向前探索，在探索过程中，一旦发现原来的选择是错误的，就退回一步重新选择，继续向前探索，如此反复进行，直至得到解或证明无解。

二.深度优先搜索框架

void Search(int k) {
    if(到目的地) 输出解                 //边界条件
    else
        for (i=1;i<=算符总数;i++)      //枚举所有可能性
            if (满足条件){             //约束条件
                保存结果和状态
                Search(k+1);          //递归搜索
                恢复保存结果之前的状态  //状态恢复
            }
        }
}

三.应用

1.迷宫问题

在一方形迷宫中有n*m个格子，
我们知道闯迷宫的人的初始坐标 (sx,sy) 以及目标出口 (tx,ty)，
以及迷宫中若干障碍物的坐标。
每次我们可以向上、下、左、右的格子做一次移动，
让我们判断是否能够到达迷宫出口，
或者统计到达迷宫出口的方案数。

2.排列组合问题

从n个不同元素中任取m（m≤n）个元素，
按照一定的顺序排列起来，
叫做从n个不同元素中取出m个元素的一个排列。
当m=n时所有的排列情况叫全排列。

完结撒花★,°:.☆(￣▽￣)/$:.°★ 。