|
Professional Programmer
Join Date: Feb 2005
Posts: 343
Rep Power: 4 
|
can someone please help me with this tree
Ok, so i need to make a tree where each node is a 2d array and it can have possibly 4 children per node. Each 2d array has 1 blank spot represented by 0. This blank can move either, left, up, right, down in that order, thats where the 4 children come from. It finds the first set of children fine, in fact it even finds the goal fine, if the goal is among the first set of children. If the goal is not among the first set of children it goes into an infinite loop because it keeps producing the same 4 children over and over again. I think its something with how it saves the children, i think it might over write them or something, im not sure but i have until tomorrow at noon to have this done and i am close, i think. All i am missing is the recursive step that is needed to produce the next layers of children. I also need to keep track of a function f(n) and state that has the lowest f(n) is the state that i produce its children. The children are checked to see if they are the goal right when they are produced. F(n) is simply the level of the tree i am on plus the number of ints in the 2d array that the current state has that are different from the goal state. So while im going through this tree making children i need to keep track of the level, i actually think i do that correctly but can not make the chidlren correctly, again i think because of the way java references objects or something. I know i've asked a few questions related to this without telling what the whole thing is, mainly out of laziness. But anyway here are the 2 classes that i am using. The GridNode clas contains the 2d array and all the methods to manipulate it. The other class has main as well as the methods that go up and down the tree. Its pretty sloppy because i only have a little bit of time to finish it so ive just been doing whatever i can to try and figure it out. If anyone can tell me what i need to do i would appreciate it. Thanks,
import java.io.*;
public class GridNode
{
private int[][] state;
private GridNode leftChild;
private GridNode upChild;
private GridNode rightChild;
private GridNode downChild;
private int level;
private int f;
private int h;
// set state to newState and firstChild to newFirstChild and nextSibling to newNextSibling
public GridNode(int[][] newState, GridNode newLeftChild, GridNode newUpChild, GridNode newRightChild, GridNode newDownChild)
{
setState(newState);
setLeftChild(newLeftChild);
setUpChild(newUpChild);
setRightChild(newRightChild);
setDownChild(newDownChild);
} // end GridNode constructor
// empty constructor
public GridNode()
{
}
// copy one state to another
public static int[][] copy(int[][] a)
{
int[][] b = new int[a[0].length][a.length];
for (int i = 0; i < a.length; i++)
for (int j = 0; j < a[0].length; j++)
b[i][j] = a[i][j];
return b;
} // end copy
public int getLevel()
{
return level;
} // end getLevel
public int getF()
{
return f;
} // end getF
public int getH()
{
return h;
} // end getH
public void setLevel(int newLevel)
{
level = newLevel;
} // end setLevel
public void setF(int newF)
{
f = newF;
} // end setF
public void setH(int newH)
{
h = newH;
} // end setH
public static GridNode copy(GridNode a)
{
GridNode b = a;
return b;
} // end copy
// get current state
public int[][] getState()
{
return state;
} // end getState
public void setState(int[][] newState)
{
state = newState;
} // end setState
// set leftChild
public void setLeftChild(GridNode newLeftChild)
{
leftChild = newLeftChild;
} // end setLeftChild
// set UpChild
public void setUpChild(GridNode newUpChild)
{
upChild = newUpChild;
} // end setUpChild
// set right child
public void setRightChild(GridNode newRightChild)
{
rightChild = newRightChild;
} // end setRightChild
// set down child
public void setDownChild(GridNode newDownChild)
{
downChild = newDownChild;
} // end setDownChild;
// get leftChild
public GridNode getLeftChild()
{
return leftChild;
} // end getLeftCHild
// getUpChild
public GridNode getUpChild()
{
return upChild;
} // end getUpChild
// get right child
public GridNode getRightChild()
{
return rightChild;
} // getRightChild;
public GridNode getDownChild()
{
return downChild;
} // end getDownChild
// print the current state
public void printNode()
{
for(int row = 0; row < 3; row++)
{
for(int col = 0; col < 3; col++)
System.out.print(state[row][col] + " ");
System.out.println();
} // end for
} // end printNode
// check to see if current state is equal to the goal state
public boolean isEqual(int[][] state, int[][] goalState)
{
for (int row = 0; row < 3; row++)
{
for (int col = 0; col < 3; col++)
{
if (state[row][col] == goalState[row][col])
continue;
else
return false;
} // end for
} // end for
return true;
} // end isEqual
// calculates h1(n)
public int findHone(int[][] state, int[][] goalState)
{
int hOne = 0;
for (int row = 0; row < 3; row++)
{
for (int col = 0; col < 3; col++)
{
if (state[row][col] != goalState[row][col] && state[row][col] != 0)
hOne++;
else
continue;
} // end for
} // end for
return hOne;
} // end findHone
// find f(n) = g(n) + h(n)
public int findF(int g, int h)
{
return g + h;
} // end findF
// check to see if it can move left
public boolean canMoveLeft(int[][] state)
{
int tempPos = -1;
for (int row = 0; row < 3; row++)
{
for (int col = 0; col < 3; col++)
{
if (state[row][col] == 0)
tempPos = col;
} // end for
} // end for
if (tempPos == 0)
return false;
else
return true;
} // end canMoveLeft
// check to see if it can move up
public boolean canMoveUp(int[][] state)
{
int tempPos = -1;
for (int row = 0; row < 3; row++)
{
for (int col = 0; col < 3; col++)
{
if (state[row][col] == 0)
tempPos = row;
} // end for
} // end for
if (tempPos == 0)
return false;
else
return true;
} // end canMoveUp
// check to see if it can move right
public boolean canMoveRight(int[][] state)
{
int tempPos = -1;
for (int row = 0; row < 3; row++)
{
for (int col = 0; col < 3; col++)
{
if (state[row][col] == 0)
tempPos = col;
} // end for
} // end for
if (tempPos == 2)
return false;
else
return true;
} // end canMoveRight
// check to see if it can move down
public boolean canMoveDown(int[][] state)
{
int tempPos = -1;
for (int row = 0; row < 3; row++)
{
for (int col = 0; col < 3; col++)
{
if (state[row][col] == 0)
tempPos = row;
} // end for
} // end for
if (tempPos == 2)
return false;
else
return true;
} // end canMoveDown
// move it left, the old one
public void moveLeft(int[][] state)
{
for (int row = 0; row < 3; row++)
{
for (int col = 0; col < 3; col++)
{
if (state[row][col] == 0)
{
state[row][col] = state[row][col-1];
state[row][col-1] = 0;
//printNode();
return;
} // end if
} // end for
} // end for
} // end moveLeft
// move it Up
public void moveUp(int[][] state)
{
for (int row = 0; row < 3; row++)
{
for (int col = 0; col < 3; col++)
{
if (state[row][col] == 0)
{
state[row][col] = state[row-1][col];
state[row-1][col] = 0;
// printNode(state);
return;
} // end if
} // end for
} // end for
} // end moveUp
// move it right
public void moveRight(int[][] state)
{
for (int row = 0; row < 3; row++)
{
for (int col = 0; col < 3; col++)
{
if (state[row][col] == 0)
{
state[row][col] = state[row][col+1];
state[row][col+1] = 0;
// printNode(state);
return;
} // end if
} // end for
} // end for
} // end moveRight
// move it down
public void moveDown(int[][] state)
{
//int tempPos = -1;
for (int row = 0; row < 3; row++)
{
for (int col = 0; col < 3; col++)
{
if (state[row][col] == 0)
{
state[row][col] = state[row+1][col];
state[row+1][col] = 0;
// printNode(state);
return;
} // end if
} // end for
} // end for
} // end moveDown
} // end GridNode
import java.util.*;
public class NewMain
{
private static int level;
private static List tree = new LinkedList();
private static int[][] goalState = {{7, 2, 6},
{8, 0, 4},
{1, 5, 3}
};
static int[][] initialState = {{7, 6, 4},
{8, 5, 2},
{1, 0, 3}
};
// insert root and check if its goal
static void insertRoot(GridNode root)
{
tree.add(0, root);
} // end insertRoot
// return node with the smallest f(n)
static GridNode findF(List tree, int level)
{
GridNode temp;
int lowestF = 200;
int tempLowestF = 200;
int tempLowestH = 200;
int i = 0;
int tempI = 0;
while (i < tree.size())
{
temp = (GridNode) tree.get(i);
tempLowestH = temp.findHone(temp.getState(), goalState);
tempLowestF = level + tempLowestH;
if (tempLowestF < lowestF)
{
lowestF = tempLowestF;
tempI = i;
} // end if
i++;
} // end while
return (GridNode) tree.get(tempI);
} // end findF
// insert children
static void insertChild(GridNode parent, GridNode child)
{
if (parent.canMoveLeft(parent.getState()))
{
child.setState(parent.copy(parent.getState()));
child.moveLeft(child.getState());
if (child.isEqual(child.getState(), goalState))
{
child.printNode();
return;
} // end if
tree.add(child);
parent.setLeftChild(child);
System.out.println("The child is");
child.printNode();
System.out.println();
//System.out.println("the parent is");
//parent.printNode();
level++;
if (parent.canMoveUp(parent.getState()))
{
child.setState(parent.copy(parent.getState()));
child.moveUp(child.getState());
if (child.isEqual(child.getState(), goalState))
{
child.printNode();
return;
} // end if
tree.add(child);
parent.setUpChild(child);
System.out.println("The child is");
child.printNode();
System.out.println();
//System.out.println("the parent is");
//parent.printNode();
} // end if
if (parent.canMoveRight(parent.getState()))
{
child.setState(parent.copy(parent.getState()));
child.moveRight(child.getState());
if (child.isEqual(child.getState(), goalState))
{
child.printNode();
return;
} // end if
tree.add(child);
parent.setRightChild(child);
System.out.println("The child is");
child.printNode();
System.out.println();
//System.out.println("the parent is");
//parent.printNode();
} // end if
if (parent.canMoveDown(parent.getState()))
{
child.setState(parent.copy(parent.getState()));
child.moveDown(child.getState());
if (child.isEqual(child.getState(), goalState))
{
child.printNode();
return;
} // end if
tree.add(child);
parent.setDownChild(child);
System.out.println("The child is");
child.printNode();
System.out.println();
// System.out.println("the parent is");
//parent.printNode();
} // end if
} // end if
else if (parent.canMoveUp(parent.getState()))
{
child.setState(parent.copy(parent.getState()));
child.moveUp(child.getState());
if (child.isEqual(child.getState(), goalState))
{
child.printNode();
return;
} // end if
tree.add(child);
parent.setUpChild(child);
parent.setUpChild(parent.copy(child));
System.out.println("The child is");
child.printNode();
System.out.println();
//System.out.println("the parent is");
//parent.printNode();
level++;
if (parent.canMoveRight(parent.getState()))
{
child.setState(parent.copy(parent.getState()));
child.moveRight(child.getState());
if (child.isEqual(child.getState(), goalState))
{
child.printNode();
return;
} // end if
tree.add(child);
parent.setRightChild(child);
System.out.println("The child is");
child.printNode();
System.out.println();
//System.out.println("the parent is");
//parent.printNode();
} // end if
if (parent.canMoveDown(parent.getState()))
{
child.setState(parent.copy(parent.getState()));
child.moveDown(child.getState());
if (child.isEqual(child.getState(), goalState))
{
child.printNode();
return;
} // end if
tree.add(child);
parent.setDownChild(child);
System.out.println("The child is");
child.printNode();
System.out.println();
// System.out.println("the parent is");
// parent.printNode();
} // end if
} // end else if
else if (parent.canMoveRight(parent.getState()))
{
child.setState(parent.copy(parent.getState()));
child.moveRight(child.getState());
if (child.isEqual(child.getState(), goalState))
{
child.printNode();
return;
} // end if
tree.add(child);
parent.setRightChild(child);
System.out.println("The child is");
child.printNode();
System.out.println();
//System.out.println("the parent is");
//parent.printNode();
level++;
if (parent.canMoveDown(parent.getState()))
{
child.setState(parent.copy(parent.getState()));
child.moveDown(child.getState());
if (child.isEqual(child.getState(), goalState))
{
child.printNode();
return;
} // end if
tree.add(child);
parent.setDownChild(child);
System.out.println("The child is");
child.printNode();
System.out.println();
//System.out.println("the parent is");
//parent.printNode();
} // end if
} // end else if
else if (parent.canMoveDown(parent.getState()))
{
child.setState(parent.copy(parent.getState()));
child.moveDown(child.getState());
if (child.isEqual(child.getState(), goalState))
{
child.printNode();
return;
} // end if
tree.add(child);
parent.setDownChild(child);
System.out.println("The child is");
child.printNode();
System.out.println();
//System.out.println("the parent is");
//parent.printNode();
level++;
} // end else if
if (!child.isEqual(child.getState(), goalState))
{
System.out.println("the level is " + level);
insertChild(findF(tree, level), child);
} // end if
} // end insertChild
// print the node and f(n) for the node being used
public static void printOutput(GridNode node, int f, int g, int h)
{
node.printNode();
System.out.println("the f(n) function is: " + f + " = " + g + " + " + h);
System.out.println();
} // end printOutput
public static void main(String[] args)
{
GridNode parent = new GridNode(initialState, null, null, null, null);
GridNode child = new GridNode(null, null, null, null, null);
insertChild(parent, child);
System.out.println("the size of the list is " + tree.size());
System.out.println();
// find out its f(n) value
// find out if its the goal
// if not find next set of children
//System.out.println(findF(tree));
} // end main
} // end NewMain |