Iterative Deepening Finished
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 ->
io:format("Solution not found at depth ~w, iterating~n", [Limit]),
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 not found at depth 1, iterating
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 not found at depth 1, iterating
Solution not found at depth 2, iterating
Solution not found at depth 3, iterating
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 not found at depth 1, iterating
Solution not found at depth 2, iterating
Solution not found at depth 3, iterating
Solution not found at depth 4, iterating
Solution not found at depth 5, iterating
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 not found at depth 2, iterating
Solution not found at depth 3, iterating
Solution not found at depth 4, iterating
Solution not found at depth 5, iterating
Solution not found at depth 6, iterating
Solution not found at depth 7, iterating
Solution not found at depth 8, iterating
Solution not found at depth 9, iterating
Solution not found at depth 10, iterating
Solution not found at depth 11, iterating
Solution not found at depth 12, iterating
Solution not found at depth 13, 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.
