Iterative Deepening A Star in all languages

    Iterative Deepening A Star in Java

    Posted: , Last Updated:

    Java™ is a compiled language used for many purposes, ranging from embedded systems, UI-applications to web servers.

    See Code

    Iterative Deepening A Star in C

    Posted: , Last Updated:

    C is a compiled language used for many purposes, although it can be primarily found in systems where importance is important. This is because C offers a lot of low-level support for optimization, at the cost of not having some of the convenient abstractions that other languages offer. C is therefore primarily found in situations where available computation power is low such as embedded systems, or situations where required computation power is high, such as simulation or deep learning.

    See Code

    Iterative Deepening A Star in Javascript

    Posted: , Last Updated:

    JavaScript JavaScript is an interpreted scripting language previously primarily used in web pages (executed in browsers) that has since…

    See Code

    Iterative Deepening A Star in Python

    Posted: , Last Updated:

    Python Python™ is an interpreted language used for many purposes ranging from embedded programming to web development, with one of the largest use cases being data science.

    See Code

    Iterative Deepening A Star in R

    Posted: , Last Updated:

    R R is an interpreted language first released in 1993 with a significant increase in popularity in recent years. It is primarily used for data mining and -science as well as statistics, and is a popular language in non-computer science disciplines ranging from Biology to Physics. R is dynamically typed, and has one of the widest variety of libraries for statistics, machine learning, data mining etc.

    See Code

About the algorithm:

Iterative Deepening A Star Algorithm

The Iterative Deepening A Star (IDA*) algorithm is an algorithm used to solve the shortest path problem in a tree, but can be modified to handle graphs (i.e. cycles). It builds on Iterative Deepening Depth-First Search (ID-DFS) by adding an heuristic to explore only relevant nodes.

Description of the Algorithm

Whereas Iterative Deepening DFS uses simple depth to decide when to abort the current iteration and continue with a higher depth, Iterative Deepening A Star uses a heuristic to determine which nodes to explore and at which depth to stop. This is similar to how Dijkstra always explores the node with the currently shortest difference and A Star adds an heuristic to this to only explore nodes that are actually closer to the goal.

In more detail, this leads to the following Steps:

  1. For each child of the current node
  2. If it is the target node, return
  3. If the distance plus the heuristic exceeds the current threshold, return this exceeding threshold
  4. Set the current node to this node and go back to 1.
  5. After having gone through all children, go to the next child of the parent (the next sibling)
  6. After having gone through all children of the start node, increase the threshold to the smallest of the exceeding thresholds.
  7. If we have reached all leaf (bottom) nodes, the goal node doesn’t exist.

Example of the Algorithm

Consider the following graph: Graph for the Iterative Deepening A Star (IDA*) shortest path algorithm

The steps the algorithm performs on this graph if given node 0 as a starting point and node 6 as the goal, in order, are:

  1. Iteration with threshold: 6.32
  2. Visiting Node 0
  3. Visiting Node 1
  4. Breached threshold with heuristic: 8.66
  5. Visiting Node 2
  6. Breached threshold with heuristic: 7.00
  7. Iteration with threshold: 7.00
  8. Visiting Node 0
  9. Visiting Node 1
  10. Breached threshold with heuristic: 8.66
  11. Visiting Node 2
  12. Visiting Node 5
  13. Breached threshold with heuristic: 8.83
  14. Iteration with threshold: 8.66
  15. Visiting Node 0
  16. Visiting Node 1
  17. Visiting Node 3
  18. Breached threshold with heuristic: 12.32
  19. Visiting Node 4
  20. Breached threshold with heuristic: 8.83
  21. Visiting Node 2
  22. Visiting Node 5
  23. Breached threshold with heuristic: 8.83
  24. Iteration with threshold: 8.83
  25. Visiting Node 0
  26. Visiting Node 1
  27. Visiting Node 3
  28. Breached threshold with heuristic: 12.32
  29. Visiting Node 4
  30. Visiting Node 2
  31. Visiting Node 5
  32. Visiting Node 6
  33. Found the node we’re looking for!

Final lowest distance from node 0 to node 6: 9

Notice how the algorithm did not continue to explore down from node 3 in the iteration it found the goal node in. If node 3 would’ve had children, whereas Iterative Deepening DFS would’ve potentially (and needlessly!) explored them, Iterative Deepening A Star did not.

Runtime of the Algorithm

The runtime complexity of Iterative Deepening A Star is in principle the same as Iterative Deepening DFS. In practice, though, if we choose a good heuristic, many of the paths can be eliminated before they are explored making for a significant time improvement. More information on how the heuristic influences the complexity can be found on the Wikipedia Article.

Space of the Algorithm

The space complexity of Iterative Deepening A Star is the amount of storage needed for the tree or graph. O(|N|), |N| = number of Nodes in the tree or graph, which can be replaced with b^d for trees, where b is the branching factor and d is the depth. Additionally, whatever space the heuristic requires.