Skip to content

A* and IDA* Search Overview

Johnny K edited this page Mar 5, 2019 · 1 revision

A* and IDA* search are a set of state space searching algorithms that find an optimal path from a beginning state to a known destination state. They can be used to solve a variety of problems from solving a puzzle with the least amount of steps to find the quickest path through a maze.

State Space Searches

State space search problems attempt to find the optimal path between an initial state and a goal state. This problem is equivalent to finding the optimal path between two nodes on a graph. Each state can be represented as a node on a graph. Each node has a set of reachable neighboring nodes which represent the states that can be reached from the current state. By exploring paths on the graph we attempt to find the optimal path from the starting node to the goal node.

In state space search problems we have states which can me modified to make new states. For instance we might have a puzzle we are trying to solve. We start at some state that is not the solution to the puzzle. The puzzle may have some set of rules that dictate what moves are currently possible(for instance we can only move an item a specific direction). So from a given starting state there may only be a few possible moves and each of these moves will be a new state. Eventually the goal state will be found by traversing the possible states.

A simple example would be navigating a maze. We start at some point in the maze and the goal is to reach the maze's endpoint. At any given point in the maze we have 4 basic directions that can be traveled: north, south, east, west. Of course there may be a wall that limits the possible directions or one direction may be back tracking. Your starting point is a node on a graph and each possible direction you can travel is a node connected to the current node. We can search through this graphs of states(state being the current position you are in) to find the state which represents you reaching the endpoint.

State Space Search Algorithms

There are a few algorithms that are popular for state space searches: depth-first search(DFS), breadth-first search(BFS), iterative deepening depth-first search(IDS), greedy searching, and A* search. Notice all these are graph algorithms because we are searching a state space tree.

All these algorithms have their own pros and cons. These pros and cons are often focused on: if the optimal solution is found, running time, and memory usage. We will skip discussion of other algorithms and solely focus on A* and IDA*. These two algorithms will both find optimal solutions, but differ in running time and memory usage. A* can consume more more memory than IDA*. IDA* can search the same paths over and over since it doesn’t use dynamic programming like A*, which can result in longer runtimes.

A* and IDA* Algorithms

Both these algorithms are similar in nature in that they try to intelligently select the order of the paths they explore. They both do this by using a heuristic function that scores how close (in terms of steps to reach the goal node) a node is to the goal node. The general idea is that we want to explore paths that lead to nodes that are more similar to the goal node and have a short path from and starting node. To achieve this both algorithms use a f value to score nodes and the f value is the sum of the nodes heuristic value and the length of the path to get this node. We explore nodes with a smaller f value before looking at ones with a larger f value. This pushes us to nodes that are getting more similar to the goal node while also having a shorter path.

An important characteristic of the heuristic function is that it must be admissible. A heuristic function is admissible if it underestimates or calculates the exact number of steps to reach the goal node. If the heuristic function is not admissible we cannot guarantee the optimal path will be found.

The main difference about these two algorithms is the process in which they explore the search space. In A* a priority queue is used to keep track of all possible children nodes queued to be explored. This means there can be a large number of nodes sitting in the queue which can waste a large amount of memory. IDA* on the other hand searches the graph in an iterative fashion exploring the search space at increasing depths per iteration. In each iteration it only stores the current path being explored. This leads to the memory usage being linear to the length of the path being explored. The downside to IDA* is that the same paths will be revisited on each iteration possibly resulting in a longer runtime.