%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