Talk:Iterative deepening A*

Not actually IDA* at all?

I've seen IDA* pseudocode like this on a number of Google searches, but it doesn't even implement A*, it implements an iterative depth-first search algorithm that completely loses the advantages of A*. Additionally, I've found IDA* in two different textbooks and talked to a University Ph.D about it, and their accounts of IDA* are nothing like this.

Well, there are different implementations, but this one seems to be correct. IDA* only uses f = g + h from the A* algorithm. g stands for the costs of the current node (from the start node to the current one) plus an admissible heuristic h (e.g. the air-line distance).

Currently I'm taking part in a proseminar (graphalgorithms) where I had to implement A* and IDA* and I saw two approaches: the recursive (as here) and the iterative (like in the german Book "Algorithmische Graphentheorie" [algorithmic graph theory] from Volker Turau - page 277 http://books.google.de/books?id=HB0kxef_s10C&pg=PA277&lpg=PA277&dq=umkreissuche+a+star+algorithm&source=bl&ots=4zEFM9ikX5&sig=NTozIxw7gUicUZteTyYtk9abXZs&hl=de&sa=X&ei=8mQZT6n2J873sgaFqtlI&ved=0CEIQ6AEwBA#v=onepage&q&f=false -, http://www.amazon.de/Algorithmische-Graphentheorie-Volker-Turau/dp/3486200380). Both are correct whereas the iterative variant seems to be more error-prone. 87.164.245.29 (talk) —Preceding undated comment added 12:36, 20 January 2012 (UTC).

I have to share the concerns of the first poster, based on my understanding of IDA* from http://planning.cs.uiuc.edu/booka4.pdf , p. 39. If this code is IDA*, shouldn't the first node to be explored be the one with the lowest cost-so-far + estimated cost-to-go, as in A*? In addition, I'm pretty certain that if all edge costs are set to 1 but h(x) = 0 for all x, this code will not be able to find the solution if it is more than one edge away from the start state... this is clearly not what it should do, as h(x) = 0 is a perfectly admissible heuristic. Gzabers (talk) 22:11, 26 December 2012 (UTC)

I do not understand Python

Well, I do not understand Python..... --120.195.63.69 (talk) 11:57, 14 December 2009 (UTC)

Error on threshold calculation

I think there is an error in the pseudocode on how the new threshold is calculated (next_cost_limit).

In A Parallel Implementation of Iterative-Deepening-A* it says

For the first iteration, this threshold is the cost (f-value) of the initial state. For each new iteration, the threshold used is the minimum of all node costs that exceeded the (previous) threshold in the preceding iteration.

The python pseudocode of the article doesn't enforce this minimum and the algorithm might fail on some graphs due to this. I would therefore say that the line

next_cost_limit = min(next_cost_limit, new_cost_limit)

should be changed to

if new_cost_limit > cost_limit and new_cost_limit < next_cost_limit next_cost_limit = new_cost_limit —Preceding unsigned comment added by 83.76.247.10 (talk) 18:06, 17 December 2010 (UTC)

Original research ?

Unlike Dijkstra or A*, this algorithm is badly covered in the web search. The only relevant hit I found is http://intelligence.worldofcomputing.net/ai-search/iterative-deepening-a-star.html but it looks more like a blog post. Has it been properly published? Is it vital to put some serious reference. Audriusa (talk) 08:07, 30 March 2011 (UTC)

IDA* is covered in ISBN 0-13-604259-7, so it is certainly a "real" algorithm. As for web resources, I'm not sure. Cheezmeister (talk) 13:21, 10 April 2011 (UTC)

Any researcher in AI and Robotics knows and sometimes used this algorithm. It's a solid and serious research indeed. 193.145.56.241 (talk) 13:24, 2 October 2012 (UTC)

Algorithm Tests Out

I can vouch that this algorithm works. I independently tried to implement IDA* in Python, based on the description in Matt Ginsberg's book Essentials of Artificial Intelligence. That description is murkier than the one here. It doesn't use structured programming. I was having trouble getting my implementation to work on larger examples (searching to depth 10 in a space of size 36!). I used this code to help me debug, almost using it in its entirety by the time I got it to work. I'm not sure about the comment Error on Threshold Calculation above, however.

Rmkeller (talk) 00:29, 18 January 2013 (UTC)