I am making a Java program but I am having trouble on part of it. Here is the pr
ID: 3792107 • Letter: I
Question
I am making a Java program but I am having trouble on part of it.
Here is the program I am trying to create:
Create a project to solve the Cannibals and Missionaries problem: Three missionaries and three cannibals are on one side of a river, along with a boat that can hold one or two people. Find a way to get everyone to the other side without ever leaving a group of missionaries in one place outnumbered by the cannibals in that place. Implement and solve this problem by generating an appropriate tree structure and then using an appropriate search algorithm to search this tree.
The problem I am having is generating the tree structure so that I can search it. Could you please help show me how to generate the tree structure or at least how to go about making it?
Explanation / Answer
aaa
File 1: BreadthFirstSearch
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Set;
public class BreadthFirstSearch {
public State exec(State initialState) {
if (initialState.isGoal()) {
return initialState;
}
Queue<State> frontier = new LinkedList<State>(); // FIFO queue
Set<State> explored = new HashSet<State>();
frontier.add(initialState);
while (true) {
if (frontier.isEmpty()) {
return null; // failure
}
State state = frontier.poll();
explored.add(state);
List<State> successors = state.generateSuccessors();
for (State child : successors) {
if (!explored.contains(child) || !frontier.contains(child)) {
if (child.isGoal()) {
return child;
}
frontier.add(child);
}
}
}
}
}
File 2: DepthLimitedSearch
import java.util.List;
public class DepthLimitedSearch {
public State exec(State initialState) {
int limit = 20;
return recursiveDLS(initialState, limit);
}
private State recursiveDLS(State state, int limit) {
if (state.isGoal()) {
return state;
} else if (limit == 0) {
return null;
} else {
List<State> successors = state.generateSuccessors();
for (State child : successors) {
State result = recursiveDLS(child, limit - 1);
if (null != result) {
return result;
}
}
return null;
}
}
}
file 3: Main.java
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
public class Main {
public static void main(String[] args) {
System.out.println("==== Missionaries and Cannibals Problem ====");
System.out.println("Choose the search method: ");
System.out.println(" 1. Breadth-first search");
System.out.println(" 2. Depth-limited search");
System.out.print(" Type your choice and press ENTER: ");
String optionStr = null;
try {
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
optionStr = in.readLine();
} catch (IOException e) {
System.out.println("[ERROR] Fail to read the typed option.");
e.printStackTrace();
}
int option = Integer.parseInt(optionStr);
State initialState = new State (3, 3, Position.LEFT, 0, 0);
switch(option) {
case 1:
executeBFS(initialState);
break;
case 2:
executeDLS(initialState);
break;
default:
System.out.println("[ERROR] Invalid search option.");
}
}
private static void executeBFS(State initialState) {
BreadthFirstSearch search = new BreadthFirstSearch();
State solution = search.exec(initialState);
printSolution(solution);
}
private static void executeDLS(State initialState) {
DepthLimitedSearch search = new DepthLimitedSearch();
State solution = search.exec(initialState);
printSolution(solution);
}
private static void printSolution(State solution) {
if (null == solution) {
System.out.print(" No solution found.");
} else {
System.out.println(" Solution (cannibalLeft,missionaryLeft,boat,cannibalRight,missionaryRight): ");
List<State> path = new ArrayList<State>();
State state = solution;
while(null!=state) {
path.add(state);
state = state.getParentState();
}
int depth = path.size() - 1;
for (int i = depth; i >= 0; i--) {
state = path.get(i);
if (state.isGoal()) {
System.out.print(state.toString());
} else {
System.out.print(state.toString() + " -> ");
}
}
System.out.println(" Depth: " + depth);
}
}
}
file 4: State.Java
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
public class Main {
public static void main(String[] args) {
System.out.println("==== Missionaries and Cannibals Problem ====");
System.out.println("Choose the search method: ");
System.out.println(" 1. Breadth-first search");
System.out.println(" 2. Depth-limited search");
System.out.print(" Type your choice and press ENTER: ");
String optionStr = null;
try {
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
optionStr = in.readLine();
} catch (IOException e) {
System.out.println("[ERROR] Fail to read the typed option.");
e.printStackTrace();
}
int option = Integer.parseInt(optionStr);
State initialState = new State (3, 3, Position.LEFT, 0, 0);
switch(option) {
case 1:
executeBFS(initialState);
break;
case 2:
executeDLS(initialState);
break;
default:
System.out.println("[ERROR] Invalid search option.");
}
}
private static void executeBFS(State initialState) {
BreadthFirstSearch search = new BreadthFirstSearch();
State solution = search.exec(initialState);
printSolution(solution);
}
private static void executeDLS(State initialState) {
DepthLimitedSearch search = new DepthLimitedSearch();
State solution = search.exec(initialState);
printSolution(solution);
}
private static void printSolution(State solution) {
if (null == solution) {
System.out.print(" No solution found.");
} else {
System.out.println(" Solution (cannibalLeft,missionaryLeft,boat,cannibalRight,missionaryRight): ");
List<State> path = new ArrayList<State>();
State state = solution;
while(null!=state) {
path.add(state);
state = state.getParentState();
}
int depth = path.size() - 1;
for (int i = depth; i >= 0; i--) {
state = path.get(i);
if (state.isGoal()) {
System.out.print(state.toString());
} else {
System.out.print(state.toString() + " -> ");
}
}
System.out.println(" Depth: " + depth);
}
}
}
File 1: BreadthFirstSearch
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Set;
public class BreadthFirstSearch {
public State exec(State initialState) {
if (initialState.isGoal()) {
return initialState;
}
Queue<State> frontier = new LinkedList<State>(); // FIFO queue
Set<State> explored = new HashSet<State>();
frontier.add(initialState);
while (true) {
if (frontier.isEmpty()) {
return null; // failure
}
State state = frontier.poll();
explored.add(state);
List<State> successors = state.generateSuccessors();
for (State child : successors) {
if (!explored.contains(child) || !frontier.contains(child)) {
if (child.isGoal()) {
return child;
}
frontier.add(child);
}
}
}
}
}
File 2: DepthLimitedSearch
import java.util.List;
public class DepthLimitedSearch {
public State exec(State initialState) {
int limit = 20;
return recursiveDLS(initialState, limit);
}
private State recursiveDLS(State state, int limit) {
if (state.isGoal()) {
return state;
} else if (limit == 0) {
return null;
} else {
List<State> successors = state.generateSuccessors();
for (State child : successors) {
State result = recursiveDLS(child, limit - 1);
if (null != result) {
return result;
}
}
return null;
}
}
}
file 3: Main.java
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
public class Main {
public static void main(String[] args) {
System.out.println("==== Missionaries and Cannibals Problem ====");
System.out.println("Choose the search method: ");
System.out.println(" 1. Breadth-first search");
System.out.println(" 2. Depth-limited search");
System.out.print(" Type your choice and press ENTER: ");
String optionStr = null;
try {
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
optionStr = in.readLine();
} catch (IOException e) {
System.out.println("[ERROR] Fail to read the typed option.");
e.printStackTrace();
}
int option = Integer.parseInt(optionStr);
State initialState = new State (3, 3, Position.LEFT, 0, 0);
switch(option) {
case 1:
executeBFS(initialState);
break;
case 2:
executeDLS(initialState);
break;
default:
System.out.println("[ERROR] Invalid search option.");
}
}
private static void executeBFS(State initialState) {
BreadthFirstSearch search = new BreadthFirstSearch();
State solution = search.exec(initialState);
printSolution(solution);
}
private static void executeDLS(State initialState) {
DepthLimitedSearch search = new DepthLimitedSearch();
State solution = search.exec(initialState);
printSolution(solution);
}
private static void printSolution(State solution) {
if (null == solution) {
System.out.print(" No solution found.");
} else {
System.out.println(" Solution (cannibalLeft,missionaryLeft,boat,cannibalRight,missionaryRight): ");
List<State> path = new ArrayList<State>();
State state = solution;
while(null!=state) {
path.add(state);
state = state.getParentState();
}
int depth = path.size() - 1;
for (int i = depth; i >= 0; i--) {
state = path.get(i);
if (state.isGoal()) {
System.out.print(state.toString());
} else {
System.out.print(state.toString() + " -> ");
}
}
System.out.println(" Depth: " + depth);
}
}
}
file 4: State.Java
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
public class Main {
public static void main(String[] args) {
System.out.println("==== Missionaries and Cannibals Problem ====");
System.out.println("Choose the search method: ");
System.out.println(" 1. Breadth-first search");
System.out.println(" 2. Depth-limited search");
System.out.print(" Type your choice and press ENTER: ");
String optionStr = null;
try {
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
optionStr = in.readLine();
} catch (IOException e) {
System.out.println("[ERROR] Fail to read the typed option.");
e.printStackTrace();
}
int option = Integer.parseInt(optionStr);
State initialState = new State (3, 3, Position.LEFT, 0, 0);
switch(option) {
case 1:
executeBFS(initialState);
break;
case 2:
executeDLS(initialState);
break;
default:
System.out.println("[ERROR] Invalid search option.");
}
}
private static void executeBFS(State initialState) {
BreadthFirstSearch search = new BreadthFirstSearch();
State solution = search.exec(initialState);
printSolution(solution);
}
private static void executeDLS(State initialState) {
DepthLimitedSearch search = new DepthLimitedSearch();
State solution = search.exec(initialState);
printSolution(solution);
}
private static void printSolution(State solution) {
if (null == solution) {
System.out.print(" No solution found.");
} else {
System.out.println(" Solution (cannibalLeft,missionaryLeft,boat,cannibalRight,missionaryRight): ");
List<State> path = new ArrayList<State>();
State state = solution;
while(null!=state) {
path.add(state);
state = state.getParentState();
}
int depth = path.size() - 1;
for (int i = depth; i >= 0; i--) {
state = path.get(i);
if (state.isGoal()) {
System.out.print(state.toString());
} else {
System.out.print(state.toString() + " -> ");
}
}
System.out.println(" Depth: " + depth);
}
}
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.