Lab 2
Below is a general tree search algorithm:
function Tree_Search(Problem problem, Container fringe) returns a solution, or failure Begin fringe.Insert(Make_Node(problem.Initial_State()); loop do if fringe.isEmpty then return failure; node = fringe.Remove_Front(); if problem.Goal_Test(node.State) succeeds return node; fringe.Insert_All(Expand(node, problem)); end loop End function Expand(Node node, Problem problem) returns a set of nodes Begin successors = the empty set; for each action, result in problem.Successor_Function(node.State) do s = new Node; s.Parent_node = node; s.Action = action; s.State = result; s.Path_Cost = node.Path_Cost + problem.Step_Cost(node.State, action, s.State); // if your Problem class can provide heuristics // s.Expected_Cost = s.Path_Cost + problem.heuristics(s.State); s.Depth = node.Depth + 1; add s to successors; return successors; End
When the breadth-first search strategy is used, the fringe is a queue.
When the depth-first search strategy is used, the fringe is a stack.
When the uniform cost search strategy is used, the fringe is a
priority queue using each node's Path_Cost as the key.
When the A* search strategy is used, the fringe is a priority
queue using each node's Expected_Cost as the key.
Assume that you've implemented the Problem class in the last lab, implement a search agent using which ever search strategy to find a solution from a problem's initial state to its goal state.