拥抱「资料结构」的「演算法」(28) - 深度优先与广度优先搜寻法

前言

图形也有搜寻演算法可以使用，例如深度优先搜寻法与广度深度优先搜寻法，一起来看看吧

生活常识

你在超市购物时，都是怎麽选购货架上的物品？是使用左右扫射，还是上下扫瞄呢？哪一种方式可以最快找到你想买的东西呢？

图片来源:https://www.pexels.com/zh-tw/photo/1005638/

你玩过迷宫吗？这是个很考验运气、耐性、智慧与勇气的游戏，从起点走到终点，会出现很多路径，面临多条路径的选择时，常常会出现选择障碍，因为如果选错可能就会走回头路，你会怎麽决定你的策略呢？

1. 随机选一条路之後就勇往直前等遇到死路在做打算，
2. 每个路径会先去探一小段路之後再做打算

不管是哪一种，都很有可能走得头昏眼花、四肢不听使唤，最後还不见得能顺利过关XD，不知道你有没有听过一种可以快速破解迷宫的方法，叫做沿墙走，不过只适用於某些类型的迷宫，最土法炼钢的方式就是勇敢尝试，试到最後面一定会找到出口，只怕时间不够或是你已经感到心疲力竭先放弃了，那要怎麽预防迷路呢？可以学习童话故事中丢面包屑的方式，让自己清楚知道要注意哪些路径

图片来源:https://www.pexels.com/zh-tw/photo/1904204/

专业知识

图形说明

如果对於树或图形结构不熟悉的话，可以参考前几天的文章，图形是由许多顶点与边组成的，而树也是图的一种，当今天我们在某着顶点，想要到达某个顶点时，会经过某些路径，而要如何快速找到这两个顶点之间的相连路径，就是演算法要做的事情

判断是否走过

由於目标顶点位於图形的哪个位置我们并不知道，检查该顶点是不是我们要寻找的顶点，在搜寻过程中为了清楚知道哪些顶点是已经搜寻过的(就像走迷宫可以丢面包屑或做记号)，我们必须透过其他的资料结构堆叠、伫列或是使用递回演算法来辅助我们记忆已访问过的顶点或路径，才不会做重覆性的搜寻

深度优先搜寻法 Depth-first Search

选择路径

如果要找 A 走到 G 的路径，请找一个与 A 相邻的点且没有走过的点，重覆以下两个动作直到找到目标点或所有点都被走过为止

• 有找到：判断是否为目标点，如果不是则将此点纪录为已走过，并以此点为新的点，再继续往下找与新点相邻且没有走过的点，例如， B 与 A 相邻，B 不是 G 点，所以再去找与 B 相邻的点，找到 C
• 没找到：回到前面的点，然後再去找到其他没有走过的相邻点做搜寻，例如，与 C 点相邻的点都走过了，还是找不到 G 点，那就要回到 B，再去找与 B 相邻且没有走过的点

例子

如果以二元树作为例子，其实搜寻方式就很类似前序走访，例如从节点 1 走到节点 6，如果这是一个迷宫，使用深度搜寻实际走的样子会长这样

只是要特别注意的是走访过的节点不能再度走访，所以使用堆叠後进先出的特性来记录还没有走过的节点，如果忘记堆叠的可以参考前几天的文章

由上图可发现，深度优先会一直往下一层搜寻，直到树叶节点还找不到未走过的节点时，才会往上一层找没有走过的节点，搜寻顺序为：1、2、4、5、6、6、7

广度优先搜寻法 Breadth-first Search

选择路径

如果要找 A 走到 G 的路径，请找一个与 A 相邻的点且没有走过的点，重覆以下两个动作直到找到目标点或所有点都被走过为止

• 有找到：判断是否为目标点，如果不是则将此点纪录为已走过，并回到上一个基准节点去寻找其他与基准节点相邻的点，例如，A 为基准点 B，A 与 B 相邻，但 B 不是 G 点，所以需要回到 A 点，再去找与 A 相邻且没有走过的点，会找到 C
• 没找到：表示与基准节点相邻的点都不是目标点，则找新的基准点，例如，以 A 为基准点的相邻节点都走过了，则可使用 B 当作基准点，再去找与 B 相连的节点

例子

如果以二元树作为例子，其实搜寻方式如下图，例如从节点 1 走到节点 6，如果这是一个迷宫，使用广度搜寻实际走的样子会长这样

只是要特别注意的是走访过的节点不能再度走访，所以使用伫列後进先出的特性来记录还没有走过的节点，如果忘记伫列的可以参考前几天的文章

由上图可发现，广度优先会往同一层搜寻，直到找不到未走过节点时，才会往下一层找没有走过的节点，搜寻顺序为：1、2、3、4、5、6、7

今日小结

深度与广度谁比较好呢？其实还是要看使用的情境，如果已经有个很明确的目标，那深度也许是不错的选择，但资源有限的情况下，可能广度会比较好，个人看法，参考参考XD

今日谜题

小美遇到的人生的十字入口，入口位於下图的上方，有三个入口，行经路线只要经过线条，就必须强制转弯，途中会经过许多字母，其中一条路可以组成一个有意义的单字，小美不知道该如何选择，请问你能帮他找到对他最有意义的一条路径吗？

昨日谜题

谜题说明：认识到费式数列的规则之後，再去认识其他的类似也有其他规则的数列，这段数列 1, 1, 1, 2, 2, 3, 4, 5, 7, 9, 12, 16, ？，其实是巴都万数列

简单来说，P(3) = P(1) + P(0) = 1 + 1 = 2，也就是说每一个数字，都是由往前推的第三个数字与第二个数字相加而来，再举一个例子，16 = 7(往前推的第三个数字) + 9(往前推的第二个数字)，所以问号处的数字会由 9 + 12 而组成，所以答案是 21，你答对了吗？