`

【转】搜索算法基础教程 - 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可能是源代码仓库的某个特定版本,其中包含了商城的全部源代码。开发者可以通过解压后查看文件结构,了解各个模块的实现细节,包括控制器、模型、...

    NX二次开发-属性操作(创建与编辑)

    目前关于属性操作的创建于编辑主要有新旧两个版本,旧版本主要使用UF_ATTR_assign()函数,新版本主要使用UF_ATTR_set_user_attribute()函数。注意在使用新版本是需要初始化。

    编书 机械制图习题集(属性块图框)出版社.dwg

    编书 机械制图习题集(属性块图框)出版社.dwg

    毕业设计物联网实战项目基于 ESP8266 及 1.3 寸 TFT 实现的华为太空人时钟.zip

    【项目资源】: 物联网项目适用于从基础到高级的各种项目,特别是在性能要求较高的场景中,比如操作系统开发、嵌入式编程和底层系统编程。如果您是初学者,可以从简单的控制台程序开始练习;如果是进阶开发者,可以尝试涉及硬件或网络的项目。 【项目质量】: 所有源码都经过严格测试,可以直接运行。 功能在确认正常工作后才上传。 【适用人群】: 适用于希望学习不同技术领域的小白或进阶学习者。 可作为毕设项目、课程设计、大作业、工程实训或初期项目立项。 【附加价值】: 项目具有较高的学习借鉴价值,也可直接拿来修改复刻。 对于有一定基础或热衷于研究的人来说,可以在这些基础代码上进行修改和扩展,实现其他功能。 【沟通交流】: 有任何使用上的问题,欢迎随时与博主沟通,博主会及时解答。 鼓励下载和使用,并欢迎大家互相学习,共同进步。 # 注意 1. 本资源仅用于开源学习和技术交流。不可商用等,一切后果由使用者承担。 2. 部分字体以及插图等来自网络,若是侵权请联系删除。

    【机器人控制】基于MATLAB的不同神经网络控制器性能对比:机器人手臂模型的NNPC、MRC和NARMA-L2控制策略分析(复现论文或解答问题,含详细可运行代码及解释)

    内容概要:本文档提供了三种神经网络控制器(NNPC、MRC和NARMA-L2)在机器人手臂模型上性能比较的MATLAB实现代码及详细解释。首先初始化工作空间并设定仿真参数,包括仿真时间和采样时间等。接着定义了机器人手臂的二阶动力学模型参数,并将其转换为离散时间系统。对于参考信号,可以选择方波或正弦波形式。然后分别实现了三种控制器的具体算法:MRC通过定义参考模型参数并训练神经网络来实现控制;NNPC利用预测模型神经网络并结合优化算法求解控制序列;NARMA-L2则通过两个神经网络分别建模f和g函数,进而实现控制律。最后,对三种控制器进行了性能比较,包括计算均方根误差、最大误差、调节时间等指标,并绘制了响应曲线和跟踪误差曲线。此外,还强调了机器人手臂模型参数的一致性和参考信号设置的规范性,提出了常见问题的解决方案以及性能比较的标准化方法。 适合人群:具备一定编程基础,特别是熟悉MATLAB编程语言的研究人员或工程师,以及对神经网络控制理论有一定了解的技术人员。 使用场景及目标:①理解不同类型的神经网络控制器的工作原理;②掌握在MATLAB中实现这些控制器的方法;③学会如何设置合理的参考信号并保证模型参数的一致性;④能够根据具体的性能指标对比不同控制器的效果,从而选择最适合应用场景的控制器。 其他说明:本文档不仅提供了完整的实验代码,还对每个步骤进行了详细的注释,有助于读者更好地理解每段代码的功能。同时,针对可能出现的问题给出了相应的解决办法,确保实验结果的有效性和可靠性。为了使性能比较更加公平合理,文档还介绍了标准化的测试流程和评估标准,这对于进一步研究和应用具有重要的指导意义。

    《基于YOLOv8的雪场设备识别系统》(包含源码、完整数据集、可视化界面、部署教程)简单部署即可运行。功能完善、操作简单,适合毕设或课程设计.zip

    资源内项目源码是来自个人的毕业设计,代码都测试ok,包含源码、数据集、可视化页面和部署说明,可产生核心指标曲线图、混淆矩阵、F1分数曲线、精确率-召回率曲线、验证集预测结果、标签分布图。都是运行成功后才上传资源,毕设答辩评审绝对信服的保底85分以上,放心下载使用,拿来就能用。包含源码、数据集、可视化页面和部署说明一站式服务,拿来就能用的绝对好资源!!! 项目备注 1、该资源内项目代码都经过测试运行成功,功能ok的情况下才上传的,请放心下载使用! 2、本项目适合计算机相关专业(如计科、人工智能、通信工程、自动化、电子信息等)的在校学生、老师或者企业员工下载学习,也适合小白学习进阶,当然也可作为毕设项目、课程设计、大作业、项目初期立项演示等。 3、如果基础还行,也可在此代码基础上进行修改,以实现其他功能,也可用于毕设、课设、作业等。 下载后请首先打开README.txt文件,仅供学习参考, 切勿用于商业用途。

    (源码)基于Python的微信智能聊天机器人.zip

    # 基于Python的微信智能聊天机器人 ## 项目简介 本项目是一个基于Python的微信智能聊天机器人框架,旨在通过ChatGPT的强大对话能力,将微信打造成一个智能助手。该机器人支持私聊和群聊的智能回复、语音识别、图片生成、插件扩展等功能,能够与好友进行多轮对话,并提供丰富的交互体验。项目支持多端部署,包括个人微信、微信公众号和企业微信应用。 ## 项目的主要特性和功能 多端部署支持个人微信、微信公众号和企业微信应用等多种部署方式。 智能对话支持私聊和群聊的智能回复,具备多轮会话上下文记忆功能,支持GPT3、GPT3.5、GPT4等模型。 语音识别可识别语音消息并通过文字或语音回复,支持Azure、Baidu、Google、OpenAI等多种语音模型。 图片生成支持图片生成和图生图功能(如照片修复),可选择DALLE、Stable Diffusion、Replicate等模型。

    Android毕设实战项目基于Android的健身信息管理系统.zip

    【项目资源】: 适用于从基础到高级的各种项目,特别是在性能要求较高的场景中,比如操作系统开发、嵌入式编程和底层系统编程。如果您是初学者,可以从简单的控制台程序开始练习;如果是进阶开发者,可以尝试涉及硬件或网络的项目。 【项目质量】: 所有源码都经过严格测试,可以直接运行。 功能在确认正常工作后才上传。 【适用人群】: 适用于希望学习不同技术领域的小白或进阶学习者。 可作为毕设项目、课程设计、大作业、工程实训或初期项目立项。 【附加价值】: 项目具有较高的学习借鉴价值,也可直接拿来修改复刻。 对于有一定基础或热衷于研究的人来说,可以在这些基础代码上进行修改和扩展,实现其他功能。 【沟通交流】: 有任何使用上的问题,欢迎随时与博主沟通,博主会及时解答。 鼓励下载和使用,并欢迎大家互相学习,共同进步。 # 注意 1. 本资源仅用于开源学习和技术交流。不可商用等,一切后果由使用者承担。 2. 部分字体以及插图等来自网络,若是侵权请联系删除。

    《基于YOLOv8的医疗废物分类系统》(包含源码、完整数据集、可视化界面、部署教程)简单部署即可运行。功能完善、操作简单,适合毕设或课程设计.zip

    资源内项目源码是来自个人的毕业设计,代码都测试ok,包含源码、数据集、可视化页面和部署说明,可产生核心指标曲线图、混淆矩阵、F1分数曲线、精确率-召回率曲线、验证集预测结果、标签分布图。都是运行成功后才上传资源,毕设答辩评审绝对信服的保底85分以上,放心下载使用,拿来就能用。包含源码、数据集、可视化页面和部署说明一站式服务,拿来就能用的绝对好资源!!! 项目备注 1、该资源内项目代码都经过测试运行成功,功能ok的情况下才上传的,请放心下载使用! 2、本项目适合计算机相关专业(如计科、人工智能、通信工程、自动化、电子信息等)的在校学生、老师或者企业员工下载学习,也适合小白学习进阶,当然也可作为毕设项目、课程设计、大作业、项目初期立项演示等。 3、如果基础还行,也可在此代码基础上进行修改,以实现其他功能,也可用于毕设、课设、作业等。 下载后请首先打开README.txt文件,仅供学习参考, 切勿用于商业用途。

    毕业设计物联网实战项目基于腾讯云物联网开发平台的智能台灯,全套腾讯解决方案,可使用微信小程序远程控制.zip

    【项目资源】: 物联网项目适用于从基础到高级的各种项目,特别是在性能要求较高的场景中,比如操作系统开发、嵌入式编程和底层系统编程。如果您是初学者,可以从简单的控制台程序开始练习;如果是进阶开发者,可以尝试涉及硬件或网络的项目。 【项目质量】: 所有源码都经过严格测试,可以直接运行。 功能在确认正常工作后才上传。 【适用人群】: 适用于希望学习不同技术领域的小白或进阶学习者。 可作为毕设项目、课程设计、大作业、工程实训或初期项目立项。 【附加价值】: 项目具有较高的学习借鉴价值,也可直接拿来修改复刻。 对于有一定基础或热衷于研究的人来说,可以在这些基础代码上进行修改和扩展,实现其他功能。 【沟通交流】: 有任何使用上的问题,欢迎随时与博主沟通,博主会及时解答。 鼓励下载和使用,并欢迎大家互相学习,共同进步。 # 注意 1. 本资源仅用于开源学习和技术交流。不可商用等,一切后果由使用者承担。 2. 部分字体以及插图等来自网络,若是侵权请联系删除。

    scipy-0.11.0.tar.gz

    该资源为scipy-0.11.0.tar.gz,欢迎下载使用哦!

    【机械故障仿真】PT500PLUS平行轴齿轮箱故障测试台Machine Vibration & Gearbox Simulator(机械振动-齿轮箱模拟器):转子及齿轮传动故障模拟与数据采集系统设计

    内容概要:PT500PLUS平行轴齿轮箱故障测试台是由瓦伦尼安(VALENIAN)Machine Vibration & Gearbox Simulator(机械振动-齿轮箱模拟器)开发的专业机械故障仿真测试设备。该测试台旨在模拟和研究转子、齿轮传动、轴承及电机系统中的多种常见故障,包括但不限于轴不对中、转子不平衡、机械松动、轴承故障、齿轮故障(如点蚀、磨损、断齿等)以及电机故障(如转子不平衡、轴承故障、匝间短路等)。测试台配备有先进的传感器和数据采集系统,能够实时采集并分析振动、噪声、转速、扭矩等参数,提供多通道同步信号采集与频谱分析功能。此外,测试台还配备了10寸触摸屏、PLC智能控制系统和急停按钮,确保操作简便和安全。 适用人群:机械工程专业师生、科研人员以及从事机械故障诊断和维护的技术人员。 使用场景及目标:①用于高校和科研机构的教学和研究,帮助学生和研究人员深入理解机械故障的机理;②为企业提供故障诊断和预防性维护的解决方案,提高设备可靠性和运行效率;③通过模拟真实工况下的故障,进行轴承寿命预测性试验,研究轴承故障机制与轴承载荷、转速、振动、温度之间的关系。 其他说明:测试台结构紧凑,模块化设计,便于移动和维护。它不仅支持多种传感器的安装和数据采集,还提供了丰富的分析软件功能,如FFT频谱分析、轴心轨迹图、小波分析等,支持数据导出和二次开发,适用于各种复杂的研究和应用需求。

    ### 【5G智慧文旅】商业街、水街信息集成方案:5G技术赋能全方位智慧化升级与游客体验优化

    内容概要:本文档详细介绍了XXX5G特色商业街的规划设计方案,旨在通过5G技术与物联网等前沿科技的融合,全方位提升游客体验感和街区运营效率。首先,基础信息系统涵盖综合管理智慧平台、统一结算系统、5G视频智慧安防监控系统等多个子系统,实现多系统协同管理和数据安全保障。其次,特色应用方面,推出5G短信服务、5G智慧机器人、5G无人巡逻车、5G+XR时空走廊、5G+元宇宙体验馆等项目,将尖端科技与深厚文化底蕴巧妙结合,创新文旅体验形式。最后,通过5G高清视频直播与分享、5G+高空文旅等举措,进一步提升水街的影响力和吸引力。 适用人群:本方案适用于文旅项目规划者、商业街运营管理者、信息技术从业者以及对智慧城市建设感兴趣的各界人士。 使用场景及目标:①为商业街提供全面的智慧化升级方案,涵盖基础信息系统和特色应用两大部分;②通过5G技术赋能,实现高效运营管理和沉浸式游客体验;③推动文旅产业创新发展,促进地方经济繁荣和社会进步。 其他说明:该方案不仅关注技术实现,更重视用户体验和服务质量,强调文化传承与科技创新的有机结合,致力于打造具有国际影响力的智慧文旅新地标。

    【更新至2023年】2000-2023年中国气候政策不确定性指数(全国、省、市三个层面)

    【更新至2023年】2000-2023年中国气候政策不确定性指数数据(全国、省、市三个层面) 1.时间:2000-2023年 2.来源:使用人工审计和深度学习算法MacBERT模型,基于中国《人民日报》《光明日报》《经济日报》《环球时报》《科技日报》《中国新闻社》等6家主流报纸中的1,755,826篇文章,构建了2000年1月至2023年12月的中国全国、省份和主要城市层面的CCPU指数。研究框架包括六个部分:数据收集、清洗数据、人工审计、模型构建、指数计算与标准化以及技术验证。 3.范围:中国、省、市三个层次 4.参考文献:Ma, Y. R., Liu, Z., Ma, D., Zhai, P., Guo, K., Zhang, D., & Ji, Q. (2023). A news-based climate policy uncertainty index for China. Scientific Data, 10(1), 881. 5.时间跨度:全国层面:日度、月度、年度;省级层面:月度、年度;地级市层面:月度、年度

    毕设单片机实战项目基于STM32F401和ESP8266的硬件开源物连网平台.zip

    【项目资源】: 单片机项目适用于从基础到高级的各种项目,特别是在性能要求较高的场景中,比如操作系统开发、嵌入式编程和底层系统编程。如果您是初学者,可以从简单的控制台程序开始练习;如果是进阶开发者,可以尝试涉及硬件或网络的项目。 【项目质量】: 所有源码都经过严格测试,可以直接运行。 功能在确认正常工作后才上传。 【适用人群】: 适用于希望学习不同技术领域的小白或进阶学习者。 可作为毕设项目、课程设计、大作业、工程实训或初期项目立项。 【附加价值】: 项目具有较高的学习借鉴价值,也可直接拿来修改复刻。 对于有一定基础或热衷于研究的人来说,可以在这些基础代码上进行修改和扩展,实现其他功能。 【沟通交流】: 有任何使用上的问题,欢迎随时与博主沟通,博主会及时解答。 鼓励下载和使用,并欢迎大家互相学习,共同进步。 # 注意 1. 本资源仅用于开源学习和技术交流。不可商用等,一切后果由使用者承担。 2. 部分字体以及插图等来自网络,若是侵权请联系删除。

    机械工程BTS200轴承寿命预测测试台Bearing Prognostics Simulator:多功能加载与润滑系统设计及应用反映了文档的核心内容

    内容概要:BTS200轴承寿命预测测试台是一款专为研究轴承寿命预测及加速磨损过程设计的实验设备。该设备结构灵活,支持不同尺寸和类型的轴承测试,最大负载可达15000N。测试台采用先进的伺服电缸加载系统,能够在轴向和径向上精确施加载荷,并配备高精度测力传感器和温度监测系统,确保实验数据的准确性。此外,BTS200还拥有油液循环润滑系统,通过油膜减少摩擦和磨损,保持机械部件在适宜的工作温度范围内,延长轴承寿命。Bearing Prognostics Simulator(实验台可通过触控屏操作,支持多速运行(0-3000RPM),并具备过热保护机制,在温度超过150℃时自动停机。BTS200广泛应用于轴承寿命预测、故障机制研究以及剩余寿命预测模型的开发。 适合人群:轴承设计研发人员、机械工程研究人员、高校实验室师生及相关领域工程师。 使用场景及目标:①研究轴承在不同载荷和转速条件下的磨损特性;②开发和验证轴承剩余寿命预测模型;③探索轴承故障机制及其对系统性能的影响;④评估不同润滑方式对轴承寿命的影响。 其他说明:BTS200测试台不仅提供硬件支持,还配备了完整的软件控制系统,包括PLC闭环控制、温度监测反馈模块等,确保实验过程的稳定性和数据的可靠性。此外,设备支持快速安装和拆卸测试轴承,便于实验操作。

    AXI Memory Mapped to PCI Express (PCIe) Gen2 v2.9

    xilinx基于PCIE IP的PCIE Bridge IP操作手册

    毕设单片机实战项目基于 STM32F407+ESP8266+RFID 的模拟公交车刷卡收费系统(物联网版).zip

    【项目资源】: 单片机项目适用于从基础到高级的各种项目,特别是在性能要求较高的场景中,比如操作系统开发、嵌入式编程和底层系统编程。如果您是初学者,可以从简单的控制台程序开始练习;如果是进阶开发者,可以尝试涉及硬件或网络的项目。 【项目质量】: 所有源码都经过严格测试,可以直接运行。 功能在确认正常工作后才上传。 【适用人群】: 适用于希望学习不同技术领域的小白或进阶学习者。 可作为毕设项目、课程设计、大作业、工程实训或初期项目立项。 【附加价值】: 项目具有较高的学习借鉴价值,也可直接拿来修改复刻。 对于有一定基础或热衷于研究的人来说,可以在这些基础代码上进行修改和扩展,实现其他功能。 【沟通交流】: 有任何使用上的问题,欢迎随时与博主沟通,博主会及时解答。 鼓励下载和使用,并欢迎大家互相学习,共同进步。 # 注意 1. 本资源仅用于开源学习和技术交流。不可商用等,一切后果由使用者承担。 2. 部分字体以及插图等来自网络,若是侵权请联系删除。

    使用教程 (1).mov

    使用教程 (1).mov

    (源码)基于webpack和Vue的前端项目构建方案.zip

    # 基于webpack和Vue的前端项目构建方案 ## 项目简介 本项目是基于webpack和Vue构建的前端项目方案,借助webpack强大的打包能力以及Vue的开发特性,可用于快速搭建现代化的前端应用。项目不仅完成了基本的webpack与Vue的集成配置,还在构建速度优化和代码规范性方面做了诸多配置。 ## 项目的主要特性和功能 1. 打包功能运用webpack进行模块打包,支持将scss转换为css,借助babel实现语法转换。 2. Vue开发支持集成Vue框架,能使用Vue单文件组件的开发模式。 3. 构建优化采用threadloader实现多进程打包,cacheloader缓存资源,极大提高构建速度开启热更新功能,开发更高效。 4. 错误处理与优化提供不同环境下的错误映射配置,便于定位错误利用webpackbundleanalyzer分析打包体积。

Global site tag (gtag.js) - Google Analytics