Algorithm SA can formally be extended to graph search.

First, graph-search needs to be transferred into some sort of tree search. There are several strategies dealing with the problem. For example, the procedure presented in Nilsson (1980) is one of the strategies. It generates an explicit graph G and a subset T of graph G called the search tree.

Second, since the branching factor is not a constant, and there is not only one solution path, the depth N at which the goal is located is generally unknown, etc. There is no threshold to be given in the graph-search algorithm. One of the formal algorithm may be given as follows.

Assume that T is a search tree of G, and has m 0-subtrees . The evaluation function ...

Start Free Trial

No credit card required