This task will refer to the graph below, where each vertex represents a state, a

Question

This task will refer to the graph below, where each vertex represents a state, and each arrow corresponds to a possible action transition. The cost of a transition is 1 unless there is a different number written for an edge. State A is the initial state and state I is the only state that satisfies the goal test. The number given in parentheses after the name of a state is a heuristic estimate of the cost to the goal.

1. Give the path, if one exists, that is found using the below-uninformed search techniques within the general tree search algorithm to get from A to I. When generating the successors of a node, assume their insertion into the queue has them appear in alphabetical order and that the nodes are added in batches (e.g., successors of A are in the queue ordered (AB AC) as a tuple). If the goal is found give the node (specified in terms of its path i.e. ABDH) that first passes the goal test, the total number of nodes generated (including the initial node), and how many nodes are in the fringe at its largest point. Otherwise, explain what prevents the search from finding the goal. (Note: for all the searches use the convention from class and the tree-search pseudocode on page 77 where a node is checked for the goal state when it is removed from the frontier.)

a. Breadth-first search

b. Depth-first search

c. Depth-limited search with limit 2 (the root is depth = 0)

d. Iterative Deepening Depth-Limited search

e. Consider an A* graph -search on this graph from state A to I. For each iteration of A*, write out the contents of the fringe, in prioritized order, and the contents of the closed/explored list. When writing out the list of nodes at a particular step, you should specify a node in terms of its path and its f() value (i.e AB(4)), as was done in class. When prioritizing the fringe, break ties putting first whichever node was in the fringe longer; if there is still a tie use alphabetical ordering based on the node’s state. When the search is finished, what solution was found, how many nodes were generated, and how many nodes were in the fringe at its largest point? Also, answer the following: Is the heuristic admissible? Is it consistent?

Explanation / Answer

NoSuchVertexException.java

import java.util.NoSuchElementException;

public class NoSuchVertexException extends RuntimeException
{
    public NoSuchVertexException(int vert)
    {
        super("Vertex does not exist: " + vert);
    }
}

GraphVertex.java

import java.util.LinkedList;
import java.awt.Point;

public class GraphVertex implements Comparable<GraphVertex>
{
    private int distanceFromStart;
    private LinkedList<Point> edges;
    public static final boolean START_VERTEX = true;
    public static final boolean INTERIOR_VERTEX = false;

    public GraphVertex(boolean vertexType)
    {
        edges = new LinkedList<Point>();
        if(vertexType == START_VERTEX)
        {
            distanceFromStart = 0;
        }
        else
        {
            distanceFromStart = Integer.MAX_VALUE;
        }
    }

    public void addEdge(int vertex, int distance)
    {
        edges.add(new Point(vertex, distance));
    }

    public int getDistanceFromStart()
    {
        return distanceFromStart;
    }

    public void setDistanceFromStart(int distance)
    {
        distanceFromStart = Math.min(distanceFromStart, distance);
    }

    public void relaxEdges(Graph g)
    {
        int size = edges.size();
        Point point;
        for(int position = 0; position < size; position++)
        {
            point = edges.get(position);
            g.setVertexDistanceFromStart(point.x, point.y + this.getDistanceFromStart());
        }
    }

    @Override
    public int compareTo(GraphVertex gv)
    {
        return this.getDistanceFromStart() - gv.getDistanceFromStart();
    }
}

Graph.java

import java.util.LinkedList;

public class Graph
{
    private LinkedList<GraphVertex> vertices;

    public Graph() {
        vertices = new LinkedList<GraphVertex>();
    }

    public void addVertex() {
        if (vertices.isEmpty()) {
            vertices.add(new GraphVertex(GraphVertex.START_VERTEX));
        } else {
            vertices.add(new GraphVertex(GraphVertex.INTERIOR_VERTEX));
        }
    }

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.