AI
寻路
203
AI
寻路
7-26:随机位置的搜索树对比
三种搜索都有可能需要检查指数级的状态,但由于
h
(
n
)
函数计算出的启发式信息
A*
搜索
将搜索最少的状态。
解决
n
2
1
个方块这样的问题不只有寻路这种方法。
Parberry
1995
)提出了一
种别出心裁的方法,使用分治思想。也就是说,给定一个
n
×
n
数码,
n
> 3
,首先完
成最左边的列和最上部的行,然后递归解决
(
n
1)
2
1
数码问题。当归结为一个
3
×
3
的问题,这 可以简单地使用穷举法来解决。这个方法保证能在
5
×
n
3
步内找到解。
7.11 参考文献
Barr, A. and E. Feigenbaum,
The Handbook of Arti cial Intelligence
. William Kaufmann,
Inc., 1981.
204
7
Berlekamp, E. and D. Wolfe,
Mathematical Go:
Chilling Gets the Last Point
. A K Peters/
CRC Press, 1994.
Botea, A., M. Müller, and J. Schaeffer,
Near optimal hierarchical path-finding,
Journal of
Game Development
, 1(1): 2004,
http://www.cs.ualberta.ca/
~
mmueller/ps/ hpastar.pdf
.
Hartmann, S.,
Project Scheduling Under Limited Resources: Models, Methods, and
Applications
. Springer, 1999.
Kaindl, H. and G. Kainz,
Bidirectional heuristic search reconsidered,
Journal of Arti cial
Intelligence Research
, 7: 283-317, 1997,
http://arxiv.org/pdf/cs/9712102.pdf.
Korf, R. E.,
Recent progress in the design and analysis of admissible heuristic func-tions,
Proceedings, Abstraction, Reformulation, and Approximation: 4th International Symposium
(SARA), Lecture notes in Computer Science #1864: 45
51, 2000,
http://www.aaai.org/
Papers/AAAI/2000/AAAI00-212.pdf
.
Laramee, F. D.,
Chess programming Part IV: Basic search,
GameDev.net, August 26,
2000,
http://www.gamedev.net/reference/articles/article1171.asp
.
Michalewicz, Z. and D. Fogel,
How to Solve It: Modern Heuristics
. Second Edition.
Springer, 2004.
Nilsson, N.,
Problem-Solving Methods in Articial Intelligence
. McGraw-Hill, 1971.
Parberry, I.,
A real-time algorithm for the (n2
1)-Puzzle,
Information Processing Letters
,
56(1):23
28, 1995,
http://dx.doi.org/10.1016/0020-0190(95)00134-X
.
Pearl, J.,
Heuristics: Intelligent Search Strategies for Computer Problem Solving
. Addison-
Wesley, 1984.
Pepicelli, G.,
Bitwise optimization in Java: Bitfields, bitboards, and beyond,
O
Reilly on
Java.com, February 2, 2005,
http://www.onjava.com/pub/a/onjava/ 2005/02/02/bitsets.html
.
Reinefeld, A.,
Complete solution of the 8-puzzle and the benefit of node ordering in IDA,
Proceedings of the 13th International Joint Conference on Artificial Intelli
gence (IJCAI),
Volume 1, 1993,
http://dl.acm.org/citation.cfm?id=1624060
.
Reinefeld, A. and T. Marsland,
Enhanced iterative-deepening search,
IEEE Trans
-
actions on Pattern Analysis and Machine Intelligence
, 16(7): 701–710, 1994,
http:// dx.doi.
org/10.1109/34.297950
.
AI
寻路
205
AI
寻路
Russell, S. J.,
Efficient memory-bounded search methods,
Proceedings, 10th Euro
pean
Conference on Artificial Intelligence (ECAI): 1–5, 1992.
Russell, S. J. and P. Norvig,
Artifcial Intelligence: A Modern Approach
. Third Edition.
Prentice Hall, 2009.
Samuel, A.,
Some studies in machine learning using the game of checkers,
IBM Journal
3(3): 210–229, 1967,
http://dx.doi.org/10.1147/rd.116.0601
.
Schaeffer, J.,
Game over: Black to play and draw in checkers,
Journal of the Interna
tional Computer Games Association
(ICGA),
https://ilk.uvt.nl/icga/journal/contents/ Schae
er07-01-08.pdf
.
Schaeffer, J., N. Burch, Y. Björnsson, A. Kishimoto, M. Müller, R. Lake, P. Lu, and S.
Sutphen,
Checkers is solved,
Science Magazine
, September 14, 2007, 317(5844): 1518–
1522,
http://www.sciencemag.org/cgi/content/abstract/317/5844/1518
.
Shannon, C.,
Programming a computer for playing chess,
Philosophical Magazine
,
41(314): 1950,
http://tinyurl.com/ChessShannon-pdf
.
Wichmann, D. and B. Wuensche,
Automated route finding on digital terrains,
Proceedings
of IVCNZ, Akaroa, New Zealand, pp. 107–112, November 2004,
https://www.researchgate.
net/publication/245571114_Automated_Route_Find ing_on_Digital_Terrains
.

Get 算法技术手册(原书第2 版) now with O’Reilly online learning.

O’Reilly members experience live online training, plus books, videos, and digital content from 200+ publishers.