Algorithm 版 (精华区)

发信人: sino (茶水), 信区: Algorithm
标  题: A* References 
发信站: 哈工大紫丁香 (2002年08月29日00:52:05 星期四), 站内信件

发信人: jamguo (卜卜熊的耙耙兔), 信区: Algorithm
标  题: A* References
发信站: 日月光华 (2002年08月03日07:54:38 星期六), 站内信件

From: cd000450@interramp.com (Bryan Stout)
Newsgroups: rec.games.programmer
Subject: Re: Shortest path algorithm?
Date: 27 Feb 1996 02:32:33 GMT

kathi@lightside.com says...
Many times I have seen people ask here about a shortest path algorithm... th
e answer is almost always "Look in a good algorithm's book." Can anyone reco
mmend such a book?
My problem is that I am trying to find paths on a 640x480 grid... with any o
f the algorithms I've seen so far, the worst-case scenarios would take treme
ndous amount of memory to store the tree...
--
Katherine Lynne
kathi@lightside.com

From my own experience, I would absolutely say the algorithm to try is the A
* (pronounced "A-star") algorithm. This is described in most good introducto
ry Artificial Intelligence textbooks. If you want a specific reference, try
the Encyclopedia of Artificial Intelligence, Stuart C. Shapiro, ed. (see art
icles on "Search" and "A* Search"); The Handbook of Artificial Intelligence,
 vol. 1, Barr and Feigenbaum, eds. (chapter 2 is on search); Principles of A
rtificial Intelligence, Nils J. Nilsson (a bit dated, but good discussion of
 A*).
If your domain is not hard to maneuver around, A* should take up *much* less
 memory than Dijkstra's algorithm, say. If your heuristic estimate function
is on the average not very close to the true remaining cost of the path, the
n A* ends up being close to a full breadth-first search. If you memory probl
ems, options you have include: a) trying a higher estimate function, even on
e which sometimes overestimates the distance; b) beam search (limit the size
 of the Open list, discarding the worst entry when it's full); c) try the it
erative-deepening A* search (IDA*); d) use more efficient data structures fo
r the Open and Closed lists. The Encyclopedia mentioned above discusses the
beam search and IDA*; Sedgewick's Algorithms in C++ has a good discussion of
 various data structures for representing priority queues, and their tradeof
fs. (Although, oddly enough, he does not mention the possible use of balance
d search trees for a priority queue, though he has a chapter about them else
where; I would probably try using height-balanced trees (aka AVL trees), as
discussed in Reingold et al's Combinatorial Algorithms.)
There, I've just given you a preview of my talk at the Computer Game Develop
ers' Conference!

Bryan Stout
bstout@interramp.com


--
宁叫我负天下人，
    不叫天下人负我

--
    我一直认为马佩军是西电编程第一高手，他编程的时候根本不是人，是指针。

                                             --《阳光男孩之大学十年》

※ 来源:·哈工大紫丁香 bbs.hit.edu.cn·[FROM: 202.118.229.154]