%0 Journal Article
%A 郭晶晶
%A 贺怀清
%A 李建伏
%A 刘浩翰
%T 基于随机游走的多目标A*算法的改进
%D 2018
%R 10.11772/j.issn.1001-9081.2017071899
%J 计算机应用
%P 116-119
%V 38
%N 1
%X 针对基于降维技术改进的多目标A*(NAMOAdr*)算法中存在的高原搜索现象,结合蒙特卡罗随机游走策略提出了一种基于随机游走的多目标A*(RWNAMOAdr*)算法,其基本思想是当NAMOAdr*算法陷入高原搜索时,利用随机游走策略及时找到一个出口(具有被上次扩展标签的启发值非支配的启发值的标签)逃离该高原搜索。针对NAMOAdr*算法何时陷入高原搜索的问题,提出了一种检测高原搜索的方法,即当连续扩展m次标签的启发值都被上一次扩展的标签的启发值支配时则认为NAMOAdr*算法陷入了高原搜索。使用多目标搜索算法的标准测试平台——随机网格进行了实验。实验结果表明RWNAMOAdr*算法比NAMOAdr*算法的运行时间平均减少了50.69%,占用的空间平均减少了约10%,能够为现实生活中加速多目标路径搜索提供理论支撑。
%U http://www.joca.cn/CN/10.11772/j.issn.1001-9081.2017071899