|
|
 |
|
|
Thread Tools | Display Modes |
Sep 19th, 2007, 7:27 PM
|
#1 |
|
Professional Programmer
Join Date: Feb 2005
Posts: 323
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 GridNodeimport 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 |
|
|
|
Sep 19th, 2007, 7:56 PM
|
#2 |
|
Resident Grouch
 
Join Date: Jun 2005
Posts: 6,453
Rep Power: 10
|
Why are you starting a new thread over each facet of a single problem? It dilutes your responses. Shall we answer here or there?
__________________
Abstraction doesn't make it impossible to write bad code; it makes it possible to write superior code. Contributor's Corner: Grumpy on C++ Exceptions DaWei on Pointers |
|
|
|
|
Sep 19th, 2007, 7:59 PM
|
#3 |
|
Professional Programmer
Join Date: Feb 2005
Posts: 323
Rep Power: 4
|
i dont know cause im losing my mind cause ive been working on this for about 6 - 10 hours a day for the past 7 days straight and am just frustrated cause there is no one (excluding what i got from you guys on this forum which i appreciate very much) that will give me even the slightest hint at anything that can help me. so to answer your question i dont care, i just want to know how to do this.
|
|
|
|
|
Sep 19th, 2007, 9:07 PM
|
#4 |
|
Resident Grouch
Join Date: Jun 2005
Posts: 6,453
Rep Power: 10
|
If you don't care, why should anyone else? Just curious.
__________________
Abstraction doesn't make it impossible to write bad code; it makes it possible to write superior code. Contributor's Corner: Grumpy on C++ Exceptions DaWei on Pointers |
|
|
|
|
Sep 19th, 2007, 9:30 PM
|
#5 |
|
Professional Programmer
Join Date: Feb 2005
Posts: 323
Rep Power: 4
|
no no no i mean i dont care where you put the answer, i do very much care about figuring this out. I'm been pulling my hair out over it for the past week and would really like to know what to do
|
|
|
|
|
Sep 20th, 2007, 9:24 AM
|
#6 | |
|
Resident Grouch
Join Date: Jun 2005
Posts: 6,453
Rep Power: 10
|
package ArrayThangy;
import java.io.*;
public class Main
{
public Main (){}
public static class ArrayThangy
{
public int[] theGoodies = {1, 2, 3};
public ArrayThangy (){}
}
public static void main (String args [])
{
ArrayThangy numeroUno = new ArrayThangy ();
ArrayThangy numeroDos = new ArrayThangy ();
ArrayThangy numeroTres = new ArrayThangy ();
System.out.println ("Assign array one to array two");
// The following will result in a shallow copy, a reference
numeroDos = numeroUno;
System.out.println ("Note that the arrays are identical");
System.out.print ("Array one: ");
for (int i = 0; i < numeroUno.theGoodies.length; i++)
{
System.out.print (numeroUno.theGoodies [i]);
System.out.print (" ");
}
System.out.print ("\nArray two: ");
for (int i = 0; i < numeroDos.theGoodies.length; i++)
{
System.out.print (numeroDos.theGoodies [i]);
System.out.print (" ");
}
System.out.println ("\n\nChange the value of an element in array two");
numeroDos.theGoodies [0] = 5;
System.out.println ("Note that the arrays are still identical");
System.out.print ("Array one: ");
for (int i = 0; i < numeroUno.theGoodies.length; i++)
{
System.out.print (numeroUno.theGoodies [i]);
System.out.print (" ");
}
System.out.print ("\nArray two: ");
for (int i = 0; i < numeroDos.theGoodies.length; i++)
{
System.out.print (numeroDos.theGoodies [i]);
System.out.print (" ");
}
System.out.println ("\n\nMake a deep copy of one to three");
// The following will result in a deep copy
for (int i = 0; i < numeroUno.theGoodies.length; i++)
numeroTres.theGoodies [i] = numeroUno.theGoodies [i];
System.out.println ("Note that arrays one and three are also identical");
System.out.print ("Array one: ");
for (int i = 0; i < numeroUno.theGoodies.length; i++)
{
System.out.print (numeroUno.theGoodies [i]);
System.out.print (" ");
}
System.out.print ("\nArray three: ");
for (int i = 0; i < numeroTres.theGoodies.length; i++)
{
System.out.print (numeroTres.theGoodies [i]);
System.out.print (" ");
}
System.out.println ("\nChange the value of an element in array three");
numeroTres.theGoodies [0] = 1;
System.out.println ("Note that the arrays are NOT identical");
System.out.print ("Array one: ");
for (int i = 0; i < numeroUno.theGoodies.length; i++)
{
System.out.print (numeroUno.theGoodies [i]);
System.out.print (" ");
}
System.out.print ("\nArray three: ");
for (int i = 0; i < numeroTres.theGoodies.length; i++)
{
System.out.print (numeroTres.theGoodies [i]);
System.out.print (" ");
}
}
}Quote:
__________________
Abstraction doesn't make it impossible to write bad code; it makes it possible to write superior code. Contributor's Corner: Grumpy on C++ Exceptions DaWei on Pointers |
|
|
|
|
|
Sep 20th, 2007, 10:51 AM
|
#7 |
|
Professional Programmer
Join Date: Feb 2005
Posts: 323
Rep Power: 4
|
i dont understand, I do make a copy of the array when i store it in the other one... i was thinking maybe something with setting the leftChild, upChild, rightChild, and downChild, but i also have a method that does that, i think it does it correctly anyway, and that didnt work either. I dont know, i think its kinda stupid too, that ive taken 2 years of java classes and this is the first time ive run into any problems with copying things from one instance to another or have heard anything about shallow copy and deep copy and all that, youd think in 4 java classes that somewhere along the line that would have been talked about, but it wasnt and i think thats part of what really threw me off for this assignment.
|
|
|
|
|
Sep 20th, 2007, 11:20 AM
|
#8 |
|
Resident Grouch
Join Date: Jun 2005
Posts: 6,453
Rep Power: 10
|
Okay, I don't know exactly what you're trying to do. Are you trying to make a matrix with a link from each element to the four adjoining, orthogonal elements?
Are you growing the matrix as time goes by? Does it always have an equal number of elements or each row? How do you determine the values to be placed in the elements?
__________________
Abstraction doesn't make it impossible to write bad code; it makes it possible to write superior code. Contributor's Corner: Grumpy on C++ Exceptions DaWei on Pointers |
|
|
|
|
Sep 20th, 2007, 4:14 PM
|
#9 |
|
Professional Programmer
Join Date: Feb 2005
Posts: 323
Rep Power: 4
|
each matrix is always 3 x 3 im trying to link matrices together
|
|
|
|
|
Sep 20th, 2007, 4:17 PM
|
#10 |
|
Resident Grouch
Join Date: Jun 2005
Posts: 6,453
Rep Power: 10
|
So you have a stack of 3x3 2D matrices, which makes a 3D entity. Does each matrix need to link to every other matrix, or only to the ones 'above' and 'below'?
I'm just trying to get a simplified picture so I can farble with it some.
__________________
Abstraction doesn't make it impossible to write bad code; it makes it possible to write superior code. Contributor's Corner: Grumpy on C++ Exceptions DaWei on Pointers |
|
|
|
|
| Bookmarks |
| Currently Active Users Viewing This Thread: 1 (0 members and 1 guests) | |
| Thread Tools | |
| Display Modes | |
|
|
Similar Threads
|
||||
| Thread | Thread Starter | Forum | Replies | Last Post |
| data tree for A* algorithm | cwl157 | Java | 0 | Sep 17th, 2007 3:48 PM |
| Pickle a Class | Dietrich | Python | 9 | Nov 17th, 2006 1:38 PM |
| linked list & binary tree questions | n00b | C++ | 14 | Nov 4th, 2006 2:24 AM |
| Having trouble implementing an int AVL Tree | xenop | Java | 2 | Oct 2nd, 2006 7:41 PM |
| BinaryTree , I need help on inserting expression to the Tree | Master | C# | 3 | Oct 14th, 2005 3:42 PM |
Linear Mode
