算法设计与实践（基于MWORKS）课件 第五章 搜索算法

第五章搜索算法1.宽度优先搜索Breadth-FirstSearch2.深度优先搜索Depth-FirstSearch3.双向搜索策略BidirectionalSearchStrategy4.贪心搜索算法GreedySearchAlgorithmCONTENTS目录搜索算法的核心价值核心任务：智能寻优作为计算机科学的基石，它的核心在于在庞大而复杂的问题空间中，通过一系列智能策略，高效地定位并找到满足特定条件的解，或是在众多可能性中筛选出最优解。🎯解决问题的底层逻辑与数学模型广泛应用：无处不在从我们日常高频使用的地图导航、搜索引擎，到复杂的人工智能决策、游戏开发寻路、网络爬虫抓取以及大数据挖掘分析，它在各行各业中都扮演着至关重要的角色。🚀驱动现代数字技术发展的核心引擎宽度优先搜索Breadth-FirstSearch105.1宽度优先搜索算法5.1.1概念

宽度优先搜索算法基于图论与树结构，是一种有条理、系统的遍历算法。作为逐层遍历图或树的搜索算法，它从起始节点开始，先访问起始节点的所有邻接节点，然后再依次访问这些邻接节点的邻接节点，以此类推，按照层次顺序进行遍历。就像平静湖面投入石子泛起的涟漪，以起始节点为中心，一层一层向外扩散。先访问距离起始节点最近的一层节点，逐个探究节点信息，不遗漏细节。完成这一层后，再依次访问距离为2、3、……的节点层，逐步遍历整个图或树，确保覆盖所有节点。5.1宽度优先搜索算法使用队列（FIFO）存储待访问节点。从起始节点开始，依次访问其所有邻居节点。将邻居节点加入队列，继续访问下一层节点。010203初始化队列起始访问层次遍历核心思想完备性(Completeness)如果图中存在从起点到目标的路径，BFS一定能保证找到这条路径，不会遗漏任何可能的解。最优性(Optimality)在无权图（所有边权重相同）中，BFS按层遍历的特性保证了找到的第一条路径一定是最短路径。时间复杂度O(V+E)，V为节点数，E为边数。算法会遍历处理每一个节点和边。空间复杂度O(V)，在最坏情况下，辅助队列需要存储当前层的所有节点，空间开销取决于节点总数。5.1宽度优先搜索算法关键特点5.1宽度优先搜索算法操作原理🔑队列可视化图解图中展示了队列“入队”与“出队”的方向，直观体现了数据“先进先出”的流动过程。可将队列想象成有序生产线，起始节点作为首个待加工产品放入队列，开启流程。接着算法进入循环迭代环节，每次循环像一道工序：先取出队首节点，如同从生产线拿下产品，访问节点信息，找出未访问的相邻节点，按顺序送入队列，为后续探索储备。如此循环，直到队列为空，意味着所有能到达的节点都已访问。5.1宽度优先搜索算法步骤队列状态（从左到右为队首到队尾）取出节点加入队列的节点说明1AAB、C初始队列只有根节点A，取出A后，将A的子节点B和C加入队列2B、CBD、E取出队首B，将B的子节点D和E加入队列3C、D、ECF、G取出队首C，将C的子节点F和G加入队列4D、E、F、GD-取出队首D，D无新子节点加入队列5E、F、GE-取出队首E，E无新子节点加入队列6F、GF-取出队首F，F无新子节点加入队列7GG-取出队首G，G无新子节点加入队列8---队列为空，宽度优先搜索算法遍历结束示意图5.1.2Julia实现宽度优先搜索算法实验核心目标算法实现掌握基于邻接表构建图，并编写完整的BFS遍历逻辑。核心数据结构理解透彻理解队列(Queue)在层级调度中“先进先出”的关键作用。遍历特性可视化打印访问序列，直观观察算法“逐层向外扩展”的运行特性。5.1宽度优先搜索算法5.1宽度优先搜索算法初始化一个队列，将起始节点加入队列。初始化一个集合，用于记录已访问的节点。从队列中取出一个节点，访问该节点。将该节点的所有未访问邻居加入队列。重复步骤3-4，直到队列为空。算法步骤核心逻辑与实现(JuliaLanguage)usingDataStructures#使用队列数据结构functionbfs(graph,start)visited=Set()#记录已访问的节点queue=Queue{Int}()#初始化队列enqueue!(queue,start)#将起始节点加入队列while!isempty(queue)node=dequeue!(queue)#取出队列中的第一个节点ifnode∉visitedprintln("Visitingnode:",node)#访问节点push!(visited,node)#标记为已访问forneighboringraph[node]#遍历邻居节点ifneighbor∉visitedenqueue!(queue,neighbor)#将未访问的邻居加入队列endendendendend5.1宽度优先搜索算法核心逻辑与实现(JuliaLanguage)#示例图的邻接表表示graph=Dict(1=>[2,3],2=>[4,5],3=>[6],4=>[],5=>[7],6=>[],7=>[])#从节点1开始进行BFSbfs(graph,1)5.1宽度优先搜索算法▍程序运行输出结果BFS遍历顺序:1→2→3→4→5→6→7第一层(Level1)初始化队列，首先访问并输出起始节点：1第二层(Level2)遍历第一层节点的所有邻接节点，依次输出：2,3第三层(Level3)遍历第二层节点的所有未访问邻接节点，输出：4,5,6第四层(Level4)继续遍历，输出节点5的唯一邻接节点：7算法核心特性验证输出序列完美体现了BFS算法“逐层推进、由近及远”的搜索特性，验证了代码实现的正确性。5.1宽度优先搜索算法结果分析5.1.3实例演示▍任务背景介绍在社交网络平台中，“好友推荐”是提升活跃度的核心功能。我们需要挖掘用户的“二度好友”（朋友的朋友），而这一问题恰好可以抽象为图搜索问题，BFS是解决它的绝佳算法。▍核心问题抽象节点：代表社交网络中的每一个独立用户。边：代表用户之间已建立的直接好友关系。目标：高效搜索出距离目标用户两步之遥的所有节点。5.1宽度优先搜索算法usingDataStructures#社交网络图结构social_network=Dict("A"=>["B","C"],"B"=>["A","D","E"],"C"=>["A","F"],"D"=>["B"],"E"=>["B","F"],"F"=>["C","E"])functionfriend_recommendation(user)visited=Set{String}([user])#已访问集合（包含自己）queue=Queue{String}()enqueue!(queue,user)recommended=Set{String}()#使用集合自动去重while!isempty(queue)current=dequeue!(queue)#遍历当前用户的所有直接好友forfriendinsocial_network[current]iffriend∉visited#标记为已访问（直接好友不进入推荐列表）push!(visited,friend)#遍历二度好友（朋友的朋友）forfofinsocial_network[friend]iffof∉visited&&fof!=userpush!(recommended,fof)endendendendendreturncollect(recommended)end#测试推荐系统println(friend_recommendation("A"))#输出["D","E","F"]Step1.网络与队列初始化构建社交网络图数据结构，将用户的直接好友加入队列，并标记为已访问，作为BFS的起点。Step2.BFS广度优先层级探索循环取出队列节点，遍历其所有关联好友。重点筛选出用户未访问过的“二度好友”（朋友的朋友）。Step3.生成最终推荐列表将筛选出的二度好友去重并收集，形成最终的好友推荐结果集返回给用户。5.1宽度优先搜索算法代码执行完成，BFS算法输出推荐列表：为A推荐的好友:["D","E","F"]第一层

