Talk:A* search algorithm: Difference between revisions

Revision as of 14:50, 5 June 2007

Revision as of 15:32, 5 June 2007

Line 397:

:I'm familiar with the version of A* that you are, which requires monotonicity. I'm not familiar with the one in this article, but I'm told that the "open" and "closed" lists are used to avoid the situation that requires monotonicity (at the expense of taking longer to compute). Meanwhile, the paragraph I wrote on monotonicity was removed as [http://en.wikipedia.org/w/index.php?title=A%2A_search_algorithm&diff=44574419&oldid=44574042 "inaccurate"] by [[User:Qwertyus]]. Does anyone have a text that describes A* both with and without monotonicity which would help clarify this matter? [[User:Rspeer|'''<span style="color: #63f;">r</span><span style="color: #555;">speer</span>''']] / [[User talk:Rspeer|<span style="color: #555;">ɹəəds</span><span style="color: #63f;">ɹ </span>]] 03:08, 26 April 2007 (UTC)

IMHO if h is monotonous, then each node gets expanded at most once (and thus it's legitimate to rule out updating expanded nodes using the "closed" list) (and this means the algorithm is fast, too). If h is not monotonous, the same nodes get expanded multiple times and you need to consider all neighbors when expanding a node. It also means that the algorithm will be slower (since it repeatedly expands the same nodes). So as to react to your comment, it's a different story: If h is monotonous, then you MAY use the "closed" list to save (only a few) machine cycles (only saves you a few tests). If it isn't, you MUST NOT use the "closed" list. &mdash; Jiri Svoboda 19:26, 5 June 2007 (UTC)