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.