直接好友基于广度优先搜索(BFS)的第一层遍历，确定Alice的直接好友集合为：{B,C}第二层

二度人脉遍历直接好友的好友列表，并排除A本人，得到候选名单：D,E(来自B)

F(来自C)最终结果

去重合并对候选名单进行去重与格式整理，生成最终的推荐好友列表：["D","E","F"]5.1宽度优先搜索算法结果分析深度优先搜索Depth-FirstSearch205.2.1概念

深度优先搜索算法是用于遍历图或树结构的重要算法。和宽度优先搜索算法按层逐步推进不同，它采用“纵深”策略。从起始节点出发后，会沿着一条路径持续深入，只要还有未探索的分支，就不会转向其他路径。直到遇到叶节点，即没有后续分支，或者碰到之前已经访问过的节点，无法继续前进，才会回溯到上一个存在未探索分支的节点，再从新分支继续深入。通过不断深入与回溯，来了解图或树的内部结构。5.2深度优先搜索算法5.2深度优先搜索算法使用栈（LIFO）存储待访问节点。从起始节点开始，访问一个邻居节点并深入。回溯时访问其他邻居节点。010203初始化队列起始访问层次遍历核心思想完备性(Completeness)在有限的图中，若解存在，DFS一定能找到目标。但在无限图中，搜索过程可能陷入死循环而无法终止。非最优性(Optimality)DFS不保证找到的路径是代价最小的最短路径。由于其“深度优先”的特性，它可能沿着一条很长的分支深入，最终找到一条非最优的解路径。时间复杂度(Time)最坏情况下为O(V+E)，其中V是顶点数，E是边数。与BFS相同，每个节点和每条边都只被访问一次。空间复杂度(Space)最坏情况下为O(V)。主要取决于递归调用栈的深度（或迭代实现中的栈大小），在极端情况下需要存储整个路径上的节点。5.2深度优先搜索算法关键特点图示：栈(Stack)的“后进先出”数据结构5.2深度优先搜索算法操作原理实现深度优先搜索算法通常有两种方法：递归或栈（Stack）数据结构。

