# Iterative Deepening

*By Robert Laing*

A snag we hit in puzzle solving is the graph isn’t handily prestored in a database
for route finding using transitive closures
with infinite loop protection thanks to cycles with tabling.
We have to turn to what’s sometimes called *generative recursion* to dynamically build our graph as we explore it. For this, we’ll return to the techniques introduced in BreadthDepthFirst.

We’ll be using iterative deepening depth-first search which gets depth first to mimic breadth first by doing it repeatedly, lengthening its depth-limit one step at a time. The reason is unbounded depth first instead of finding the shortest route, finds the leftmost route. Breadth first does find the shortest route, but even the cheap RAM available on modern computers is often insufficient for it to complete this task.

As in route finding, we want a rule `route(Start, End, Path)`

. We can’t simply call a transitive closure in examples such as buttons and lights and
wolf, goat, cabbage because initially all we have is the starting node
and rules to expand a node. To build a simple skeleton template to expand on later, we’ll be using `arc(Parent, Child)`

and a slightly modified version of the `getchildren`

rule used in BreadthDepthFirst. The difference is that to trace a path from `start`

to `goal`

, we need to remember the pairs. I’m keeping to the tradition of using an unlabeled graph and working with nodes, but for most practical purposes, we actually want a `string`

of labels as we’ll get to in puzzle solving`.

We also need to remember the depth of each arc.

```
getchildren(Depth, Parent, Children) :-
findall(arc(Depth, Parent, Child), arc(Parent, Child), Unsorted),
sort(Unsorted, Children).
```

Iterative deepening allows us to memoize child nodes generated in past iterations, and we only need to append new nodes to the frontier list when we reach an unexplored level. The basic template used in BottomUpRecursion gets a third rule to simply shunt nodes from the frontier to the visited list when we are not at the *Limit* depth.

```
depthfirst(_, [], RGraph, Graph) :-
reverse(RGraph, Graph).
depthfirst(Limit, [arc(Depth, Parent, Child)|Frontier], Visited, Acc) :-
\+succ(Depth, Limit),
depthfirst(Limit, Frontier, [arc(Depth, Parent, Child)|Visited], Acc).
depthfirst(Limit, [arc(Depth, Parent, Child)|Frontier], Visited, Acc) :-
succ(Depth, Limit),
getchildren(Limit, Child, GrandChildren),
append(GrandChildren, Frontier, NewFrontier),
depthfirst(Limit, NewFrontier, [arc(Depth, Parent, Child)|Visited], Acc).
```

Next we have the recursive *iterative deepening* rule which keeps increasing the depth limit and feeding the visited list of the previous call as the frontier list of the current call until the *end* goal is found. This is a first attempt which runs into problems with cycles and unreachable goals (eg `route(a, x, Path)`

) would hang the computer.

```
iterative_deepening(Limit, End, Graph, Graph) :-
memberchk(arc(Limit, _, End), Graph).
iterative_deepening(Depth, End, GraphIn, Acc) :-
\+memberchk(arc(Depth, _, End), GraphIn),
succ(Depth, Limit),
depthfirst(Limit, GraphIn, [], GraphOut),
iterative_deepening(Limit, End, GraphOut, Acc).
```

`route(Start, End, Path)`

will need to use the list of arcs produced by iterative_deepening to create a list of nodes from start to end. As explained in PuzzleSolving, for nearly all practical purposes we want a list of the labels between the nodes (the historical meaning of the jargon term `string`

), not a list of the nodes themselves. But lets stick to this computer science textbook tradition for now.

```
getpath(Start, Graph, [Node|Path], [Start, Node|Path]) :-
member(arc(1, Start, Node), Graph).
getpath(Start, Graph, [Child|Path], Acc) :-
member(arc(_, Parent, Child), Graph),
getpath(Start, Graph, [Parent, Child|Path], Acc).
route(Start, End, Path) :-
getchildren(1, Start, GraphIn),
iterative_deepening(1, End, GraphIn, GraphOut),
getpath(Start, GraphOut, [End], Path).
```

Testing the above on this example with `route(a, t, Path)`

we’ll get the desired answers of *Path = [a, b, f, m, t]* and *Path = [a, c, h, n, t]*.

Similarly, `route(a, s, Path)`

(a worst case scenario at the bottom right) promptly gives us *Path = [a, d, j, s]*.

Snags with the code so far is there’s not protection from {{{{route(a, x, Path)}}} hanging the computer. This can be fixed by adding a statement to iterative_deepening:

```
iterative_deepening(Limit, End, Graph, Graph) :-
memberchk(arc(Limit, _, End), Graph).
iterative_deepening(Depth, End, GraphIn, Acc) :-
\+memberchk(arc(Depth, _, End), GraphIn),
succ(Depth, Limit),
depthfirst(Limit, GraphIn, [], GraphOut),
GraphOut \== GraphIn,
iterative_deepening(Limit, End, GraphOut, Acc).
```

Adding the guard `GraphOut \== GraphIn`

halts the recursion when depthfirst isn’t finding anything new.

The full code for the above example looks like this. An advantage of iterative deepening is that besides memoizing old search results, we can prune known ‘‘cul-de-sacs’’ out of the graph which we’ll get to next in PrunedIterativeDeepening.

```
arc(a, b).
arc(a, c).
arc(a, d).
arc(b, e).
arc(b, f).
arc(c, g).
arc(c, h).
arc(c, i).
arc(d, j).
arc(e, k).
arc(f, l).
arc(f, m).
arc(h, n).
arc(i, o).
arc(i, p).
arc(j, q).
arc(j, r).
arc(j, s).
%arc(m, f).
%arc(m, m).
arc(m, t).
arc(n, t).
getchildren(Depth, Parent, Children) :-
findall(arc(Depth, Parent, Child), arc(Parent, Child), Unsorted),
sort(Unsorted, Children).
depthfirst(_, [], RGraph, Graph) :-
reverse(RGraph, Graph).
depthfirst(Limit, [arc(Depth, Parent, Child)|Frontier], Visited, Acc) :-
\+succ(Depth, Limit),
depthfirst(Limit, Frontier, [arc(Depth, Parent, Child)|Visited], Acc).
depthfirst(Limit, [arc(Depth, Parent, Child)|Frontier], Visited, Acc) :-
succ(Depth, Limit),
getchildren(Limit, Child, GrandChildren),
append(GrandChildren, Frontier, NewFrontier),
depthfirst(Limit, NewFrontier, [arc(Depth, Parent, Child)|Visited], Acc).
% iterative_deepening(_, _, [], []).
iterative_deepening(Limit, End, Graph, Graph) :-
memberchk(arc(Limit, _, End), Graph).
iterative_deepening(Depth, End, GraphIn, Acc) :-
\+memberchk(arc(Depth, _, End), GraphIn),
succ(Depth, Limit),
depthfirst(Limit, GraphIn, [], GraphOut),
GraphOut \== GraphIn,
iterative_deepening(Limit, End, GraphOut, Acc).
getpath(Start, Graph, [Node|Path], [Start, Node|Path]) :-
member(arc(1, Start, Node), Graph).
getpath(Start, Graph, [Child|Path], Acc) :-
member(arc(_, Parent, Child), Graph),
getpath(Start, Graph, [Parent, Child|Path], Acc).
route(Start, End, Path) :-
getchildren(1, Start, GraphIn),
iterative_deepening(1, End, GraphIn, GraphOut),
getpath(Start, GraphOut, [End], Path).
```