IDA *

from Wikipedia, the free encyclopedia

IDA * ( English iterative deepening A * ) is a term from computer science . It describes a method for searching for the shortest path between two nodes (graph theory) in a graph . The algorithm combines the desirable properties of depth-first search (low memory consumption) and a variant of breadth-first search , the A * algorithm (control of the search using a heuristic).

General

In contrast to normal and iterative depth-first search , IDA * is an informed search ; it works in a similar way to iterative depth-first search , but controls the search depth with the help of a heuristic.

The iterative depth-first search essentially consists of a loop in which the search depth (starting at 1) is increased by the value 1 per loop pass until a solution is found. The depth from the starting node to the examined node is always measured. If the unit for the depth is no longer the number of edges but a different unit (e.g. path length in kilometers), you have to specify a value when increasing the depth. If you choose the value too high, you may find a less than optimal solution.

IDA * does not take the depth from the starting node to the examined node for the termination condition, but the length of the entire path from the starting node to the destination node. Since only the length of the path from the starting node to the currently examined node is exactly known, the path length from the currently examined node to the destination node is estimated using a heuristic.

The heuristic used must meet one condition: The distance it estimates to the target must be less than or equal to the real distance to the target. In a geographical search in the road network, the straight line length is obviously a valid heuristic.

Algorithm (informal)

In IDA * the loop starts with the value of the heuristic for the start node as the limit for the search depth. According to the condition on the heuristic, there cannot be a shorter path from start to finish. The recursive search within the loop must either return a solution or the minimum of the path length determined by the heuristic for all nodes that were found as the first nodes behind the limit. This minimum is used as the limit for the search depth for the next loop pass.

If there is no path from the start node to the destination node, this algorithm does not terminate. To prevent the infinite loop, you can limit the outer loop, for example with a limit that is obtained by multiplying the value calculated by the heuristic for the start node with a fixed factor (arbitrarily set to 10 in the following program code).

Algorithm (formal) 

public Node<?> solve(Node root) {
    Node solutionNode = null;
    int bound = root.getOptimisticDistanceToSolution();
    // 10 ist ein willkürlich gewählter Faktor zur Begrenzung der Suche
    int maxBound = bound * 10; 
    while (solutionNode == null) {
        SearchResult r = search(root, bound);
        if (r.solutionNode != null) {
            solutionNode = r.solutionNode;
        }
        if (r.t >= maxBound) {
	        return null;
        }
        bound = r.t;
    }
    return solutionNode;
}

SearchResult search(Node node, int bound) {
    int f = node.getMovesDone() + node.getOptimisticDistanceToSolution();
    if (f > bound) {
        return new SearchResult(f);
    }
    if (node.isSolution()) {
        return new SearchResult(node);
    }
    int min = Integer.MAX_VALUE;
    List<Node> successors = node.nextNodes();
    for (Node succ : successors) {
        SearchResult r = search(succ, bound);
        if (r.solutionNode != null) {
	        return r;
        }
        if (r.t < min) {
	        min = r.t;
        }
    }
    return new SearchResult(min);
}

properties

Storage space consumption

The storage space consumption is proportional to the number of edges on the way from the start to the destination node. It is thus significantly smaller than with a breadth-first search or the A * algorithm, since the search front and the set of nodes already examined do not have to be saved.

running time

In the worst case, all possible paths to all possible nodes are considered, the runtime then increases exponentially with the search depth (measured in number of edges). With a good heuristic, however, the runtime is significantly shorter.

literature