递归方式的代码较为简洁。程序运行时，系统栈自动保存节点回溯信息，无需额外操作，使得遍历过程顺畅。例如，在处理一些具有层级结构的数据时，递归的深度优先搜索算法能自然地按照深度优先顺序访问节点。

使用栈来手动模拟递归过程时，首先将起始节点压入栈，开启探索。接着进入循环：每次取出栈顶节点，访问该节点信息，然后按照先右后左的顺序，将其未访问的相邻节点压入栈，同时用标记数组记录已访问节点，避免重复访问。如此循环，直到栈为空，完成遍历。5.2深度优先搜索算法示意图（递归遍历）步骤描述访问节点下一步操作1从根节点A开始A递归访问A的左子节点B2进入B节点B递归访问B的左子节点D3进入D节点D由于D没有子节点，回溯到B4返回B节点-递归访问B的右子节点E5进入E节点E由于E没有子节点，回溯到B，再回溯到A6返回A节点-递归访问A的右子节点C7进入C节点C递归访问C的左子节点F8进入F节点F由于F没有子节点，回溯到C9返回C节点-递归访问C的右子节点G10进入G节点G由于G没有子节点，回溯到C，再回溯到A，遍历结束5.2深度优先搜索算法示意图（栈模拟）步骤栈内元素（从栈底到栈顶）取出节点访问节点新入栈节点（按顺序）1A---2-AAC,B（先右子节点C，后左子节点B）3C,B---4CBBE,D（先右子节点E，后左子节点D）5C,E,D---6C,EDD-7C,E---8CEE-9C---10-CCG,F（先右子节点G，后左子节点F）11G,F---12GFF-13G---14-GG-15---栈为空，遍历结束实验目的深入掌握DFS的递归与非递归两种核心实现方式。透彻理解栈(Stack)数据结构在非递归DFS遍历中的核心驱动作用。可视化观察DFS算法深度优先探索路径与回溯剪枝的动态特性。5.2深度优先搜索算法5.2.2Julia实现深度优先搜索算法5.2深度优先搜索算法创建一个栈，并将起始节点压入栈。弹出栈顶节点，访问并标记为已访问。对于该节点的未访问邻接节点，将其逆序压入栈（保证从左到右访问）。重复步骤2和3，直到栈为空。算法步骤非递归实现DFSusingDataStructures#导入栈数据结构functiondfs(graph::Dict{Int,Vector{Int}},start::Int)visited=Set{Int}()#记录已访问的节点stack=Stack{Int}()#初始化栈push!(stack,start)#将起始节点压入栈while!isempty(stack)current=pop!(stack)#弹出栈顶节点ifcurrent∉visitedprintln("访问节点:",current)#访问节点push!(visited,current)#标记为已访问#逆序遍历邻接节点，保证从左到右访问forneighborinreverse(graph[current])ifneighbor∉visitedpush!(stack,neighbor)#压入未访问的邻接节点endendendendend#示例图（邻接表表示）graph=Dict{Int,Vector{Int}}(1=>[2,3],2=>[4,5],3=>[6],4=>Int[],5=>Int[],6=>Int[])#从节点1开始深度优先搜索println("DFS遍历结果:")dfs(graph,1)5.2深度优先搜索算法💡代码运行核心输出DFS遍历顺序：1→2→4→5→3→6🔍执行逻辑拆解(回溯与探索)①深度优先：从根节点1出发，优先选择首个邻居2，再深入至4②首次回溯：节点4无未访问邻居，触发回溯机制，返回到上一层节点2③分支切换：节点2切换至第二个邻居5，再次走到路径尽头④最终遍历：多级回溯至根节点1，探索最后一个分支3→6，遍历完成▲深度优先搜索算法运行图5.2深度优先搜索算法结果分析

