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. 74.140.141.209 (talk) 03:13, 17 September 2011‎ (UTC)

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)

This code is indeed broken. It can find a solution state but there's no guarantee the solution found is optimal. A simple but slow fix would be to sort branches by ascending cost when expending (e.g. "for s in successors(node) sorted by h(node)"). A much faster fix (which I believe is correct) is to collect each solution state after exploring each child branch and then return the discovered solution (if any) with the lowest cost. Jackcanty (talk) 08:37, 22 January 2013 (UTC)

I've fixed the pseudocode so an optimal solution is now guaranteed to be found. Jackcanty (talk) 09:01, 22 January 2013 (UTC)

It's not clear to me what new_start_cost is doing. Its passed as an argument to the recursive call, but doesn't appear in the function signature. 137.186.44.205 (talk) 22:54, 6 April 2013 (UTC)

I think the article is just a bit confusing. It gives you the impression that IDA* is more closely related to the A* search algorithm, while in reality it is a iterative deepening depth-first search algorithm that only borrows the idea to use a heuristic function from A*. —Kri (talk) 22:22, 23 September 2014 (UTC)

I rewrote the first paragraph of the article to reflect this fact. —Kri (talk) 22:49, 23 September 2014 (UTC)

I do not understand Python

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

I've just added another pseudocode. Please check if there is something unclear and/or incorrect Stannic (talk) 23:32, 24 July 2013 (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)

Order of generating successors

Does the order of generating successors matter in the algorithm as presented here? Currently, the search is stops at the first encounter with a solution, but I don't think that guarantees optimality unless successors(node) returns nodes succ in increasing order of cost(node, succ). QVVERTYVS (hm?) 16:03, 12 January 2015 (UTC)

Unnecessary ordering requirement for successors!?

successors(node) node expanding function, expand nodes ordered by g + h(node)

The above is the description of the successors. The discussion earlier in 2014 concluded that the successors have to be considered in an increasing ordering of f-values, but I do not think this is true. The above line may be a remnant of that discussion.

The reason why the first encountered goal state is the one with the lowest cost path is that when goal node n is found, the threshold on the preceding round was set to f(n). That's why higher cost paths to goal states will not be considered, and that's why the order in which the successors are generated does not matter.

The (incorrect) argument for having to order the successors would seem to be as follows. Consider starting state A, with two successors B and C, which both are goal states. Let h(A) = 1 and the cost of A->B is 2 and the cost of A->C is 3. If we just went through the successors and detected a goal state as soon as we saw one, then of course a bad ordering of the successors would lead to the more expensive goal state C. But the first time B and C are encountered we do not check whether they are goal states. Instead, their f-values f(B)=2 and f(C)=3 are used in computing the new threshold, which will be 2. On the next iteration any visit to C will not check whether C is a goal state because f(C) is above the threshold. But B will be detected as a goal state as it should.

That's why the misleading "expand nodes ordered by g + h(node)" should be removed, as it plays no role in the optimality of the algorithm. — Preceding unsigned comment added by 84.253.238.230 (talk) 08:32, 27 January 2021 (UTC)

Wrong Bound in Pseudocode?

In the routine "ida_star" of the pseudocode, bound is set to "h(root)". But "h(root)" is a lower bound for the cost. Shouldn't it be an upper bound? --Been-jamming (talk) 19:06, 19 December 2021 (UTC)

Question is a bit stale now, but maybe someone will benefit from the answer. Korf (1985) calls for h(root) as the initial bound (section 6). In that work, h() is assumed to admissible, which assures the lowest cost solution is found by A* and IDA* both. But your intuition is correct. To get the optimal solution, you need admissible h(), and the higher h() is, while being admissible, the better. Call me Bifficus (talk) 15:57, 26 September 2023 (UTC)