|
Step 1>
package com.kartik.river.pass;
import java.util.ArrayList;
import java.util.Arrays;
/**
* A state is defined as a 4-bit string (encapsulated by
* the Pos enum) which represents whether a particular entity (in the
order
* TigerGoatGrassState) is on the west or east side of the river.
*
* @author kartik chandra Mandal
*
*/
public class TigerGoatGrassState implements State
{
// constant for the goal state
private final TigerGoatGrassState.Pos[] GOAL = new
TigerGoatGrassState.Pos[]
{ Pos.EAST, Pos.EAST, Pos.EAST, Pos.EAST };
/*
* All fwgc states are defined by the 4-item array of Pos primitives,
either
* east or west (side of the river) for each member of the problem
* "BoatMan, Tiger, Goat, Grass" in that order
*/
public enum Pos
{
WEST, EAST
};
// The current 4-bit representation of the state
public Pos[] curState;
/**
* Default Constructor
*/
public TigerGoatGrassState()
{
curState = new Pos[]
{ Pos.WEST, Pos.WEST, Pos.WEST, Pos.WEST };
}
/**
* Polymorphic constructor #1
*
* @param fPos
* -
Farmer position
* @param wPos
* -
Tiger position
* @param gPos
* -
Goat position
* @param cPos
* -
Grass position
*/
public TigerGoatGrassState(Pos fPos, Pos wPos, Pos gPos, Pos cPos)
{
curState = new Pos[]
{ fPos, wPos, gPos, cPos };
}
/**
* Polymorphic constructor #2
*
* @param stateArr
* -
Array containing a state, which has all four positions
*/
public TigerGoatGrassState(TigerGoatGrassState.Pos[] stateArr)
{
curState = new Pos[]
{ stateArr[0], stateArr[1], stateArr[2], stateArr[3] };
}
/**
* How much it costs to come to this state
*/
@Override
public double findCost()
{
return 1;
}
/**
* Generate all possible successors to the current state.
*
* Will trim out successor states that match a state description in the
* "invalid states" array.
*/
@Override
public ArrayList<State> genSuccessors()
{
ArrayList<State> successors = new ArrayList<State>();
TigerGoatGrassState.Pos[] tempState = Arrays.copyOf(curState,
curState.length);
/*
* If the farmer is on the west He can take the w
*/
// if the farmer is on the west
if (tempState[0] == Pos.WEST)
{
// he must select an entity to take
// taking the tiger east, if the goat isn't alone there
if (tempState[1] == Pos.WEST)
{
tempState[0] = Pos.EAST;
tempState[1] = Pos.EAST;
successors.add(new TigerGoatGrassState(tempState));
tempState = Arrays.copyOf(curState, curState.length);//
reset
}
// taking the goat east
if (tempState[2] == Pos.WEST)
{
tempState[0] = Pos.EAST;
tempState[2] = Pos.EAST;
successors.add(new TigerGoatGrassState(tempState));
tempState = Arrays.copyOf(curState, curState.length);
}
// taking the grass east, if the goat isn't alone there
if (tempState[3] == Pos.WEST)
{
tempState[0] = Pos.EAST;
tempState[3] = Pos.EAST;
successors.add(new TigerGoatGrassState(tempState));
tempState = Arrays.copyOf(curState, curState.length);
}
// going alone, if we didn't add anything
tempState[0] = Pos.EAST;
successors.add(new TigerGoatGrassState(tempState));
tempState = Arrays.copyOf(curState, curState.length);
}
// if the farmer is on the east
else
{
// he must select an entity to take
// taking the tiger west
if (tempState[1] == Pos.EAST)
{
tempState[0] = Pos.WEST;
tempState[1] = Pos.WEST;
successors.add(new TigerGoatGrassState(tempState));
tempState = Arrays.copyOf(curState, curState.length);
}
// taking the goat west
if (tempState[2] == Pos.EAST)
{
tempState[0] = Pos.WEST;
tempState[2] = Pos.WEST;
successors.add(new TigerGoatGrassState(tempState));
tempState = Arrays.copyOf(curState, curState.length);
}
// taking the grass west
if (tempState[3] == Pos.EAST)
{
tempState[0] = Pos.WEST;
tempState[3] = Pos.WEST;
successors.add(new TigerGoatGrassState(tempState));
tempState = Arrays.copyOf(curState, curState.length);
}
// going alone
tempState[0] = Pos.WEST;
successors.add(new TigerGoatGrassState(tempState));
tempState = Arrays.copyOf(curState, curState.length);
}
for (int i = 0; i < successors.size(); i++)
{
TigerGoatGrassState s = (TigerGoatGrassState)
successors.get(i);
tempState = s.curState;
// check for conflicts, also don't return to the starting
state why
// not
if (Arrays.equals(tempState, new TigerGoatGrassState.Pos[]
{ Pos.EAST, Pos.EAST, Pos.WEST, Pos.WEST })
|| Arrays.equals(tempState, new
TigerGoatGrassState.Pos[]
{ Pos.EAST, Pos.WEST, Pos.WEST, Pos.WEST })
|| Arrays.equals(tempState, new
TigerGoatGrassState.Pos[]
{ Pos.EAST, Pos.WEST, Pos.WEST, Pos.EAST })
|| Arrays.equals(tempState, new
TigerGoatGrassState.Pos[]
{ Pos.WEST, Pos.EAST, Pos.EAST, Pos.WEST })
|| Arrays.equals(tempState, new
TigerGoatGrassState.Pos[]
{ Pos.WEST, Pos.WEST, Pos.EAST, Pos.EAST })
|| Arrays.equals(tempState, new
TigerGoatGrassState.Pos[]
{ Pos.WEST, Pos.EAST, Pos.EAST, Pos.EAST })
|| Arrays.equals(tempState, new
TigerGoatGrassState.Pos[]
{ Pos.WEST, Pos.WEST, Pos.WEST, Pos.WEST }))
{
successors.remove(i);
i = 0; // start the search over to ensure all nodes
are checked
// x.x
}
}
return successors;
}
/**
* Check to see if the current state is the goal state.
*
* @return - true or false, depending on whether the current state
matches
* the goal
*/
@Override
public boolean isGoal()
{
if (Arrays.equals(curState, GOAL))
{
return true;
}
return false;
}
/**
* Overriden equals method. Generated by Eclipse
*/
@Override
public boolean equals(Object obj)
{
if (this == obj)
return true;
else if (obj == null)
return false;
else if (getClass() != obj.getClass())
return false;
TigerGoatGrassState other = (TigerGoatGrassState) obj;
if (!curState.equals(other.curState))
return false;
return true;
}
/**
* Method to print out the current state. Prints the current position
of
* each thing.
*/
@Override
public void printState()
{
System.out.println("Boatman: " +
curState[0]+"\t|");
System.out.println("Tiger: " +
curState[1]+"\t|");
System.out.println("Goat: " +
curState[2]+"\t|");
System.out.println("Grass: " +
curState[3]+"\t|");
}
@Override
public void printStateOdd() {
StringBuffer br = new StringBuffer();
br.append("Boatman:
").append(curState[0]).append("\n\t\t")
.append("Tiger:
").append(curState[1]).append("\n\t\t")
.append("Goat: ").append(curState[2]).append("\n\t\t")
.append("Grass:
").append(curState[3]).append("\n");
String newTabFromat = br.toString();
System.out.println(newTabFromat);
}
/**
* Overloaded equals method to compare two states.
*
* @return true or false, depending on whether the states are equal
*/
@Override
public boolean equals(State s)
{
if (Arrays.equals(curState, ((TigerGoatGrassState)
s).getCurState()))
{
return true;
}
else
return false;
}
/**
* @return the curState
*/
public Pos[] getCurState()
{
return curState;
}
}
Step 2>
package com.kartik.river.pass;
import java.util.ArrayList;
/**
*
* State interface from which problem states inherit. Defines a method
to check
* if the current state is a goal, generate successors, and find the
cost to
* come to the current state.
*
* @author kartik chandra Mandal
*
*/
public interface State {
/**
* determine if current state is goal
*
* @return boolean
*/
boolean isGoal();
/**
* generate successors to the current state
*
* @return ArrayList<State>
*/
ArrayList<State> genSuccessors();
/**
* determine cost from initial state to THIS state
*
* @return double
*/
double findCost();
/**
* print the current state
*/
public void printState();
/**
* print the current state
*/
public void printStateOdd();
/**
* compare the actual state data
*
* @param s
* s
* @return boolean
*/
public boolean equals(State s);
}
Step 3>
package com.kartik.river.pass;
/**
*
* Class to represent a SearchNode. This will be a wrapper for a State,
and
* track the cost to get to that state and the state's parent node.
*
* @author kartik chandra Mandal
*
*/
public class SearchNode {
private State curState;
private SearchNode parent;
private double cost; // cost to get to this state
private double hCost; // heuristic cost
private double fCost; // f(n) cost
/**
* Constructor for the root SearchNode
*
* @param state
*
the state passed in
*/
public SearchNode(State state) {
curState = state;
parent = null;
cost = 0;
hCost = 0;
fCost = 0;
}
/**
* Constructor for all other SearchNodes
*
* @param prev
*
the parent node
* @param state
*
the state
* @param currentCost
*
the g(n) cost to get to this node
* @param heuristic
*
the h(n) cost to get to this node
*/
public SearchNode(SearchNode prev, State state, double currentCost,
double heuristic) {
parent = prev;
curState = state;
cost = currentCost;
hCost = heuristic;
fCost = cost + hCost;
}
/**
* @return the curState
*/
public State getCurState() {
return curState;
}
/**
* @return the parent
*/
public SearchNode getParent() {
return parent;
}
/**
* @return the cost
*/
public double getCost() {
return cost;
}
/**
*
* @return the heuristic cost
*/
public double getHCost() {
return hCost;
}
/**
*
* @return the f(n) cost for A*
*/
public double getFCost() {
return fCost;
}
}
Step 4>
package com.kartik.river.pass;
import java.util.ArrayList;
import java.util.Stack;
/**
* Defines a Depth-First search to be performed on a qualifying puzzle.
* Currently supports TigerGoatGrassState.
*
* @author kartik chandra Mandal
*/
public class DFSearchForBTGG {
/**
* Initialization function for TigerGoatGrassState DFSearch
*/
public static void search(boolean d) {
SearchNode root = new SearchNode(new TigerGoatGrassState());
Stack<SearchNode> stack = new Stack<SearchNode>();
stack.add(root);
performSearch(stack, d);
}
/*
* Helper method to check to see if a SearchNode has already been
evaluated.
* Returns true if it has, false if it hasn't.
*/
private static boolean checkRepeats(SearchNode searNode) {
boolean retValue = false;
SearchNode checkNode = searNode;
// While n's parent isn't null, check to see if it's equal to the
node
// we're looking for.
while (searNode.getParent() != null && !retValue) {
if (searNode.getParent().getCurState()
.equals(checkNode.getCurState())) {
retValue = true;
}
searNode = searNode.getParent();
}
return retValue;
}
/**
* Performs a DFSearch using q as the search space
*
* @param stackOfSearchNode
* -
A SearchNode queue to be populated and searched
*/
public static void performSearch(Stack<SearchNode>
stackOfSearchNode,
boolean flag) {
int searchCount = 1; // counter for number of iterations
while (!stackOfSearchNode.isEmpty()) // while the queue is not
empty
{
SearchNode tempNode = (SearchNode) stackOfSearchNode.pop();
// if tempNode is not the goal state
if (!tempNode.getCurState().isGoal()) {
// generate tempNode's immediate successors
ArrayList<State> tempSuccessors =
tempNode.getCurState()
.genSuccessors();
/*
* Loop through the successors, wrap them in a
SearchNode, check
* if they've already been evaluated, and if not, add
them to
* the queue
*/
for (int i = 0; i < tempSuccessors.size(); i++) {
// second parameter here adds the cost of the
new node to
// the current cost total in the SearchNode
SearchNode newNode = new SearchNode(tempNode,
tempSuccessors.get(i),
tempNode.getCost()
+
tempSuccessors.get(i).findCost(), 0);
if (!checkRepeats(newNode)) {
stackOfSearchNode.add(newNode);
}
}
searchCount++;
} else
// The goal state has been found. Print the path it took to
get to
// it.
{
// Use a stack to track the path from the starting
state to the
// goal state
Stack<SearchNode> solutionPath = new
Stack<SearchNode>();
solutionPath.push(tempNode);
tempNode = tempNode.getParent();
while (tempNode.getParent() != null) {
solutionPath.push(tempNode);
tempNode = tempNode.getParent();
}
solutionPath.push(tempNode);
// The size of the stack before looping through and
emptying it.
int loopSize = solutionPath.size();
System.out
.println("How to crossing the river
of boat man by DFS algo?");
System.out.println("From->To\t|
To->From");
System.out.println("-------------------------------");
for (int i = 0; i < loopSize; i++) {
tempNode = solutionPath.pop();
if (i % 2 == 0) {
tempNode.getCurState().printState();
} else {
System.out.print("\t\t");
tempNode.getCurState().printStateOdd();
}
System.out.println();
System.out.println();
}
System.out.println("The cost was: " +
tempNode.getCost());
if (flag) {
System.out.println("The number of nodes
examined: "
+ searchCount);
}
System.exit(0);
}
}
System.out.println("Error! No solution found!");
}
}
Step 5>
package com.kartik.river.pass;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;
/**
* Defines a Bredth-First search to be performed on a qualifying puzzle.
* Currently supports TigerGoatGrassState.
*
* @author kartik chandra Mandal
*/
public class BFSearchForBTGG {
/**
* Initialization function for TigerGoatGrassState BFSearch
*/
public static void search(boolean d) {
SearchNode root = new SearchNode(new TigerGoatGrassState());
Queue<SearchNode> queue = new
LinkedList<SearchNode>();
queue.add(root);
performSearch(queue, d);
}
/**
* Helper method to check to see if a SearchNode has already been
evaluated.
* Returns true if it has, false if it hasn't.
*/
private static boolean checkRepeats(SearchNode n) {
boolean retValue = false;
SearchNode checkNode = n;
// While n's parent isn't null, check to see if it's equal to the
node
// we're looking for.
while (n.getParent() != null && !retValue) {
if
(n.getParent().getCurState().equals(checkNode.getCurState())) {
retValue = true;
}
n = n.getParent();
}
return retValue;
}
/**
*
* Performs a BFSearch using q as the search space
*
* @param q
* -
A SearchNode queue to be populated and searched
* @param d
* A
SearchNode queue to be populated and searched
*/
public static void performSearch(Queue<SearchNode> q, boolean d)
{
int searchCount = 1; // counter for number of iterations
while (!q.isEmpty()) // while the queue is not empty
{
SearchNode tempNode = (SearchNode) q.poll();
if (!tempNode.getCurState().isGoal()) // if tempNode is not
the goal
//
state
{
ArrayList<State> tempSuccessors =
tempNode.getCurState()
.genSuccessors(); // generate tempNode's
immediate
//
successors
/*
* Loop through the successors, wrap them in a
SearchNode, check
* if they've already been evaluated, and if not, add
them to
* the queue
*/
for (int i = 0; i < tempSuccessors.size(); i++) {
// second parameter here adds the cost of the
new node to
// the current cost total in the SearchNode
SearchNode newNode = new SearchNode(tempNode,
tempSuccessors.get(i),
tempNode.getCost()
+
tempSuccessors.get(i).findCost(), 0);
if (!checkRepeats(newNode)) {
q.add(newNode);
}
}
searchCount++;
} else
// The goal state has been found. Print the path it took to
get to
// it.
{
// Use a stack to track the path from the starting
state to the
// goal state
Stack<SearchNode> solutionPath = new
Stack<SearchNode>();
solutionPath.push(tempNode);
tempNode = tempNode.getParent();
while (tempNode.getParent() != null) {
solutionPath.push(tempNode);
tempNode = tempNode.getParent();
}
solutionPath.push(tempNode);
// The size of the stack before looping through and
emptying it.
int loopSize = solutionPath.size();
System.out
.println("How to crossing the river
of boat man by BFS algo?");
System.out.println("From->To\t|
To->From");
System.out.println("-------------------------------");
for (int i = 0; i < loopSize; i++) {
tempNode = solutionPath.pop();
if (i % 2 == 0) {
tempNode.getCurState().printState();
} else {
System.out.print("\t\t");
tempNode.getCurState().printStateOdd();
}
System.out.println();
System.out.println();
}
System.out.println("The cost was: " +
tempNode.getCost());
if (d) {
System.out.println("The number of nodes
examined: "
+ searchCount);
}
System.exit(0);
}
}
// This should never happen with our current puzzles.
System.out.println("Error! No solution found!");
}
}
Step 6>
package com.kartik.river.pass;
import java.util.Scanner;
public class ProblemSolver
{
static char continueOption;
static char menuOpion;
public static void main(String[] args) {
// Numbers to be adjusted if the debug toggle is present, as
components
// of args will be in different locations if it is.
// Print out correct usage and end the program if there aren't
any
// parameters
do {
System.out
.println("'B' - To be execute forTiger
Goat And Grass problem by Bfs algo running");
System.out
.println("'D' - To be execute forTiger
Goat And Grass problem by Dfs algo running");
System.out.println("'N' - To quite running
program");
System.out.println("Please choose your choices");
Scanner keyboard = new Scanner(System.in);
String input = keyboard.next();
menuOpion = input.charAt(0);
boolean debug = false;
switch (menuOpion) {
case 'B':
BFSearchForBTGG.search(debug);
break;
case 'D':
DFSearchForBTGG.search(debug);
break;
default:
System.out.println("you enter wrong menu
option");
}
System.out.println();
System.out.print("Do you want to Continue? Y/N");
continueOption = keyboard.next().charAt(0);
} while (continueOption == 'Y' || continueOption == 'y');
}
}
Out put:
'B' - To be execute forTiger Goat And Grass problem by Bfs algo running
'D' - To be execute forTiger Goat And Grass problem by Dfs algo running
'N' - To quite running program
Please choose your choices
B
How to crossing the river of boat man by BFS algo?
From->To | To->From
-------------------------------
Boatman: WEST |
Tiger: WEST |
Goat: WEST |
Grass: WEST |
Boatman: EAST
Tiger: WEST
Goat: EAST
Grass: WEST
Boatman: WEST |
Tiger: WEST |
Goat: EAST |
Grass: WEST |
Boatman: EAST
Tiger: EAST
Goat: EAST
Grass: WEST
Boatman: WEST |
Tiger: EAST |
Goat: WEST |
Grass: WEST |
Boatman: EAST
Tiger: EAST
Goat: WEST
Grass: EAST
Boatman: WEST |
Tiger: EAST |
Goat: WEST |
Grass: EAST |
Boatman: EAST
Tiger: EAST
Goat: EAST
Grass: EAST
The cost was: 7.0
|
0 Comments