CSCI 485 --- Fall 2023

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.