搜索引擎优化论文(【知识点】代价树搜索的常用方法及算法介绍)

　　搜索引擎优化论文(【知识点】代价树搜索的常用方法及算法介绍)

　　摘要：代价树深度优先搜索算法是代价树搜索的常用方法之一，但在没有限制的情况下，可能会陷入死循环或大量无效搜索，搜索不完整，找到解决方案可能不是最佳解决方案 问题。针对深度优先搜索的不足，在搜索过程中设计了一定的剪枝条件，提高搜索效率，避免陷入死循环，尽量返回成本更低的方案。

　　关键词 : 成本树；搜索; 深度优先；

　　摘要：代价树的深度优先搜索算法是代价树搜索的常用方法之一。在没有约束的情况下可能陷入死循环或大量无效搜索。深度优先搜索可能不完整，解决方案可能不是最优的。针对深度优先搜索的不足，在搜索过程中设计了一些剪枝条件，以提高搜索效率，避免陷入死循环，返回较低的解。

　　关键字：成本树；搜索; 深度优先；

　　搜索是人工智能的重要研究内容之一，是指按照一定的条件和规则从当前状态搜索到目标状态的路径的过程，包括盲搜索和启发式搜索[1]。其中，盲搜索是指在搜索的每一步都按照既定的规则和策略进行搜索，而启发式搜索是指在搜索过程的每一步根据评价函数或一定的方法。搜索 [2]。

　　成本树是成本搜索树的缩写，是指在有向边上标有成本（或成本）的搜索树。代价树搜索与普通搜索的区别在于，在搜索过程中要考虑当前搜索路径的代价，选择代价较低的路径继续搜索[3]。

　　1.成本树深度优先搜索算法

　　1.1、算法介绍

　　代价树的深度优先搜索主要从根节点S0开始展开，从后续节点中选择代价最小的节点继续展开，以此类推，直到节点无法展开无解找到，并执行回溯。如果找到解决方案，则返回。

　　成本树深度优先搜索需要定义两个队列，OPEN队列代表未展开节点的队列，CLOSED队列代表展开节点的队列。

　　定义节点 jf(j)=f(i)+c(i,j) 的成本，其中 c(i,j) 表示边缘节点 i 到其后继节点 j 的成本。

　　算法流程如下。

　　(1)将节点S0放入OPEN表，CLOSED表为空。

　　(2)判断OPEN表是否为空，如果为空则返回，如果不为空，则从OPEN表的表头取出第一个节点n，放入CLOSED表中。

　　(3)判断节点n是否为目标节点，如果是则返回。

　　(4)判断节点n是否可伸缩，如果不是，返回步骤(2).

　　(5)如果节点n可以展开，则展开节点n，计算后续节点的代价并按升序添加到OPEN表的表头，返回步骤(2).

　　

　　1.2、 算法劣势分析

　　(1)算法在扩展节点时没有考虑后继节点是否已经出现在祖先节点中，可能会导致死循环。

　　(2)算法扩展一个节点，不考虑该节点是否是已经搜索到的无效节点。

　　（3)由于在执行复杂搜索时缺乏约束，算法可能会在未解决的路线上浪费大量时间。

　　(4)算法返回的搜索结果不一定是最优解。

　　2、 成本树深度优先搜索优化

　　2.1、 算法优化

　　针对代价树深度优先搜索的不足，对算法进行了相应的改进。

　　（1)深度优先搜索算法根据具体问题限制搜索层数，当搜索到指定层数时，认为无法展开。如果之后没有找到解搜索完成，增加限制层数。

　　(2)扩展节点n时判断是否出现在CLOSED表中，如果存在则丢弃节点n。

　　(3)扩展节点n时，判断OPEN表中是否出现对应的后继节点，如果存在，比较其cost，如果后继节点的cost低，则丢弃OPEN表中对应的节点，如果节点 n 的后继节点成本高，则丢弃相应的后继节点。

　　2.2、 改进算法应用分析

　　业务员出行问题，有A、B、C、D、E、F、G 7个城市。交通路线如图1所示。图中的数字代表所需的出行费用。业务员需要从A市到G市，如何寻找更便宜的路线？

　　图 1. 推销员差旅问题的路线图

　　

　　2.2.1、 深度优先搜索过程

　　根据深度优先搜索方法，遍历顺序如图2所示。

　　(1)首先从节点A展开，将节点B和节点C添加到OPEN表中，将节点A添加到CLOSED表中。

　　图2 深度优先搜索过程

　　

　　(2)选择成本较低的节点B展开，从OPEN表中取出节点B，将节点B添加到CLOSED表中，展开节点B，将节点C和节点E添加到OPEN表中。

　　(3)选择成本较低的节点C展开，从OPEN表中取出节点C，将节点C添加到CLOSED表，展开节点C，将节点E和节点D添加到OPEN表。

　　(4)选择成本较低的节点E展开，从OPEN表中取出节点E，将节点E添加到CLOSED表中，展开节点E。此时后继节点中的B就是节点成本最低，搜索将陷入无限循环。

　　2.2.2、改进深度优先搜索过程

　　由于城市数量较少，不需要通过设置层数来限制搜索深度。根据改进的深度优先搜索方法，遍历序列如图3所示。

　　图 3 改进的深度优先搜索过程

　　

　　(1)首先从节点A展开，将节点B和节点C添加到OPEN表中，将节点A添加到CLOSED表中。

　　(2)选择cost较低的节点B展开，从OPEN表中取出节点B，将节点B添加到CLOSED表中，展开节点B，因为OPEN表中已经存在节点C，而且原来的cost节点较小因此被丢弃，并将节点E添加到OPEN表中。

　　(3)选择节点E展开，从OPEN表中取出节点E，将节点E添加到CLOSED表，展开节点E，将节点F添加到OPEN表。

　　(4)选择节点F展开，从OPEN表中提取节点F并将节点F添加到CLOSED表中，展开节点F，节点F不能展开。

　　(5)选择节点C展开，从OPEN表中取出节点C并将节点C添加到CLOSED表中，展开节点C，将节点E和D添加到OPEN表中。

　　(6)选择节点E展开，因为节点E已经存在于CLOSED表中并且是无效节点，所以被丢弃。

　　(7)选择节点D展开，找到解，搜索结束。

　　三、结论

　　经验证推销员出行问题，改进后的算法避免了搜索陷入死循环，提高了搜索效率。但是，仍然存在一个问题，找到的解可能不是最优解，而且搜索到的解比普通的深度优先搜索要好。

　　参考

　　[1] 陆凯，唐涛，高春海。城域网乘客深度优先策略路径生成算法[J]. 可持续发展, 2020, 12(13):1-16.

　　[2]龚建华深度优先搜索算法及其改进[]现代电子技术2007(22):90-92.

　　[3]张建旭，姜艳，刘兴国基于深度优先反向搜索算法确定有效路径集[J]．重庆交通大学学报自然科学版2015,34(3):93-98.