搜索算法——深度-广度.doc

《搜索算法——深度-广度.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、搜索算法——深度优先（DFS）、广度优先（BFS）1.深度优先搜索所谓深度优先搜索，其思想概括如下：（1）在每个阶段的决策时，采取能深则深的原则试探所有的方案，一旦深入一层则保存当前操作引起的状态。（2）一旦试探失败，为了摆脱当前失败的状态，采取回到上一阶段尝试一下方案的策略（回溯策略）；或则在求解所有解时，求得一个解后，回溯到上一阶段尝试下一方案，以求解下一个解。（3）在各个阶段尝试方案时，采取的是穷举的思想。2.广度优先在深度优先搜索法中，深度越大的结点优先得到扩展，若把它改为深度越小的结点越先得到扩展，就是广度优先搜索法。由于广度优先

2、搜索先将所有与上一层结点相邻接的结点搜索完之后，再继续往下搜索与该层所有邻接而又没有访问过的结点，可以看作是分层次搜索的。因此，当某一层出现目标结点时，这时所进行的步骤是最少的。所以，广度优先搜索管饭应用于求解问题的最短路径、最少步骤、最优方法等方面。【11-4-1】米宫问题（maze）（广度优先BFS）问题描述：在一个由n*m（n，m<=5）个方格组成的迷宫中，设有t处障碍，在每一个格子中，只能上下左右移动，当然障碍处不可通过。如果给定出发点和目标点的坐标，要求每个方格最多经过1次，能否走出迷宫，如果能输出最短路径长度，否则输出-1。输入

3、格式：第一行三个用空格分隔的数字n、m和t。其中n为行，m为列，t为障碍总数。第二行四个空格分隔的数字，分别表示出发点和目标点的坐标。接下来t行，每行为一个障碍点的坐标。输出格式：一个数字，表示最短路径长度（不能到达则输出-1）。【11-4-2】零点游戏（zerosum）（深度优先DFS）问题描述：玩过24点的人都知道：游戏是对于给定的4个数字运用四则运算，使其最终计算结果为24.现在有人在此基础上发明了零点游戏：对于给定的数字n（2

4、何符号（第一个数字前不能插入符号），数列就变成一个表达式，找出能满足上述要求所有结点为零的表达式。输入格式：一个整数n。输出格式：按照ASC码的顺序，输出所有符合要求的表达式（每对数字间用“+”、“-”、“（空格）”分隔）。