若使用递归方式，应该如何实现DFS算法？5.2深度优先搜索算法任务拓展任务背景：编译器与计算器核心在处理复杂数学表达式时，为了正确解析运算优先级，通常会将其转化为表达式树。DFS的后序遍历天然契合这一场景，因为它严格遵循“先计算子节点值，再合并计算父节点”的求值逻辑。核心逻辑抽象二叉树映射：将表达式直接映射为二叉树结构，叶子存数字，内部节点存操作符。递归计算规则：操作符节点的值=左子树结果OP右子树结果。图示：一个复杂的算术表达式被解析为对应的二叉树结构

（叶子节点为操作数，内部节点为运算符）5.2深度优先搜索算法5.2.3实例演示5.2深度优先搜索算法#定义表达式树节点结构体，增加操作符字段mutablestructExprTreeNodeval::Union{Int,String}#节点的值，可以是整数或操作符字符串left::Union{ExprTreeNode,Nothing}#左子节点，可能为ExprTreeNode类型或为空right::Union{ExprTreeNode,Nothing}#右子节点，可能为ExprTreeNode类型或为空end#构建表达式树示例root=ExprTreeNode("*",#根节点的值为乘法操作符"*"ExprTreeNode("+",ExprTreeNode(3,nothing,nothing),ExprTreeNode(4,nothing,nothing)),#左子树为加法表达式，操作数为3和4ExprTreeNode("-",ExprTreeNode(2,nothing,nothing),ExprTreeNode(1,nothing,nothing)))#右子树为减法表达式，操作数为2和1构建表达式树示例*

/\

+

-

/\/\

3

42

15.2深度优先搜索算法functioneval_expr_tree_recursive(root)#如果根节点的值是整数，直接返回该整数值ifroot.valisaIntreturnroot.valend#递归计算左子树的值，并将结果存储在left_val中left_val=eval_expr_tree_recursive(root.left)#递归计算右子树的值，并将结果存储在right_val中right_val=eval_expr_tree_recursive(root.right)#根据根节点的操作符进行相应的计算ifroot.val=="+"returnleft_val+right_val#如果是加法，返回左右子树值的和elseifroot.val=="-"returnleft_val-right_val#如果是减法，返回左右子树值的差elseifroot.val=="*"returnleft_val*right_val#如果是乘法，返回左右子树值的积递归实现的求值函数：elseifroot.val=="/"ifright_val==0error("除数不能为零")endreturnleft_val/right_val#如果是除法，返回左右子树值的商endend#调用函数计算表达式树的值result=eval_expr_tree_recursive(root)println("表达式树计算结果:",result)5.2深度优先搜索算法usingDataStructuresfunctioneval_expr_tree_stack(root)stack=Stack{Union{Int,String}}()#创建一个栈用于存储计算过程中的值和操作符postorder=[]#创建一个空列表用于存储后序遍历的节点值#定义一个内部函数进行后序遍历，并将节点值存入postorder列表functionpostorder_traversal(node)ifnode===nothing#如果节点为空，直接返回returnendpostorder_traversal(node.left)#先递归遍历左子树postorder_traversal(node.right)#再递归遍历右子树push!(postorder,node.val)#将当前节点的值存入postorder列表end非递归实现（使用栈）的求值函数：5.2深度优先搜索算法postorder_traversal(root)#对表达式树进行后序遍历forvalinpostorder#遍历后序遍历得到的节点值列表ifvalisaInt#如果值是整数，将其压入栈push!(stack,val)else#如果值是操作符right_val=pop!(stack)#从栈中弹出右操作数left_val=pop!(stack)#从栈中弹出左操作数ifval=="+"#根据操作符进行相应的计算，并将结果压入栈非递归实现（使用栈）的求值函数：push!(stack,left_val+right_val)elseifval=="-"push!(stack,left_val-right_val)elseifval=="*"push!(stack,left_val*right_val)elseifval=="/"push!(stack,left_val/right_val)endendendreturnpop!(stack)#返回栈顶的最终计算结果end#调用函数计算表达式树的值result=eval_expr_tree_recursive(root)println("表达式树计算结果:",result)代码运行结果通过代码执行，表达式(3+4)*(2-1)经过后序遍历计算，最终输出结果为7。01访问根节点，递归左子树首先定位到根节点`*`，触发递归逻辑，优先计算左子树(3+4)，得到中间结果7。02回溯根节点，递归右子树左子树计算完成后，回到根节点，继续递归计算右子树(2-1)，得到中间结果1。03结合结果，执行最终运算左右子树结果均已得出，回到根节点执行`7*1`运算，最终输出表达式的计算结果7。核心价值体现：该实例完美展示了DFS后序遍历在处理具有依赖关系的层级结构问题上的强大能力——即“先解决子问题，再回溯解决父问题”的递归思想。5.2深度优先搜索算法结果分析双向搜索策略BidirectionalSearchStrategy305.3双向搜索5.3.1概念

