人工智能中启发式搜索研究综述
发布时间：2021-03-02 06:04
启发式搜索（Heuristic Search,HS）是目前解决人工智能领域诸多问题的重要手段之一,在启发式搜索质量和效率评价相关定义的基础上,对目前几种典型启发式搜索算法原理进行分析,指出其优点及不足,并以人机大战为例提出启发式搜索的应用价值及未来研究方向。
【文章来源】：软件导刊. 2020,19(06)
【文章页数】：4 页
【部分图文】：
低估值的分支定界法
由现实生活经验可知，如果两条或多条路径到达同一节点，只需要存储距离消费最小的那条路径的距离即可。通过一个抽象处理后的实例对原理加以说明。若要求从S点城市前往D点城市，以下说明存储最短路径的分支定界法，如图3(a）-图3(f）所示。从S点出发，面临A、C两点选择，由于C点距离更短则选择C点，如图3(c）所示。到达C点后只能前往B点，此时距离S点距离为2，如图3(d）。同理继续前往E点，如图3(e），此时距离S点距离为4。接下来扩展距离比4更小的路径，即S→A→B（其实还有另一种走法S→A→C，基于后经过优先级更高的原则选择B点），此段距离到达B时距离S点为3，此时是第二次访问B点，于是依据最短路径原则选择到达B点最短的距离2，即保证存储了最短路径S→A→B。
上文对简单的分支定界法提出了两种优化策略，如果将两者优点结合起来就是A*算法[14]。下面将用经典的三数码问题[15]说明A*算法，假设采用的低估值为曼哈顿距离[16]，其中用到的算子[17]（简单理解，算子就是每一步的操作，具体一点也可理解为每一步的步骤）是空格上下左右4种方向的移动，具体实例如图4所示。在图4中，标注有*号的三数码块F(p)=2+4=6的原因说明：*号三数码块距离起点完成了两个算子操作，由此G(p)=2；与Goal相比，数字1至少向下移动1步可以到达Goal，同理数字2、3分别是2步和1步，因此步数相加为4步，即H*(p)=4。另外，*号数码块与起点数码块状态相同，因此通过比较存储最短距离对路径进行优化。
【参考文献】：
期刊论文
[1]双人博弈问题中的蒙特卡洛树搜索算法的改进[J]. 季辉,丁泽军. 计算机科学. 2018(01)
[2]一种改进的多目标人工蜂群算法[J]. 陈伟栋,童华刚,郜振华,张洪亮. 南华大学学报(自然科学版). 2017(02)
[3]八数码问题解法效率比较及改进研究[J]. 付宏杰,王雪莹,周健,周孙静,朱珠,张俊余. 软件导刊. 2016(09)
[4]基于改进A*算法的水下航行器自主搜索航迹规划[J]. 荣少巍. 电子科技. 2015(04)
[5]动态规划算法综述[J]. 张莹. 科技视界. 2014(28)
[6]基于改进粒子群算法的智能机器人路径规划[J]. 张万绪,张向兰,李莹. 计算机应用. 2014(02)
[7]基于分层的改进A算法在路径规划中的应用[J]. 钱红昇,葛文锋,钟鸣,葛铭. 计算机工程与应用. 2014(07)
[8]图规划框架下的启发式搜索的研究与发展[J]. 谷文祥,王改革,殷明浩,孙焱. 计算机科学. 2009(11)
[9]智能搜索中启发函数的选择及启发能力分析[J]. 许精明. 昆明理工大学学报(理工版). 2007(05)
[10]极小极大值理论的历史发展[J]. 尚宇红. 西北大学学报(自然科学版). 2003(02)
硕士论文
[1]基于单值变量的求解启发式方法研究[D]. 柳一君.吉林大学 2017
[2]基于图规划的智能小车的路径搜索应用研究[D]. 林尔敏.中山大学 2015
本文编号：3058750
【文章来源】：软件导刊. 2020,19(06)
【文章页数】：4 页
【部分图文】：
低估值的分支定界法
由现实生活经验可知，如果两条或多条路径到达同一节点，只需要存储距离消费最小的那条路径的距离即可。通过一个抽象处理后的实例对原理加以说明。若要求从S点城市前往D点城市，以下说明存储最短路径的分支定界法，如图3(a）-图3(f）所示。从S点出发，面临A、C两点选择，由于C点距离更短则选择C点，如图3(c）所示。到达C点后只能前往B点，此时距离S点距离为2，如图3(d）。同理继续前往E点，如图3(e），此时距离S点距离为4。接下来扩展距离比4更小的路径，即S→A→B（其实还有另一种走法S→A→C，基于后经过优先级更高的原则选择B点），此段距离到达B时距离S点为3，此时是第二次访问B点，于是依据最短路径原则选择到达B点最短的距离2，即保证存储了最短路径S→A→B。
上文对简单的分支定界法提出了两种优化策略，如果将两者优点结合起来就是A*算法[14]。下面将用经典的三数码问题[15]说明A*算法，假设采用的低估值为曼哈顿距离[16]，其中用到的算子[17]（简单理解，算子就是每一步的操作，具体一点也可理解为每一步的步骤）是空格上下左右4种方向的移动，具体实例如图4所示。在图4中，标注有*号的三数码块F(p)=2+4=6的原因说明：*号三数码块距离起点完成了两个算子操作，由此G(p)=2；与Goal相比，数字1至少向下移动1步可以到达Goal，同理数字2、3分别是2步和1步，因此步数相加为4步，即H*(p)=4。另外，*号数码块与起点数码块状态相同，因此通过比较存储最短距离对路径进行优化。
【参考文献】：
期刊论文
[1]双人博弈问题中的蒙特卡洛树搜索算法的改进[J]. 季辉,丁泽军. 计算机科学. 2018(01)
[2]一种改进的多目标人工蜂群算法[J]. 陈伟栋,童华刚,郜振华,张洪亮. 南华大学学报(自然科学版). 2017(02)
[3]八数码问题解法效率比较及改进研究[J]. 付宏杰,王雪莹,周健,周孙静,朱珠,张俊余. 软件导刊. 2016(09)
[4]基于改进A*算法的水下航行器自主搜索航迹规划[J]. 荣少巍. 电子科技. 2015(04)
[5]动态规划算法综述[J]. 张莹. 科技视界. 2014(28)
[6]基于改进粒子群算法的智能机器人路径规划[J]. 张万绪,张向兰,李莹. 计算机应用. 2014(02)
[7]基于分层的改进A算法在路径规划中的应用[J]. 钱红昇,葛文锋,钟鸣,葛铭. 计算机工程与应用. 2014(07)
[8]图规划框架下的启发式搜索的研究与发展[J]. 谷文祥,王改革,殷明浩,孙焱. 计算机科学. 2009(11)
[9]智能搜索中启发函数的选择及启发能力分析[J]. 许精明. 昆明理工大学学报(理工版). 2007(05)
[10]极小极大值理论的历史发展[J]. 尚宇红. 西北大学学报(自然科学版). 2003(02)
硕士论文
[1]基于单值变量的求解启发式方法研究[D]. 柳一君.吉林大学 2017
[2]基于图规划的智能小车的路径搜索应用研究[D]. 林尔敏.中山大学 2015
本文编号：3058750
本文链接：https://www.wllwen.com/kejilunwen/sousuoyinqinglunwen/3058750.html
