数据结构与算法 |
您所在的位置：网站首页 › 上一次的搜索 › 数据结构与算法 |
数据结构与算法
|
文章目录
一、广度优先搜索（Breadth First Search，BFS）1. BFS算法过程2. python实现3. 算法分析
二、图的应用：骑士周游问题1. 构建骑士周游图2. 骑士周游问题算法实现3. 骑士周游问题算法分析与改进（1）算法分析（2）算法改进
4. 启发式规则（heuristic）
三、深度优先搜索（Depth First Search，DFS）1. python代码实现2. 算法分析
一、广度优先搜索（Breadth First Search，BFS）
在前面的词梯问题中，在单词关系图建立完成以后，需要继续在图中寻找词梯问题的最短序列，这就需要用到“广度优先搜索（Breadth First Search，BFS）”。BFS是搜索图的最简单算法之一，也是其它一些重要的图算法的基础。 给定图G，以及开始搜索的起始顶点s。BFS搜索所有从s可到达顶点的边。而且在达到更远的距离k+1的顶点之前，BFS会找到全部距离为k的顶点。（看不懂没关系，看完后面的举例就明白了） 可以想象为以s为根，构建一棵树的过程，从顶部向下逐步增加层次。广度优先搜索能保证在增加层次之前，添加了所有兄弟节点到树中。 1. BFS算法过程我们从fool开始搜索，从fool可以到达的顶点有foul、foil、cool、pool，完成第一轮，距离为1。然后再依次以这四个顶点为起点，寻找下一步可以到达的顶点fail、poll，完成第2轮，距离等于2。然后是第三轮……。如此反复，直到抵达目标sage为止。
但有些顶点之间的距离是不确定的，比如fool到pool，可以直接到达，距离为1；也可以通过cool到达，距离为2。 为了跟踪顶点的加入过程，并避免重复顶点，要为顶点增加3个属性： 距离（distance）：从起始顶点到此顶点路径长度；前驱顶点（predecessor）：可反向追溯到起点；颜色（color）：标识了此顶点是尚未发现（白色）、已经发现（灰色）、还是已经完成探索（黑色）。还需要用一个队列Queue来对已发现的顶点进行排列，已经发现的放到队首，完成探索的放到队尾。以此决定下一个要探索的顶点（队首顶点）。 算法过程： 从起始顶点s开始，作为刚发现的顶点，标注为灰色，距离为0，前驱为None。将s加入队列，接下来是个循环迭代过程： 从队首取出一个顶点作为当前顶点；遍历当前顶点的邻接顶点；如果是尚未发现的白色顶点，则将其颜色改为灰色（已发现），距离增加1，前驱顶点为当前顶点，加入到队列中；遍历完成后，将当前顶点设置为黑色（已探索过），循环回到步骤1的队首取当前顶点。 2. python实现 def bfs(g,start): # 参数：图，起点 # 起点的距离设置为1 start.setDistance(0) # 起点的前驱设置为None start.setPred(None) vertQueue = Queue() # 将起点放入队首 vertQueue.enqueue(start) while (vertQueue.size() > 0): # 取出队列的队首元素作为当前顶点 currentVert = vertQueue.dequeue() # 遍历当前顶点的邻接顶点 for nbr in currentVert.getConnections(): if (nbr.getColor() == 'white'): nbr.setColor('gray') nbr.setDistance(currentVert.getDistance() + 1) nbr.setPred(currentVert) vertQueue.enqueue(nbr) # 当前顶点探索完成，设置为黑色 currentVert.setColor('black')在以FOOL为起始顶点，遍历了所有顶点，并为每个顶点着色、赋距离和前驱之后。就可以通过一个回途追溯函数来确定FOOL到任何单词顶点的最短词梯！ def traverse(y): # y是目标单词 x = y while (x.getPred()): print(x.getId()) x = x.getPred() print(x.getId()) traverse(g.getVertex('sage')) 3. 算法分析BFS算法主体是两个循环的嵌套： while循环对每个顶点访问一次，所以是 O ( ∣ V ∣ ) O(|V|) O(∣V∣)，V是顶点数量； 而嵌套在while中的for，由于每条边只有在其起始顶点u出队的时候才会被检查一次，而每个顶点最多出队1次，所以边最多被检查1次，一共是 O ( ∣ E ∣ ) O(|E|) O(∣E∣)，E是边的数量。 综合起来BFS的时间复杂度为 O ( ∣ V ∣ + ∣ E ∣ ) O(|V|+|E|) O(∣V∣+∣E∣)。 建立BFS树之后，回溯顶点到起始顶点的过程，最多为 O ( ∣ V ∣ ) O(|V|) O(∣V∣)。创建单词关系图也需要时间，最多为 O ( ∣ V ∣ 2 ) O(|V|^2) O(∣V∣2)。 二、图的应用：骑士周游问题在一个国际象棋棋盘上，一个棋子“马”（骑士），按照“马走日”的规则，从一 个格子出发，要走遍所有棋盘格恰好一次。把一个这样的走棋序列称为一次“周游”。 在8×8的国际象棋棋盘上，合格的“周游”数量有 1.305 × 1 0 35 1.305\times 10^{35} 1.305×1035这么多，走棋过程中失败的周游就更多了。 采用图搜索算法，是解决骑士周游问题最容易理解和编程的方案之一，解决方案还是分为两步： 首先将合法走棋次序表示为一个图；采用图搜索算法搜寻一个长度为（ 行 × 列 − 1 行\times 列-1 行×列−1）的路径，路径上包含每个顶点恰一次。 1. 构建骑士周游图将棋盘和走棋步骤构建为图的思路： 将棋盘格作为顶点；按照“马走日”规则的走棋步骤作为连接边；建立每一个棋盘格的所有合法走棋步骤能够到达的棋盘格关系图。比如下面的“马”，它的下一步合法移动可以表示为右边的图：
它可以走的合法格子最多8个，如果“马”最初在一个靠边的位置，那么就能走的格子就少于8个。 合法走棋位置函数： def genLegalMoves(x,y,bdSize): newMoves = [] """ “马”走日，可以前往的格子最多有8个 通过对“马”的当前位置（x、y）进行加减，得到合法的移动位置 """ moveOffsets = [(-1,-2),(-1,2),(-2,-1),(-2,1), ( 1,-2),( 1,2),( 2,-1),( 2,1)] # 依次将偏移量加到“马”的当前位置上，保存新的位置 for i in moveOffsets: newX = x + i[0] newY = y + i[1] # 确保不会走出棋盘，将落在棋盘内的移动位置，追加到合法移动列表中 if legalCoord(newX,bdSize) and \ legalCoord(newY,bdSize): newMoves.append((newX,newY)) return newMoves def legalCoord(x,bdSize): # 确保不会走出棋盘 if x >= 0 and x |
【本文地址】
今日新闻 |
推荐新闻 |