Consider you are a student trying to find the chocolate at graduation in the maz
ID: 3721283 • Letter: C
Question
Consider you are a student trying to find the chocolate at graduation in the maze shown in Figure 1. You enter straight (downward) through the upper left space (marked 11). You are to find one solution using a depth first search, given the maze and traversal constraints. These constraints are:
(a) Once entered, you cannot leave the maze (if helpful you can show a rejected adjacent outside space by assigning a sequential number, such as 02 adjacent to 12 or 25 to 24). (b) Your mouse can move forward one space at a time into 1 of 3 spaces, if not otherwise constrained, to the left, straight ahead, or to the right. (For example, your second move possibilities would be to 10, 21, or 12.)
(c) You cannot go through a wall (constraining the first 2 possibilities given in b).
(d) You cannot move into a space forming a cycle (e.g., for j not equal to i, X[i] does not equal X[j]).
(e) If unable to move forward (due to preceding constraints), you may reverse your last forward progress step (e.g., backtrack).
Develop a DFS solution for this problem, showing your backtracking tree and give the solution asthe spaces visited in sequence (e.g., {X[i] | i = 1..n: 11, 12, ..., 44}, where n is the number ofspaces visited before taking the cheese); show and analyze the DFS algorithm (time complexity) regarding other similar maze problems.
Student 12 13 14 23 24 21 31 32 34 41 42 43 Chocolate Figure 1: MazeExplanation / Answer
Solution: See the code below
1. DFSAgent class: DFSAgent.java
------------------------------------------------------------
package mazesolver;
/**
* DFSAgent class
*
*/
class DFSAgent {
private int[][] G; //Adjacency matrix of grapgh
private int nV; //number of vertices in graph
private enum COLOR {
WHITE,
GRAY,
BLACK
};
private int time; //time at which a vertex is accessed, discovered or visited.
private COLOR[] color; //color of each vertex indicating whether unvisited, discovered or visited.
private int[] parents; //parent vertex through which a vertex is discovered.
private int[] discoveredTime; //time when a vertex is discovered.
private int[] finishedTime; //time when a vertex is completely visited i.e. all its adjacent vertices are explored.
private static final int NIL=-1; //shows a NIL value
//private utility method to perform DFS
private void DFS_VISIT(int vertex)
{
color[vertex]=COLOR.GRAY; //vertex turns GRAY if it has been discovered.
time++;
discoveredTime[vertex]=time; //time at which vertex is discovered.
//explore adjacent vertices of vertex
for(int j=0;j<nV;j++)
{
if(G[vertex][j]==1)
{
if(color[j]==COLOR.WHITE)
{
parents[j]=vertex;
DFS_VISIT(j);
}
}
}
color[vertex]=COLOR.BLACK; //vertex turns BLACK if it is finished.
time++;
finishedTime[vertex]=time; //time at which vertex is finished.
}
/**
* constructor
*/
public DFSAgent(int G[][],int nV) {
// TODO Auto-generated constructor stub
this.G=G;
this.nV=nV;
this.time=0;
this.color=new COLOR[nV];
this.parents=new int[nV];
this.discoveredTime=new int[nV];
this.finishedTime=new int[nV];
}
/**
* performs DFS
*/
public void DFS()
{
for(int i=0;i<nV;i++)
{
color[i]=COLOR.WHITE; //initially every vertex is WHITE.
parents[i]=NIL;
}
time=0;
for(int i=0;i<nV;i++)
{
if(color[i]==COLOR.WHITE)
{
DFS_VISIT(i);
}
}
}
/**
* @return the parents
*/
public int[] getParents() {
return parents;
}
/**
* @return the discoveredTime
*/
public int[] getDiscoveredTime() {
return discoveredTime;
}
/**
* @return the finishedTime
*/
public int[] getFinishedTime() {
return finishedTime;
}
}
----------------------------------------------------
2. MAZESolver class: MAZESolver.java
-----------------------------------------------------
package mazesolver;
/**
* MAZESolver class
*
*/
public class MAZESolver {
static int MAZE[][]; //MAZE to solve
static int size; //size of MAZE
/**
* @param args
*/
public static void main(String[] args) {
//MAZE specification
MAZESolver.size=4; //example size. you can change this
MAZESolver.MAZE=new int[size][size];
/*
* Initialize MAZE. MAZE is visualized as a graph. If two ends of MAZE (vertices in graph)
* are connected, then they will be marked as 1, otherwise 0;
* Note: You can change this scheme by assigning weights or values as you desire.
*/
for(int i=0;i<MAZESolver.size;i++)
{
for(int j=0;j<MAZESolver.size;j++)
{
if(i!=j)
{
MAZESolver.MAZE[i][j]=1;
}
}
}
//initialize DFSAgent
DFSAgent dfsAgent=new DFSAgent(MAZESolver.MAZE,MAZESolver.size);
//performs DFS
dfsAgent.DFS();
//prints how the maze is solved
for(int i=0;i<MAZESolver.size;i++)
{
System.out.println("vertex:"+i+" ,parent:"+dfsAgent.getParents()[i]+" ,finished time:"+dfsAgent.getFinishedTime()[i]);
}
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.