`

【转】搜索算法基础教程 - Kangsheng的专栏 - CSDN博客

阅读更多

记录以待以后学习

搜索算法是利用计算机的高性能来有目的的穷举一个问题的部分或所有的可能情况,从而求出问题的解的一种方法。搜索过程实际上是根据初始条件和扩展规则构造一棵解答树并寻找符合目标状态的节点的过程。所有的搜索算法从其最终的算法实现上来看,都可以划分成两个部分──控制结构和产生系统,而所有的算法的优化和改进主要都是通过修改其控制结构来完成的。现在主要对其控制结构进行讨论,因此对其产生系统作如下约定:
Function ExpendNode(Situation:Tsituation;ExpendWayNo:Integer):TSituation;
表示对给出的节点状态Sitution采用第ExpendWayNo种扩展规则进行扩展,并且返回扩展后的状态。
(本文所采用的算法描述语言为类Pascal。)
一、回溯算法
回溯算法是所有搜索算法中最为基本的一种算法,其采用了一种“走不通就掉头”思想作为其控制结构,其相当于采用了先根遍历的方法来构造解答树,可用于找解或所有解以及最优解。具体的算法描述如下:
[非递归算法]<type> Node(节点类型)=Record Situtation:TSituation(当前节点状态); Way-NO:Integer(已使用过的扩展规则的数目); End<var> List(回溯表):Array[1..Max(最大深度)] of Node; pos(当前扩展节点编号):Integer;<init> ListWhile (pos&gt;0(有路可走)) and ([未达到目标]) doBegin If pos&gt;=Max then (数据溢出,跳出主程序); List[pos].Way-NO:=List[pos].Way-No+1; If (List[pos].Way-NO[递归算法]Procedure BackTrack(Situation:TSituation;deepth:Integer);Var I :Integer;Begin If deepth&gt;Max then (空间达到极限,跳出本过程); If Situation=Target then (找到目标); For I:=1 to TotalExpendMethod do Begin BackTrack(ExpendNode(Situation,I),deepth+1); End-For;End; <br>范例:一个M*M的棋盘上某一点上有一个马,要求寻找一条从这一点出发不重复的跳完棋盘上所有的点的路线。 <br>评价:回溯算法对空间的消耗较少,当其与分枝定界法一起使用时,对于所求解在解答树中层次较深的问题 有较好的效果。但应避免在后继节点可能与前继节点相同的问题中使用,以免产生循环。 <br>二、深度搜索与广度搜索 <br> 深度搜索与广度搜索的控制结构和产生系统很相似,唯一的区别在于对扩展节点选取上。由于其保留了所有的前继节点,所以在产生后继节点时可以去掉一部分重复的节点,从而提高了搜索效率。这两种算法每次都扩展一个节点的所有子节点,而不同的是,深度搜索下一次扩展的是本次扩展出来的子节点中的一个,而广度搜索扩展的则是本次扩展的节点的兄弟节点。在具体实现上为了提高效率,所以采用了不同的数据结构. <br>[广度搜索]<type> Node(节点类型)=Record Situtation:TSituation(当前节点状态); Level:Integer(当前节点深度); Last :Integer(父节点); End<var> List(节点表):Array[1..Max(最多节点数)] of Node(节点类型); open(总节点数):Integer; close(待扩展节点编号):Integer; New-S:TSituation;(新节点)<init> List While (close<open and do begin close:="close+1;" for i:="1" to totalexpendmethod new-s:="ExpendNode(List[close].Situation,I);" if not in list then open:="open+1;" end-if end-for end-while></open>[深度搜索]<var> Open:Array[1..Max] of Node;(待扩展节点表) Close:Array[1..Max] of Node;(已扩展节点表) openL,closeL:Integer;(表的长度) New-S:Tsituation;(新状态)<init> Open While (openL&gt;0) and (closeL<max and do begin closel:="closeL+1;" close openl:="openL-1;" for i:="1" to totalexpendmethod new-s:="ExpendNode(Close[closeL].Situation,I);" if not in list then open end-if end-for end></max>范例:迷宫问题,求解最短路径和可通路径。 <br>评价:广度搜索是求解最优解的一种较好的方法,在后面将会对其进行进一步的优化。而深度搜索多用于只 要求解,并且解答树中的重复节点较多并且重复较难判断时使用,但往往可以用分支定界或回溯算法代替。</init></var></init></var></type></init></var></type>

搜索算法基础教程 - Kangsheng的专栏 - CSDN博客

分享到:
评论

相关推荐

    分销商城tp5框架.zip

    文件kangsheng-master-575dfc04bb55877aec91f9bac9319ad1f10eef99可能是源代码仓库的某个特定版本,其中包含了商城的全部源代码。开发者可以通过解压后查看文件结构,了解各个模块的实现细节,包括控制器、模型、...

    基于net的超市管理系统源代码(完整前后端+sqlserver+说明文档+LW).zip

    功能说明: 环境说明: 开发软件:VS 2017 (版本2017以上即可,不能低于2017) 数据库:SqlServer2008r2(数据库版本无限制,都可以导入) 开发模式:mvc。。。

    LABVIEW程序实例-公式节点.zip

    labview程序代码参考学习使用,希望对你有所帮助。

    大米商城开源版damishop(适合外贸)

    大米外贸商城系统 简称damishop 完全开源版,只需做一种语言一键开启全球133中语言自动翻译功能,价格实现自动汇率转换,集成微信支付宝 paypal以及国外主流支付方式,自带文章博客系统。 软件架构 基于MVC+语言包模式,增加控制台,API导入产品方便对接其他系统(带json示例数据)。 使用要求 PHP7.4+ MYSQL5.6+ REDIS(可选) 安装方法 composer install 打开安装向导安装 http://您的域名/install 特色 1、缓存层增加时间与批量like删除 2、API产品导入方便对接其他系统 3、增加控制台命令行,命令行生成语言翻译包 4、后台一键开启自动翻译模式,支持全球133中语言,由于google代理翻译需要收费,这个功能需要付费。 5、可选购物车与ajax修改购物车产品 6、一键结算checkout 7、增加网站前台自定义路由 方便seo 更新日志 v3.9.7 集成鱼码支付接口,方便个人站长即使收款到账使用 v3.9.3 更新内容 1:增加ueditor与旧编辑器切换 2:增加可视化布局插

    LABVIEW程序实例-通过全局变量接收数据.zip

    labview程序代码参考学习使用,希望对你有所帮助。

    LABVIEW程序实例-日历控件.zip

    labview程序代码参考学习使用,希望对你有所帮助。

    毕设和企业适用springboot人工智能客服系统类及旅游规划平台源码+论文+视频.zip

    毕设和企业适用springboot人工智能客服系统类及旅游规划平台源码+论文+视频

Global site tag (gtag.js) - Google Analytics