4

Can somebody explain about Iterative Deepening A*? I still don't understand how it works. Iterative deepening search w/ Depth First Search, and If still not found the solution; increase the Depth++ until found solution.

If Iterative deepening using Depth, then Iterative Deepening A* use what to limit their search?

Here are a picture if you need to explain how it IDA* Works, i just don't understand how it works.

(1,2,4,9) and etc, is the step

0+2=2 is f(n)=g(n)+h(n)

IDA* EXAMPLE

yudayyy
  • 260
  • 2
  • 9
  • 20

1 Answers1

6

If Iterative deepening using Depth, then Iterative Deepening A* use what to limit their search?

The naive implementation of IDA* would just have something like threshold++ at the end of every iteration, similar to your depth++ above. This is to keep IDA* admissible.

A better algorithm (that still keeps IDA* admissible) would be to increase the threshold by the next smallest g() cost that is available (from the closed set to the open set).

See: http://webdocs.cs.ualberta.ca/~jonathan/PREVIOUS/Courses/657/Notes/10.Single-agentSearch.pdf

Shaggy Frog
  • 27,575
  • 16
  • 91
  • 128
  • `search a node as long as f <= threshold` so, if the f() cost <= threshold, then increase the threshold++. What is the first value for the **threshold**? – yudayyy May 09 '12 at 04:13
  • @yudayyy The value of the smallest outgoing edge from the start node. – Shaggy Frog May 09 '12 at 04:25
  • 2
    Actually, if you generate the f-cost of the child and detect it is outside of the current f-cost bound, then you should use the lowest f-cost of an unexplored child, not just the f-cost of the parent plus the g-cost to the child. – Nathan S. May 09 '12 at 05:43