双向搜索的核心是整合宽度优先搜索优势，进行双向探索，同时从起始节点和目标节点进行搜索的算法，旨在减少搜索空间和提高搜索效率。面对问题时，就像同时派出两支队伍，一支从起始状态出发，依既定策略向前拓展；另一支从目标状态逆向回溯。两支队伍如同在搜索空间中反向航行的船，方向相反但目标一致。当它们在某节点相遇，就找到了从起始到目标的路径。5.3双向搜索同时进行两个BFS：一个从起始节点开始，另一个从目标节点开始。当两个搜索路径相遇时，找到最短路径。0102同时进行最短路径核心思想完备性(Completeness)如果解存在，双向搜索一定能找到。最优性(Optimality)在无权图中，能找到最短路径。时间复杂度(Time)O(bd/2)，其中b是分支因子，d是深度。空间复杂度(Space)O(bd/2）。5.3双向搜索关键特点5.3双向搜索操作原理双向搜索相当于从入口和出口同时派出两支专业的探索队伍。入口处的队伍，配备了详细记录路径的工具，每向前一步，都会仔细标记走过的路线，防止重复踏入相同的区域，有条不紊地按照宽度优先搜索策略，逐步向迷宫深处推进。出口处的队伍同样如此，不过是逆向而行，依据对出口周边环境的熟悉，沿着与入口队伍相反的方向，逐步回溯，同样严谨地标记走过的每一处节点。双向夹击·高效相遇Two-WaySearchStrategy5.3双向搜索示意图步骤正向搜索队列（从起始点出发）正向已访问节点反向搜索队列（从目标点出发）反向已访问节点操作说明1[A]{A}[F]{F}初始化，起始点

A入正向队列并标记已访问，目标点F入反向队列并标记已访问2[B,C]{A,B,C}[E]{F,E}正向取出

A，遍历相邻未访问节点B、C入队并标记；反向取出F，遍历相邻未访问节点E入队并标记3[C,D,E]{A,B,C,D,E}[B]{F,E,B}正向取出

B，遍历相邻未访问节点D、E入队并标记；反向取出E，遍历相邻未访问节点B入队并标记4[D,E]{A,B,C,D,E}[A]{F,E,B,A}正向取出

C，相邻节点已访问，无新节点入队；反向取出B，遍历相邻未访问节点A入队并标记，此时发现A在正向已访问节点中，相遇找到路径5.3双向搜索示意图A-B-C|||DEF在这个示意表中，随着步骤推进，双向搜索从起始点和目标点同时展开，不断扩展队列，记录已访问节点，直至相遇找到连接起始点与目标点的路径。每一步都严格按照双向搜索算法的规则，交替进行正向和反向的探索，确保全面且高效地遍历图结构，减少不必要的搜索空间。图5-7双向搜索算法图结构5.3双向搜索5.3.2Julia实现双向搜索算法实验目的掌握双向搜索的核心实现方法，深入理解算法中的状态转移与节点扩展逻辑。对比单向BFS算法，直观量化并感受双向搜索在空间占用与时间消耗上的效率优势。可视化观察“起点→中间”与“终点→中间”两个搜索前沿逐步扩展并最终相遇的完整过程。5.3双向搜索1.初始化起始队列和目标队列，并分别将起始节点和目标节点加入队列。2.同时从两个队列进行扩展。3.当两个搜索相遇时，找到路径。算法步骤5.3双向搜索usingDataStructures#导入队列数据结构functionbidirectional_search(graph::Dict{Int,Vector{Int}},start::Int,goal::Int)#初始化前向和后向的访问记录及队列forward_visited=Set{Int}()#存储从起始节点出发已访问的节点backward_visited=Set{Int}()#存储从目标节点出发已访问的节点forward_queue=Queue{Int}()backward_queue=Queue{Int}()#前向搜索初始化enqueue!(forward_queue,start)push!(forward_visited,start)#后向搜索初始化enqueue!(backward_queue,goal)push!(backward_visited,goal)#双向搜索主循环（注意空格）while!isempty(forward_queue)&&!isempty(backward_queue)#前向搜索扩展current_forward=dequeue!(forward_queue)forneighboringraph[current_forward]ifneighbor∉forward_visitedenqueue!(forward_queue,neighbor)push!(forward_visited,neighbor)#检查是否与后向搜索相遇ifneighborinbackward_visitedreturntrueendendend5.3双向搜索#后向搜索扩展current_backward=dequeue!(backward_queue)forneighboringraph[current_backward]ifneighbor∉backward_visitedenqueue!(backward_queue,neighbor)push!(backward_visited,neighbor)#检查是否与前向搜索相遇ifneighborinforward_visitedreturntrueendendendendreturnfalse#未找到路径end#示例图（需定义为无向图）graph=Dict{Int,Vector{Int}}(1=>[2,3],2=>[1,4,5],#节点2反向连接到13=>[1,6],#节点3反向连接到14=>[2],5=>[2],6=>[3]#节点6反向连接到3)#执行双向搜索result=bidirectional_search(graph,1,6)println("双向搜索结果:",result)#输出true程序运行实时输出代码执行后，控制台成功打印出双向搜索的相遇节点，直观验证了算法的可行性与正确性。正向搜索路径(Start->Mid)从起点节点1出发：

1→2→5→3→6(相遇点)反向搜索路径(End->Mid)从终点节点8出发：

8→4→7→3→6(相遇点)算法性能核心优势验证相比单向BFS需遍历至第4层才能找到目标，双向搜索在第2-3层即在节点6相遇，大幅减少了搜索空间与时间复杂度。5.3双向搜索结果分析城市物流网络与智能路径规划示意任务背景：物流核心挑战面对庞大的城市交通网络，从起点到终点的最短路径搜索往往耗时严重。双向搜索算法在该场景下具有显著优势，能同时从“起点”与“终点”双向推进，快速收敛找到最优配送路线。问题抽象：图论模型映射节点(Node)：代表城市、物流园区或关键交通枢纽。边(Edge)：代表连接两地的公路、高速，权重为通行耗时。5.3双向搜索5.3.3实例演示5.3双向搜索usingDataStructures#导入队列数据结构#物流配送交通图（邻接表表示）traffic_graph=Dict('S'=>['A','B','C'],'A'=>['S','D','E'],'B'=>['S','F','G'],'C'=>['S','H','I'],'D'=>['A'],'E'=>['A','J','K'],'F'=>['B'],'G'=>['B','L','M'],'H'=>['C'],'I'=>['C','N','O'],'J'=>['E'],'K'=>['E'],'L'=>['G'],'M'=>['G'],'N'=>['I'],'O'=>['I'])functionbidirectional_bfs(start,goal)#初始化前向和后向队列及访问记录forward_queue=Queue{Char}()backward_queue=Queue{Char}()forward_visited=Set{Char}()backward_visited=Set{Char}()#前向搜索初始化enqueue!(forward_queue,start)push!(forward_visited,start)#后向搜索初始化enqueue!(backward_queue,goal)push!(backward_visited,goal)#双向搜索主循环（注意空格）while!isempty(forward_queue)&&!isempty(backward_queue)#前向扩展current_forward=dequeue!(forward_queue)forneighborintraffic_graph[current_forward]ifneighbor∉forward_visited5.3双向搜索#检查是否相遇ifneighborinbackward_visitedreturntrueendenqueue!(forward_queue,neighbor)push!(forward_visited,neighbor)endend#后向扩展current_backward=dequeue!(backward_queue)forneighborintraffic_graph[current_backward]ifneighbor∉backward_visited#检查是否相遇ifneighborinforward_visitedreturntrueendenqueue!(backward_queue,neighbor)push!(backward_visited,neighbor)endendendreturnfalse#未找到路径end#执行双向搜索（注意：图中不存在'T'节点）println(bidirectional_bfs('S','T'))#输出false💡优势：相比单向搜索，双向搜索通过“会师”大幅减少了无效的路径探索，效率显著提升。图示：物流配送路线规划正确节点示例结果分析5.3双向搜索由于示例中没有'T'这个节点，且交通图中没有形成从'S'到'T'的路径，所以代码的运行结果是false，表示没有找到从起始点'S'到目标点'T'的路径。图示：物流配送路线规划错误节点示例若把输出改为println(bidirectional_bfs('S','I'))，示例中有'I'节点且交通图中存在从'S'到'I'的路径。此时输出true贪心搜索算法GreedySearchAlgorithm405.4贪心搜索5.4.1概念

贪心搜索在每一步都选择当前看起来最优的选项，而不考虑整体的最优解。贪心搜索的核心在于，面对问题时，它仅聚焦当下呈现的状态，果断选取该状态下最有利的选择。这种策略不考虑后续所有可能路径的综合影响，只图当下的最优，以一种较为“短视”的方式快速推进。虽不能确保最终得到全局最优解，但常常能快速得出一个较优的可行解，为问题求解节省大量时间与计算资源。5.4贪心搜索使用优先队列（堆）存储待访问节点。每次选择启发式函数值最小的节点扩展。重复直到找到目标节点。010203优先队列起始访问重复寻找核心思想非完备性(Incompleteness)不一定能找到解。非最优性(Non-optimality)可能找到次优解。时间复杂度取决于启发式函数。空间复杂度O(V)O(V)。5.4贪心搜索关键特点5.4贪心搜索操作原理

以经典的旅行推销员问题（TravelingSalesmanProblem，简称TSP）为例说明。假设推销员要遍历多个城市，每个城市只能访问一次，最后回到起始城市，目标是找出总路程最短的旅行路线。贪心搜索通常从起始城市出发，在每个当前城市，依据简单直观的判断规则：挑选距离当前城市最近且尚未访问过的城市作为下一站。如此循环，直至遍历完所有城市，最后返回起始城市，完成旅行路线规划。

不过要清楚，由于每一步只考虑当前最优，忽略了后续决策连锁反应，所以不一定能找到真正的全局最优路线。但在实际场景中，尤其是问题规模大、计算资源受限或对实时性要求高时，其快速得到较优解的特性就凸显出价值。5.4贪心搜索示意图以旅行推销员问题（TSP）为例，假设有5个城市（A、B、C、D、E），其距离矩阵如下：ABCDEA03586B30467C54039D86305E67950距离矩阵5.4贪心搜索示意图步骤当前城市已访问城市未访问城市可选下一站城市（距离当前城市最近且未访问）选择的下一站城市累计路程路径1A{A}{B,C,D,E}B（距离为3）B3[A,B]2B{A,B}{C,D,E}C（距离为4）C3+4=7[A,B,C]3C{A,B,C}{D,E}D（距离为3）D7+3=10[A,B,C,D]4D{A,B,C,D}{E}E（距离为5）E10+5=15[A,B,C,D,E]5E{A,B,C,D,E}{}-A（回到起始城市）15+6=21[A,B,C,D,E,A]5.4.2Julia实现贪心搜索算法实验核心目标算法实现掌握深入理解贪心搜索算法的核心思想与具体代码实现逻辑。启发式函数理解认识启发式函数在搜索过程中对节点选择优先级的重要性。局限性观察直观观察贪心策略的局限性，分析其可能导致无法找到全局最优解的典型场景。5.4贪心搜索5.4贪心搜索初始化当前状态。根据当前状态选择最优的下一步。更新状态。重复步骤2和3，直到达到目标或无法继续。算法步骤5.4贪心搜索usingDataStructuresfunctiongreedy_search(problem::Any,heuristic::Function)#初始化当前状态为问题的起始状态current_state=problem.start_state#创建一个路径列表，并将起始状态加入其中，将变量名改为search_pathsearch_path=[current_state]#只要未达到目标状态while!is_goal(current_state,problem)#生成当前状态的下一个可能状态next_states=generate_next_states(current_state,problem)#根据启发式函数选择最优的下一个状态的索引best_next_index=argmin([heuristic(s,problem)forsinnext_states])#通过索引获取最优的下一个状态current_state=next_states[best_next_index]#将新的当前状态加入路径列表push!(search_path,current_state)endreturnsearch_path#返回搜索路径end#示例问题和启发式函数structProblemstart_stategoal_stateendfunctionis_goal(state::Any,problem::Problem)#显式返回是否达到目标状态的布尔值returnstate==problem.goal_stateendfunctiongenerate_next_states(state::Any,problem::Problem)#简单示例：假设状态为整数，下一步状态是当前状态加1或减1return[state+1,state-1]endfunctionheuristic(state::Any,problem::Problem)5.4贪心搜索#简单示例：计算当前状态到目标状态的绝对距离作为启发值returnabs(state-problem.goal_state)end#定义一个示例问题problem=Problem(1,10)#进行贪心搜索search_path=greedy_search(problem,heuristic)println("贪心搜索路径:",search_path)5.4贪心搜索结果分析最优解达成逻辑在本实验中，启发式函数（绝对距离）完美引导了搜索方向，每次都精准选择了“+1”的下一步。这种理想情况下，贪心搜索能够高效地找到全局最优解。算法局限性思考若路径中存在障碍，或启发式函数不够精准，贪心搜索极易失败。这深刻体现了其“目光短浅”的特性——仅关注局部最优，缺乏对全局路径的长远规划能力。5.4.3实例演示5.4贪心搜索▍任务背景：云数据中心调度在云计算中心，调度器需将海量计算任务分配至不同服务器。目标是最小化总运行成本。贪心算法在此场景中应用广泛，核心策略为：“每次将任务分配给当前成本最低的可用服务器”。▍问题抽象模型计算任务(Task)

待执行的最小单元资源节点(Server)

执行任务的硬件载体成本矩阵(Cost)

cost[i][j]分配代价核心目标(Goal)

寻找方案使总成本最低贪心策略核心虽然无法保证全局最优，但通过“局部最优”的迭代选择，能够在海量数据下快速给出高效、低成本的近似解。5.4贪心搜索#定义成本矩阵：6个任务

×4个站点cost_matrix=[[8,12,9,10],#任务T1在站点S1、S2、S3、S4上的运行成本[7,10,11,9],#任务T2在站点S1、S2、S3、S4上的运行成本[10,9,13,11],#任务T3在站点S1、S2、S3、S4上的运行成本[9,11,10,12],#任务T4在站点S1、S2、S3、S4上的运行成本[11,13,12,10],#任务T5在站点S1、S2、S3、S4上的运行成本[12,10,11,13]#任务T6在站点S1、S2、S3、S4上的运行成本]定义了一个名为cost_matrix的二维数组。二维数组中的每一行代表一个任务（T1到T6），每一列代表一个站点（S1到S4）。每行对应一个任务，每列对应一个站点，例如，cost_matrix[1]=[8,12,9,10]表示任务T1在站点S1、S2、S3、S4上的运行成本分别为8、12、9、10。数组中的每个元素表示相应任务在相应站点上的运行成本。通过这种方式，可以方便地对不同任务在不同站点的成本进行存储和后续的计算与分析。5.4贪心搜索