基于随机游走的多目标A*算法的改进

• 作者: 刘浩翰 李建伏 贺怀清 郭晶晶
• 来源期刊: 计算机应用
• 学科: 工学
• 关键词: 最短路径 启发式搜索 多目标A*算法 高原搜索 蒙特卡罗随机游走
• 年，卷（期）: 2018,（1）
• 所属期刊栏目: 人工智能
• 页码范围: 116-119
• 页数: 4页
• 分类号: TP301|TP181
• 字数: 4115字
• 语种: 中文
• DOI: 10.11772/j.issn.1001-9081.2017071899

摘要

针对基于降维技术改进的多目标A*(NAMOAd*dr)算法中存在的高原搜索现象,结合蒙特卡罗随机游走策略提出了一种基于随机游走的多目标A*(RWNAMOAd*dr)算法,其基本思想是当NAMOAd*dr算法陷入高原搜索时,利用随机游走策略及时找到一个出口(具有被上次扩展标签的启发值非支配的启发值的标签)逃离该高原搜索.针对NAMOAdr算法何时陷入高原搜索的问题,提出了一种检测高原搜索的方法,即当连续扩展m次标签的启发值都被上一次扩展的标签的启发值支配时则认为NAMOAd算法陷入了高原搜索.使用多目标搜索算法的标准测试平台——随机网格进行了实验.实验结果表明RWNAMOAd*dr算法比NAMOAd*dr算法的运行时间平均减少了50.69％,占用的空间平均减少了约10％,能够为现实生活中加速多目标路径搜索提供理论支撑.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	贺怀清	中国民航大学计算机科学与技术学院	36	162	7.0	11.0
2	李建伏	中国民航大学计算机科学与技术学院	17	139	6.0	11.0
3	刘浩翰	中国民航大学计算机科学与技术学院	16	33	3.0	5.0
4	郭晶晶	中国民航大学计算机科学与技术学院	3	6	1.0	2.0