1. 什么是深度搜索
从计算机科学专业上讲,深度优先搜索算法是最常用图的搜索算法之一,这一算法也是很多重要的图的算法的原型。
深度优先搜索其英文全称是Depth First Search,简称DFS。
深度搜索的特点是先看“一个方向”。例如:骑士在方格地图上搜索迷雾中隐藏的熊猫
2. 棋盘上宽度搜索(DFS)的代码实现
上面的演示中,观察到的是骑兵一但看见一个可以到达的位置,就去进去搜索。又点“类似”一个人走迷宫,一种策略是总是先顺左边墙走,直到走不下去再推到回一个路口,搜索下一个可以走的方向。
因此算法框架如下:
(1) 把初始状态放入栈中,设为当前状态;
(2) 扩展当前的状态,产生一个新的状态放入数组中,同时把新产生的状态设为当前状态;
(3) 判断当前状态是否和前面的重复,如果重复则回到上一个状态(出栈),产生它的另一状态;
(4) 判断当前状态是否为目标状态,如果是目标,则找到一个解答,结束算法。
(5) 如果栈为空,说明无解。
一般来说,深度搜索中有下面基本的要点:
l 确定搜索的规则:“从一个节点怎样看附近的节点”。比如前面的例子中,骑兵从一个格子,依次看上、下、左、右四个格子。如果改变了搜索次序,比如上、左、下、右,搜索的路线就完全不一样。
l 搜索到的“节点”一般进入遵守LIFO的栈,继续深度搜索。
l 被搜索过的节点要标记一下,下次再“看到”时,就不要重复处理进入栈。(注:这样也防止了在一个地方“绕圈”。)
l 当一个点可能的“方向”都搜索过了,会退会到“前面的状态”---如果前面状态修改了,要“恢复”。
l 搜索的结束条件---搜索不下去了,“边界条件”。
找出所有可能的线路:
深宽度搜索DFS尝试所有可能的“前进”方式,到达目标时,栈里就保存了一条完整的“线路”,很适合查找所有可能的方案。
比如:下图中马从起点向右到目标的所有线路。