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.