# The Geeks Shall Inherit the Earth

Personal Ramblings of the Techhouse Admin

Pages

## Iterative Deepening Finished

11 May, 2010 (19:43) | Erlang | By: Brian

I’ve completed the iterative deepening blind search algorithm and it works pretty well. The final solution is here:

```%%Problem 5
%% iterative deepening blind search
iterative_deepening_search(Problem) ->
ids_recursive(Problem, 1).

ids_recursive(Problem, Limit) ->
case depth_limited_search(Problem, Limit) of
{found, FoundState} ->
print_solution_path(Problem, FoundState),
{found, FoundState};
_Other ->
ids_recursive(Problem, Limit + 1)
end.

%% depth limited search
%% starts a depth limited search, prints solution if found
depth_limited_search(Problem, Limit) ->
case dls_recursive(Problem, new_solution(Problem), Limit) of
{found, FoundState} ->
{found, FoundState};
Other ->
Other
end.

%first try to match the goal state
dls_recursive(
#problem{goal_state = Goal},
#solution_state{state = Goal} = SState,
_Limit) ->
%io:format("Goals match: ~w~n", [Goal] ),
{found, SState};
%then see if we hit bottom
dls_recursive(_Problem,
#solution_state{depth = Depth}, Limit) when Depth >= Limit ->
{not_found, max_depth_reached};
%else generate the next possible states and iterate through them
dls_recursive(Problem, State, Limit) ->
%expand the solution with all possible moves and go deeper
New_SStates = expand_solution(Problem, State),
%try each one until it passes
dls_recurse_with_cut_off(Problem, New_SStates, Limit).

%% expand solution
expand_solution(Problem, Solution_State) ->
lists:map(fun(Move) -> update_solution(Solution_State, Move) end,
possible_moves(Problem#problem.yard, Solution_State#solution_state.state) ).

%recurse over the generated states as a stack
%if we empty the stack return out of moves
dls_recurse_with_cut_off(_Problem, [], _Limit) ->
{not_found, out_of_moves};
%take the top state of the stack, if goal return immediately
%else try the next move on the stack
dls_recurse_with_cut_off(Problem, [SState | Rest], Limit) ->
case dls_recursive(Problem, SState, Limit) of
{found, FoundState} ->
{found, FoundState};
{not_found, _Reason}    ->
dls_recurse_with_cut_off(Problem, Rest, Limit)
end.```

And some sample runs.

```trainswitch:iterative_deepening_search(trainswitch:problem3()).
Solution state at depth: 2
To go from [{t1,[engine]},{t2,[a]},{t3,[b]}] to
[{t1,[engine,a,b]}]
Apply: [{left,t2,t1},{left,t3,t1}]
{found,{solution_state,[{t1,[engine,a,b]}],
[{left,t3,t1},{left,t2,t1}],
2}}

trainswitch:iterative_deepening_search(trainswitch:problem4()).
Solution state at depth: 4
To go from [{t1,[engine]},{t2,[a]},{t3,[b,c]},{t4,[d]}] to
[{t1,[engine,a,b,c,d]}]
Apply: [{left,t2,t1},{left,t3,t1},{left,t3,t1},{left,t4,t1}]
{found,{solution_state,[{t1,[engine,a,b,c,d]}],
[{left,t4,t1},{left,t3,t1},{left,t3,t1},{left,t2,t1}],
4}}

trainswitch:iterative_deepening_search(trainswitch:problem5()).
Solution state at depth: 6
To go from [{t1,[engine]},{t2,[a]},{t3,1},{t4,[d]}] to
[{t1,[engine,a,b,c,d]}]
Apply: [{left,t3,t1},{right,t1,t4},{left,t2,t1},{left,t3,t1},{left,t4,t1},{left,t4,t1}]
{found,{solution_state,[{t1,[engine,a,b,c,d]}],
[{left,t4,t1},
{left,t4,t1},
{left,t3,t1},
{left,t2,t1},
{right,t1,t4},
{left,t3,t1}],
6}}```

For research and testing purposes I found a simple function online that runs a call a specified number of times, measures how long those runs take and then produces some useful stats. Here is that utility:

```test_avg(M, F, A, N) when N > 0 ->
L = test_loop(M, F, A, N, []),
Length = length(L),
Min = lists:min(L),
Max = lists:max(L),
Med = lists:nth(round((Length / 2)), lists:sort(L)),
Avg = round(lists:foldl(fun(X, Sum) -> X + Sum end, 0, L) / Length),
io:format("Range: ~b - ~b mics~n"
"Median: ~b mics~n"
"Average: ~b mics~n",
[Min, Max, Med, Avg]),
Med.

test_loop(_M, _F, _A, 0, List) ->
List;
test_loop(M, F, A, N, List) ->
{T, _Result} = timer:tc(M, F, A),
test_loop(M, F, A, N - 1, [T|List]).```

This blind search solves the smaller of the really large problems, 1 and 2, in a reasonable amount of time.

```Solution not found at depth 1, iterating
Solution state at depth: 14
To go from [{t1,[engine]},{t2,[d]},{t3,[b]},{t4,[a,e]},{t5,1}] to
[{t1,[engine,a,b,c,d,e]}]
Apply: [{left,t5,t1},{left,t2,t1},{right,t1,t5},{right,t1,t5},{right,t1,t2},{left,t4,t2},{left,t3,t2},{left,t4,t2},{left,t2,t1},{left,t2,t1},{left,t2,t1},{left,t5,t1},{left,t5,t1},{left,t2,t1}]
Range: 253234999 - 259874999 mics
Median: 255812999 mics
Average: 255859399 mics
255812999```

This means that problem 2 takes about 255 seconds, or 4 minutes to run with this blind search. Even if we know the depth ahead of time, 14, it still takes a long time for this to run. About 50 seconds on average.

```trainswitch:test_avg(trainswitch, depth_limited_search, [trainswitch:problem2(), 14], 5).
Range: 46078000 - 48249999 mics
Median: 47765999 mics
Average: 47484399 mics
47765999
```

The next part of this assignment is to implement an A* heuristic search of some kind on this problem. Which basically means find an algorithm that will generate a rough guess as to how close to the goal state each next step is, and choose the one that’s closest to pursue. Before going down that route, I want to explore the concurrency model in Erlang briefly. My plan is to replace the depth-limited-search algorithm with a supervisor process that spawns off processes for each next state and sends them off running. It will listen to each of its child processes for either a found state, in which case it returns that state and kills off its other workers, or all of its children have hit dead-ends and it returns a solution not found state. Each child process similarly acts as a supervisor to spawn a series of child processes that it listens to, and so on. I have no idea what sort of performance impact this will have. I know it will be somewhat random, as the different processes may run at different speeds. But that’s what the measure lots of times and average function is for.