5元可提现的电玩城

5元可提现的电玩城学报

? 工程技术 ? 上一篇

5元可提现的电玩城: 一种基于随机游走的A*算法

刘浩翰¹，郭晶晶¹，李建伏¹，冯梅²，贺怀清¹

（1.5元可提现的电玩城计算机科学与技术学院，天津300300；2.中国民用航空华北地区空中交通管理局，北京100621）

收稿日期:2017-02-23 修回日期:2017-03-27 出版日期:2017-12-27 发布日期:2017-12-15
作者简介:刘浩翰（1966—），男，黑龙江富锦人，副教授，硕士，研究方向为民航信息智能处理.
基金资助:
天津市应用基础与前沿技术研究计划重点项目（14JCZDJC32500）

5元可提现的电玩城: A* algorithm based on random walk

LIU Haohan¹, GUO Jingjing¹, LI Jianfu¹, FENG Mei², HE Huaiqing¹

(1. College of Computer Science and Technology, CAUC, Tianjin 300300, China;2. North Regional Air Traffic Management Bureau of CAAC, Beijing 100621, China)

Received:2017-02-23 Revised:2017-03-27 Online:2017-12-27 Published:2017-12-15

摘要/Abstract

摘要： 针对A*算法中出现的高原搜索现象，结合蒙特卡罗随机游走思想提出了一种基于随机游走的A*算法。其基本思想是当A*算法陷入高原搜索期时，通过随机游走策略及时找到一个节点逃离该高原搜索期。针对A*算法何时陷入高原搜索期的问题提出了一种新的检测高原搜索期的方法，即当连续扩展n 次节点的启发值都比上一次最后扩展出节点的启发值大时，则认为搜索陷入了高原搜索期。实验结果验证了该方法的有效性。

关键词: 最短路径, 启发式搜索, A*算法, 高原搜索, 蒙特卡罗随机游走

Abstract: A* algorithm based on random walk combining with Monte-Carlo random walk is proposed to solve the plateau exploration in A* algorithm. When the A* algorithm falls into the plateau exploration, a random walk algorithm is employed to help it escape from the plateaus. In addition, a new method is proposed to test plateau exploration.The phenomenon is named plateau exploration as it continuously expand states n times without reducing the heuristic value compared with last states'expanded on last expansion. Experimental results prove the effectiveness of the improved A* algorithm.

Key words: shortest path, heuristic search, A* algorithm, plateau exploration, Monte-Carlo random walk

中图分类号:

TP301

刘浩翰，郭晶晶，李建伏，冯梅，贺怀清. 一种基于随机游走的A*算法[J]. 5元可提现的电玩城学报.

LIU Haohan, GUO Jingjing, LI Jianfu, FENG Mei, HE Huaiqing. A* algorithm based on random walk[J]. .

参考文献

[1] 胡欣, 徐涛,丁晓璐,等.国际航线网络中K条最短路径算法改进与仿真[J].计算机应用, 2014, 34(4): 1192-1195.
[2] DECHTER R, PEARL J. Generalized best-first search strategies and the optimality of A* [J]. Journal of the ACM, 1985, 32(3): 505-536.
[3] 吕强.面向高性能和表达力的自动规划[D].合肥:中国科学技术大学, 2012.
[4] HELMERT M, ROGER G. How Good is Almost Perpect[C]//Proceedings of the AAAI Conference on Artificial Intelligence, 2008: 944-949.
[5] HAMPSON S, KIBLER D. Plateaus and Plateau Search in Boolean Satisfiability Problems: When to Give Up Searching and Start Again[C]//In the 2nd DIMACS Implementation Challenge, 1993: 437-456.
[6] FRANK J D, CHEESEMAN P, STUTZ J. When gravity fails: local search topology[J]. Journal of Artificial Intelligence Research, 1997(12):249-281.
[7] HOFFMANN J. Local Search Topology in Planning Benchmarks: An Empirical Analysis[C]//Proceedings of the International Joint Conference on Artificial Intelligence, 2001: 453-458.
[8] HOFFMANN J. Local Search Topology in Planning Benchmarks: A Theoretical Analysis[C]//Proceedings of the International Conference on AI Planning and Scheduling, 2002: 92-100.
[9] BENTONJ, TALAMADUPULAK,EYERICHP, et al.G-ValuePlateaus:Challenge for Planning[C]//Proceedings of the International Conference on Automated Planning and Scheduling, 2010: 259-262.
[10] GOVER F, LAGUNA M. Tabu Search[M]. Boston: Kluwer Academic Publishers, 1997.
[11] KAUTZ H, SEMAN B. Pushing the Envelope: Planning, Propositional Logic and Stochastic Search[C]//Proceedings of the AAAI Coference on Aritifical Intelligence, 1996: 1194-1201.
[12] NAKHOST H, MSLLER M. Monte-Carlo Exploration for Deterministic Planning[C]//IJCAI, 2009: 1766-1771.
[13] NAKHOSTH, HOFFMANNJ,MULLERM. ResourceConstrainedPlanning:A Monte Carlo Random Walk Approach [C]//Proceedings of the Twenty-Second International Conference on Automated Planning and Scheduling (ICAPS-2012), 2012: 181-189.
[14] LU Qiang, XU You, HUANG Ruoyun, et al. The Roamer Planner Random-Walk Assisted Best-First Search[C]//The 2011 International Planning Competition, 2011: 73-76.
[15] NAKHOST H, MULLER M, VALENZANO R, et al. Arvand: The Art of RandomWalks[C]//The 2011 International Planning Competition, 2011:15-16.

相关文章 1

编辑推荐

Metrics

本文评价

5元可提现的电玩城-搜狗指南

<tfoot id='QrtB'></tfoot>

<legend id='ZnQzE'><style id='H2JXK'><dir id='IkGdi'><q id='neA5fR'></q></dir></style></legend>

<i id='Cp5ys0'><tr id='nsQjj0'><dt id='548lI'><q id='mad3'><span id='YSngw'><b id='9bG1'><form id='P8Elvj'><ins id='f6JM'></ins><ul id='IMWaCvQ'></ul><sub id='HwjS8'></sub></form><legend id='iafhed'></legend><bdo id='kjK9l'><pre id='CdxT2'><center id='fy6Z'></center></pre></bdo></b><th id='EMuTD'></th></span></q></dt></tr></i><div id='P02Jhh'><tfoot id='Dg1VXj'></tfoot><dl id='6rLYo'><fieldset id='500KVBi6'></fieldset></dl></div>

<sup id='Qn5Le'><pre id='8CcmsqZ'></pre></sup><em id='RoIrtbo'></em>

<li id='xrwZ3'><abbr id='q8DbkDwP'></abbr></li>