Welcome to the Java Programming Forums


The professional, friendly Java community. 21,500 members and growing!


The Java Programming Forums are a community of Java programmers from all around the World. Our members have a wide range of skills and they all have one thing in common: A passion to learn and code Java. We invite beginner Java programmers right through to Java professionals to post here and share your knowledge. Become a part of the community, help others, expand your knowledge of Java and enjoy talking with like minded people. Registration is quick and best of all free. We look forward to meeting you.


>> REGISTER NOW TO START POSTING


Members have full access to the forums. Advertisements are removed for registered users.

Results 1 to 1 of 1

Thread: need help figuring out what is wrong with my A* search algorithm for an 8 puzzle

  1. #1
    Junior Member
    Join Date
    Mar 2010
    Posts
    1
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Default need help figuring out what is wrong with my A* search algorithm for an 8 puzzle

    hello, this is my first post!
    I am coding an 8 puzzle program to solve any instance of the eight puzzle. An input file for this program contains an initial state and a goal state separated by a blank line. 'B' Stands for the blank in the puzzle. Top is initial bottom is goal state. For this particular instance the algorithm does not work:
    321
    4B6
    875

    123
    456
    B78

    There are many others it does not work for, this is just one. I find one thing weird is that when checking the open list for a node with the same state with a greater gcost value(level in the tree), it never has a greater cost and never gets updated with a lesser cost. Not sure if this is a problem though. The only code that you most likely have to look at is solvePuzzle() and inListWithGreaterCost(). inListWithGreaterCost() checks a list(open) to see if there is a Node with the same state with a better cost than its current level. If the gcost of the node in the list is lower, the new Node updated with the lesser cost and the old one is removed. The open list is sorted by heuristic + gcost(level of tree) on every iteration of A* algorithm to prioritize open list. Can someone please help me out, I am very stuck as it seems that i am following the algorithm's pseudocode perfectly(I have found many versions). Here is most of the code for the EightPuzzle class, it is lengthy but you will most likely have to look at those two functions i mentioned. I just wanted to post all so you will have a better reference. I'm just not so sure what is wrong with my code that is causing me to repeat states and the loop runs infinitely, can someone please help point out what is wrong? I also posted the tree and node classes for reference,Thanks!
    import java.io.*;
    import java.text.*;
    import java.util.*;
     
     
    public class EightPuzzle{
     
        //puzzle holds current state of puzzle, and goal holds goal state
        private char [][] puzzle = new char [3][3];
        private char [][] goal = new char [3][3];
     
        //moves that can be made for current puzzle state
        private ArrayList<Character> moves;
     
        //frontier for A* search, static so it doesn't need to be allocated for
        //each object, and is a member because it is used in multiple methods
        private static Tree <EightPuzzle> frontier = new Tree<EightPuzzle>();
     
        private static final int STEPCOST = 1;//cost to make a move
     
        //used to keep track of heuristic being used
        private String heuristicID = new String();
     
        //heuristic value for EightPuzzle to goal, calculated by h1 or h2
        private int heuristic;
     
        /* constructor for an EightPuzzle takes a file and saves it in a string and
         * initializes both goal and puzzle arrays in initialize function. Also gets
         * the possible moves for the current state of the EightPuzzle and
         * initializes the frontier for A* search to this object just created.
         * This is used to construct the initial state of the puzzle.
         */
        public EightPuzzle(File in, String heuristicID)
        {
            moves = new ArrayList<Character>();
            String str = buildPuzzle(in);
            this.initialize(str);
            this.getPossibleMoves();
            frontier = new Tree<EightPuzzle>(this);
            this.heuristicID = heuristicID;
            if(heuristicID.equals("h1"))
                this.heuristic = heuristic1(this.puzzle);
            else if(heuristicID.equals("h2"))
                this.heuristic = heuristic2(this.puzzle);
            else this.heuristic = heuristic1(this.puzzle);//default
        }
     
        /* constructs an EightPuzzle from the array passed in. Sets the puzzle value
         * to state and gets the possible moves for that state.
         */
        public EightPuzzle(char[][] state,String heuristicID)
        {
            moves = new ArrayList<Character>();
     
            this.puzzle = state;
            this.getPossibleMoves();
            this.heuristicID = heuristicID;
            if(heuristicID.equals("h1"))
                this.heuristic = new Integer(heuristic1(this.puzzle));
            else if(heuristicID.equals("h2"))
                this.heuristic = new Integer(heuristic2(this.puzzle));
            else this.heuristic = new Integer(heuristic1(this.puzzle));//default
        }
     
        /* copy constructor, makes a deep copy of p.
         */
        public EightPuzzle(EightPuzzle p)
        {
            for(int i = 0; i < 3; i++)//deep copy puzzle
                for(int j = 0; j < 3; j++)
                {
                    this.puzzle[i][j] = new Character(p.puzzle[i][j]);
                }
            this.moves = new ArrayList<Character>();
            final int SIZE = p.getMoves().size();
            for(int i =0; i < SIZE;i++)//deep copy moves
                this.moves.add(new Character(p.moves.get(i)));
            //point to same goal in memory, doesn't need deep copy
            this.goal = p.getGoal();
     
            if(p.heuristicID.equals("h1"))
                this.heuristic = new Integer(heuristic1(this.puzzle));
            else if(p.heuristicID.equals("h2"))
                this.heuristic = new Integer(heuristic2(this.puzzle));
            else this.heuristic = new Integer(heuristic1(this.puzzle));//default
        }
     
        //accessor method for puzzle member
        public char [][] getPuzzle()
        {
            return this.puzzle;
        }
     
        //accessor method for heuristic
        public int getHeuristic()
        {
            return this.heuristic;
        }
     
        //accessor method for goal member
        public char [][] getGoal()
        {
            return this.goal;
        }
     
        //accessor method for frontier member
        public Tree<EightPuzzle> getFrontier()
        {
            return frontier;
        }
     
        //accessor method for moves member
        public ArrayList<Character> getMoves()
        {
            return this.moves;
        }
     
        //entry point
        public static void main(String [] args)
        {
            //EightPuzzle for h1
            EightPuzzle p1 = new EightPuzzle(new File("in.txt"),"h1");
            //solve puzzle with heuristic 1 and save it in pathH1
            ArrayList<EightPuzzle> pathH1 = p1.solvePuzzle();
     
            System.out.println("Solving with heuristic h1: \n");
            final int SIZEH1 = pathH1.size();
            for(int i = 0; i < SIZEH1;i++)//print pathH1
            {
                System.out.println("Step " + i + ":");
                System.out.println(pathH1.get(i));
            }
            //EightPuzzle for h2
            EightPuzzle p2 = new EightPuzzle(new File("in.txt"),"h2");
            //solve puzzle with heuristic 2 and save it in pathH2
            ArrayList<EightPuzzle> pathH2 = p2.solvePuzzle();
     
            System.out.println("\nSolving with heurstic h2: \n");
            final int SIZEH2 = pathH2.size();
            for(int i = 0; i < SIZEH2; i++)//print pathH2
            {
                System.out.println("Step "+ i + ":");
                System.out.println(pathH2.get(i));
            }
            //write the results to out.txt
            EightPuzzle.writeResultsToFile("out.txt", pathH1,pathH2);
        }
     
        /* Writes the results for heuristics 1 and 2 to a textfile specified by the
         * string file.
         */
        public static void writeResultsToFile(String file,
                ArrayList<EightPuzzle> pathH1,ArrayList<EightPuzzle> pathH2)
        {
            try
            {
                BufferedWriter out = new BufferedWriter(new FileWriter(file));
                final int SIZEH1 = pathH1.size();
                final int SIZEH2 = pathH2.size();
                out.write("Solving with heuristic h1: \n\n");
                for(int i = 0;i < SIZEH1;i++)//write h1 results to file
                {
                    out.write("Step " + i + ":\n");
                    out.write(pathH1.get(i) + "\n");
                }
                out.write("\nSolving with heuristic h2: \n\n");
                for(int i = 0;i < SIZEH2;i++)//write h2 results to file
                {
                    out.write("Step " + i + ":\n");
                    out.write(pathH2.get(i) + "\n");
                }
                out.close();//closed the buffer
            }catch(IOException E)
            {
                E.printStackTrace();
            }
        }
     
        /*returns a string representation of the puzzle's initial state and goal 
         state from a textfile.
         */
        public String buildPuzzle(File in)
        {
            //for building a string to ouput all at once
            StringBuilder sb = new StringBuilder();
            try//buffered reader reads one line at a time
            {
                BufferedReader reader = new BufferedReader(new FileReader(in));
                try
                {
                    String line = null;
                    while((line = reader.readLine()) != null)
                    {
                        sb.append(line);
                        sb.append(System.getProperty("line.separator"));
                    }
                }
                finally{reader.close();}//close input stream
            }
            catch(IOException E)//if file not found
            {
                E.printStackTrace();
            }
            return sb.toString();
        }
     
        /*
         * Initializes the char 2-d array puzzle and goal. The string "puzzles"
         * contains the initial state, which is initialized to puzzle array, and 
         * the goal state is separated by a blank line and is initialized to the 
         * goal array
         */
        public void initialize(String puzzles)
        {
            CharacterIterator iter = new StringCharacterIterator(puzzles);
            int row = 0;//row index for puzzle and goal
            int column = 0;//column index for puzzle and goal
            char c;
            //stop iterating when row and column is equal to 3 so we can assign goal
            //after done with puzzle assignment
            for(c = iter.first();(row!=3&& column !=3);c=iter.next())
            {
                //if c is a digit or 'B', save it in puzzle
                if(Character.isDigit(c) || c == 'B')
                {
                    this.puzzle[row][column] = c;
                    if(column<2)
                        column++;
                    else
                    {
                        row++; column = 0;//reset column, new line
                    }
                }
            }
            row=column=0;//reset row and column to zero
            for(c = iter.next();(row!=3&&column!=3);c=iter.next())
            {
                //if c is a digit or 'B', save it in goal
                if(Character.isDigit(c) || c == 'B')
                {
                    this.goal[row][column] = c;
                    if(column < 2)
                        column++;
                    else
                    {
                        row++; column = 0;//reset column, new line
                    }
                }
            }
        }
     
        /* Find the possible moves for the current state of the puzzle, finds the
         * row and column indices of 'B' in the EightPuzzle and adds the
         * elements at compatible positions that can be swapped with 'B' to the
         * moves member.
         */
        public void getPossibleMoves()
        {
            //row and column index of 'B' in puzzle
            int row=0;
            int column=0;
            //find index of 'B' in
            for(int i = 0; i < 3;i++)
                for(int j = 0; j < 3; j++)
                {
                    if(puzzle[i][j] == 'B')
                    {
                        row = i; column = j; break;//break out of loop, found 'B'
                    }
     
                }
            //if 'B' is at [0][0], these are the two characters(digits) that it
            //can be switched with
            if(row == 0 && column == 0)
            {
                moves.add(puzzle[1][0]);
                moves.add(puzzle[0][1]);
            }
            else if(row == 0 && column == 1)
            {
                moves.add(puzzle[0][0]);
                moves.add(puzzle[0][2]);
                moves.add(puzzle[1][1]);
            }
            else if(row == 0 && column == 2)
            {
                moves.add(puzzle[0][1]);
                moves.add(puzzle[1][2]);
            }
            else if(row == 1 && column == 0)
            {
                moves.add(puzzle[0][0]);
                moves.add(puzzle[1][1]);
                moves.add(puzzle[2][0]);
            }
            else if(row == 1 && column == 1)
            {
                moves.add(puzzle[1][0]);
                moves.add(puzzle[0][1]);
                moves.add(puzzle[1][2]);
                moves.add(puzzle[2][1]);
            }
            else if(row == 1 && column == 2)
            {
                moves.add(puzzle[1][1]);
                moves.add(puzzle[0][2]);
                moves.add(puzzle[2][2]);
            }
            else if(row == 2 && column == 0)
            {
                moves.add(puzzle[1][0]);
                moves.add(puzzle[2][1]);
            }
            else if(row == 2 && column == 1)
            {
                moves.add(puzzle[2][0]);
                moves.add(puzzle[1][1]);
                moves.add(puzzle[2][2]);
            }
            else if(row == 2 && column == 2)
            {
                moves.add(puzzle[2][1]);
                moves.add(puzzle[1][2]);
            }
        }
     
        //returns string representation of the puzzle
        @Override
        public String toString()
        {
            //use to append each object before returning string
            StringBuilder sb = new StringBuilder();
            for(int i = 0; i < 3; i++)
                for(int j = 0; j < 3; j++)
                {
                    sb.append(puzzle[i][j]);
                    if(j==2)sb.append("\n");//end of line add a newline character
                }
            return sb.toString();
        }
     
        /* heursitic1() defines the heursitic for the 8 puzzle. It returns how many
         * misplaced characters are in the 8 puzzle.
         */
        public int heuristic1(char[][] state)
        {
            int count = 0;
            for(int i = 0; i < 3; i++)
                for(int j = 0; j < 3; j++)
                {
                    if(state[i][j] != goal[i][j])//if the character is misplaced
                        count++;
                }
            return count;
        }
     
        /*Returns the sum of the manhattan distance of each misplaced character.
         *///have not checked if this works
        public int heuristic2(char [][] state)
        {
            //sum will be sum of manhattan distances of all misplaced elements
            int sum = 0;
            for(int i = 0; i < 3; i++)//for loops to find a misplaced element
                for(int j = 0; j < 3; j++)
                {
                    if(state[i][j]!=goal[i][j])
                    {
                        //for loops for manhattan distance computation
                        for(int m = 0; m < 3; m++)
                            for(int n = 0; n < 3; n++)
                            {
                                if(state[i][j] == goal[m][n])
                                {
                                    sum += (Math.abs((m-i))
                                            +Math.abs((n-j)));
                                }
                            }
                    }
                }
            return sum;
        }
     
        /* swaps the 'B' element of the EightPuzzle with c if c is in range '1'-'8'.
         * finds the row and column indice's of 'B' and c in the puzzle and swaps
         * the two.
         */
        private EightPuzzle swap(char c)
        {
            EightPuzzle p = new EightPuzzle(this);
     
            //check if in range
            if((Character.digit(c, 10) > 0) && (Character.digit(c,10) <9))
            {
                //x is location of row of c, y is column of c, m is row of 'B',
                //and n is column of 'B'
                int x,y,m,n;
                x = y = m = n = 0;
                for(int i = 0; i < 3; i++)//find 'B' and c
                    for(int j = 0; j < 3; j++)
                    {
                        if(p.getPuzzle()[i][j] == 'B')
                        {
                            m = i; n = j;
                        }
                        if(p.getPuzzle()[i][j] == c)
                        {
                            x = i; y = j;
                        }
                    }
                //found positions of 'B' and c, so now we swap
                p.puzzle[m][n] = c;
                p.puzzle[x][y] = 'B';
     
            }
            else System.out.println("Illegal move, \'" + c +"\' is out of range!");
            return p;
        }
     
        /* Check if the current state is the goal state.
         * Checks each element to see if it matches goal[row][column]
         * if one element does not match, it returns false immediately,
         * if all match it returns true.
         */
        public boolean goalCheck()
        {
            for(int i = 0; i < 3; i++)
                for(int j = 0; j < 3; j++)
                {
                    if(puzzle[i][j] != goal[i][j])
                        return false;
                }
            return true;
        }
     
        /* solvePuzzle(String heuristic), solves the EightPuzzle using the A*
         * search algorithm with the heuristic denoted by the string passed in.
         * open is an ArrayList for the nodes that haven't been examined. closed
         * is an ArrayList for the nodes that have been examined. path holds all of
         * the nodes stored in order, so the path can be returned as the solution
         * to the EightPuzzle. the initial state is added to the open list. while
         * open isn't empty, items are dequeued from the sorted open list. open is
         * sorted by increasing heursitic values, and sorted by the method defined
         * by the heuristic passed in. The node examined is added to path, it is
         * tested to see if it is the goal state, if so path is returned. Otherwise,
         * The examined node is added to the closed list, the neighbor nodes are
         * added to the frontier with getNeighborNodes(). gcost is updated because
         * we are at a new level in the frontier. this is updated with
         * node.getData().puzzle and node.getData().moves so the program will not
         * use the moves and puzzle from the initial state. if the child node is in
         * the open or closed list with a greater cost than gcost, the cost is
         * updated in open or closed list. If the child is not in either list, it
         * is added to the open list and the while loop continues until we find a
         * solution or the open list runs out.
         */
        public ArrayList<EightPuzzle> solvePuzzle()
        {
            //Nodes that haven't been examined yet
            ArrayList<Node<EightPuzzle>> open = new ArrayList<Node<EightPuzzle>>();
            //Nodes that have been examined
            ArrayList<Node<EightPuzzle>> closed = new ArrayList
                    <Node<EightPuzzle>>();
            //Nodes that have been explored, will contain path to goal
            ArrayList<EightPuzzle> path = new ArrayList<EightPuzzle>();
            //keep track of how far down tree we are for comparing gcost's of nodes
            int gcost = 0;
            //add the root node to the open ArrayList
            open.add(frontier.getRoot());
     
            while(!open.isEmpty())
            {
                //sort by best(lowest cost) e(n) = g(n)+h(n)
                open = sort(open);
                Node<EightPuzzle> node = new Node<EightPuzzle>
                        (new EightPuzzle(open.get(0).getData()));
                //this level is STEPCOST + node's gcost
                    //gcost = STEPCOST + node.getgcost();
                this.puzzle = node.getData().puzzle;//update this
                this.moves = node.getData().getMoves();//update this
                open.remove(0);
                path.add(node.getData());//keep track of nodes visited in order
                closed.add(node);//node has been visited
                //check if we are at the goal
                if(node.getData().goalCheck())
                    return path;
                else
                {
     
                    node.getData().getNeighborNodes(node,open,closed);
                    //this level is STEPCOST + node's gcost
                    //gcost = STEPCOST + node.getgcost();
                    final int SIZE = node.getNeighbors().size();
                    for(int i = 0; i < SIZE;i++)
                    {
     
     
                        //if node in the open list with greater cost, update it
                        //with the lower cost
                        inListWithGreaterCost(open,node.getNeighbors().get(i));
                        //if it is in neither list, add it to open
                        //if node in the closed list with greater cost, update it
                        //with the lower cost
                        inListWithGreaterCost(closed,node.getNeighbors().get(i));
     
                        if(!in(open,node.getNeighbors().get(i)) &&
                                !in(closed, node.getNeighbors().get(i)))
                            open.add(node.getNeighbors().get(i));
                    }
                }
            }
            return path;
        }
     
        /* in() checks if node is in the ArrayList list. Each individual Node in the
         * list is checked by counting how many elements are the same as node for
         * that node in the list. If the count is 9, which means all elements are
         * the same, in returns true, otherwise we keep going until count = 9 or
         * the list runs out and in returns false when the list runs out because no
         * match
         */
        private boolean in(ArrayList<Node <EightPuzzle>> list, Node<EightPuzzle> node)
        {
            int count = 0;
            final int SIZE = list.size();
            for(int i = 0; i < SIZE;i++)
            {//check if this element of list is equal to node
                for(int j = 0; j < 3; j++)
                    for(int k = 0; k < 3; k++)
                        if(list.get(i).getData().puzzle[j][k] == 
                        node.getData().puzzle[j][k])
                            count++;
                if(count == 9)//the node is in list
                    return true;
            }//if not in list
            return false;
        }
     
        /* inListWithGreaterCost() starts out like in() by checking to see if it
         * is in list. If it is in the list the index is saved and the node at that
         * index's gcost is compared to the gcost passed in. If it is less than the
         * one passed in it is updated with that value and it's parent is updated
         * and is added to the frontier with node as the parent.
         */
        private void inListWithGreaterCost(ArrayList <Node<EightPuzzle>> list
                , Node<EightPuzzle> node)
        {
            int index = -1;//will be index of node in list after it is found
            final int SIZE = list.size();
            for(int i = 0;i < SIZE;i++)
            {//check if this member is in the list first, just like in
                int count = 0;
                for(int j = 0 ; j < 3; j++)
                    for(int k = 0; k < 3; k++)
                    {
                        if(list.get(i).getData().puzzle[j][k] ==
                                node.getData().puzzle[j][k])
                                count++;
                    }
                if(count == 9)
                {//only difference between in and first part of this function
                    index = i;
                    break;
                }
            }
            if(index == -1)//not found in list
                return;
            //if gcost passed in is better than the gcost in the found node
            //update the gcost of the node in the list with gcost
             else if(node.getgcost() > list.get(index).getgcost())
            {
                //remove node from current parent
                node.setgcost(list.get(index).getgcost());
                list.set(index,node);
                //list.remove(index);
     
                //list.get(index).getParent().getNeighbors().remove(list.get(index));
                //list.get(index).setgcost(gcost);//update gcost of node
                //list.get(index).setParent(node.getParent());//change the parent to node
                //append list.get(index) to  frontier
                //frontier.append(node.getParent(),list.get(index));
            }
            return;
        }
     
        /* sort() sorts list in order of increasing e(n). e(n) = h(n) + g(n).
         * sort's behavior depends on the heuristic string, if "h1", heuristic1()
         * is used to sort the list. If "h2", heuristic2() is used to sort the list.
         * This is a bubblesort method.
         */
        public ArrayList<Node<EightPuzzle>> sort(ArrayList<Node<EightPuzzle>> list)
        {
     
            boolean swapped = false;
            do
            {
                swapped = false;
                final int SIZE = list.size();
                for(int i = 0; i < SIZE-1;i++)
                {//if(e(ni) > e(ni+1) swap them
                    if((list.get(i).getData().getHeuristic()
                            + list.get(i).getgcost())
                            > (list.get(i+1).getData().getHeuristic() +
                            list.get(i+1).getgcost()))
                    {
                            //swap the two members that are out of place
                            Node<EightPuzzle> temp = new Node<EightPuzzle>
                                    (new EightPuzzle(list.get(i).getData()));
                            list.set(i, list.get(i+1));
                            list.set(i+1,temp);//.setData(new EightPuzzle(temp));
                            swapped = true;
                    }//else if it is equal, deepest node wins
                    else if((list.get(i).getData().getHeuristic()
                            + list.get(i).getgcost())
                            == (list.get(i+1).getData().getHeuristic() +
                            list.get(i+1).getgcost()))
                    {
                        if(list.get(i).getgcost() < list.get(i+1).getgcost())
                        {
                            //swap the two members that are out of place
                            Node<EightPuzzle> temp = new Node<EightPuzzle>
                                    (new EightPuzzle(list.get(i).getData()));
                            list.set(i, list.get(i+1));
                            //list.get(i).setData(new EightPuzzle
                            //(list.get(i+1).getData()));
                            list.set(i+1,temp);//.setData(new EightPuzzle(temp));
                            swapped = true;
                        }
                    }
                }
            }while(swapped);
            return list;
        }
        /* getNeighborNodes() adds the neighbor nodes of node to the frontier(tree).
         * It is done by traversing the moves element of the EightPuzzle contained
         * in node and creating a new EightPuzzle by swapping the blank with the
         * character corresponding to the index in moves.
         */
        private void getNeighborNodes(Node<EightPuzzle> node,
                ArrayList<Node<EightPuzzle>> open, ArrayList<Node<EightPuzzle>>
                closed)
        {
            final int SIZE = node.getData().getMoves().size();
            for(int i = 0; i < SIZE;i++)//traverse node.getData().getMoves
            {
                //make a new EightPuzzle by swapping the blank('B') with
                //the corresponding character in the moves ArrayList inside the
                //node's EightPuzzle member.
                EightPuzzle p = new EightPuzzle
                        (swap(node.getData().getMoves().get(i)));
                //Make a node for the new EightPuzzle
                Node <EightPuzzle> child = new Node<EightPuzzle>(p);
     
                //clear moves because the moves from node's EightPuzzle are copied
                //to the new EightPuzzle
                child.getData().moves.clear();
                child.getData().getPossibleMoves();//get the available moves
                if(!in(open,child) && !in(closed,child)){
                    child.setgcost(STEPCOST + node.getgcost());//set it's gcost
                    frontier.append(node, child);//add to the frontier
                }
            }
        }
    }
    import java.util.*;
    public class Node <E>{
        private ArrayList<Node> neighborNodes;//children of this node
        private E data;//data inside node
        private Node<E> parent;//parent of this
     
        /*gcost is the cost to get to the current level in the tree,
        must be assigned it's "real value" as tree is constructed*/
        private int gcost = 0;
        /*assign Node's data value with value passed in constructor
        we don't set gcost, it could be 1 + parent.gcost, but for root, this would
        not work*/
        public Node(E data)
        {
            neighborNodes = new ArrayList<Node>();
            this.data=data;
        }
     
        /*No data assignment, allocates memory for neighborNodes ArrayList*/
        public Node()
        {
            neighborNodes = new ArrayList<Node>();
        }
     
        //accessor method for neighborNodes ArrayList.
        public List<Node> getNeighbors()
        {
            return this.neighborNodes;
        }
     
        //accessor method for gcost
        public int getgcost()
        {
            return gcost;
        }
     
        //method for setting gcost member
        public void setgcost(int n)
        {
            gcost = n;
        }
     
        /*adds n to the neighborNodes ArrayList and sets n's parent to this.*/
        public void append(Node<E> n)
        {
            n.parent = this;
            neighborNodes.add(n);
        }
     
        /*Accessor method for the data member*/
        public E getData()
        {
            return data;
        }
     
        /*method for setting the data for the Node*/
        public void setData(E data)
        {
            this.data = data;
        }
     
        //accessor method for the parent member
        public Node<E> getParent()
        {
            return this.parent;
        }
     
        //changes the parent of the current node
        public void setParent(Node<E> parent)
        {
            //check if it has a parent, if so remove it from the parents'
            //neighborNodes ArrayList
            if(this.parent != null)
                parent.neighborNodes.remove(this);
            this.parent = parent;
            //add this to make it available in the parents neighborNode ArrayList
            parent.neighborNodes.add(this);
        }
     
    }
    import java.util.*;
    public class Tree <E>
    {
        private Node<E> root;
     
        //constructor: assigns root with data
        public Tree(E data)
        {
            root=new Node(data);
        }
        public Tree(){}//empty constructor, no data assignment
     
        //accessor method to return the root of the Tree
        public Node<E> getRoot()
        {
            return root;
        }
     
        /* Finds the parent by comparing the toString() value of parent and
         * the current Node in the frontier and making sure it is the same Node by
         * comparing the gcost of the parent to the node. If it is, the child is
         * appended to the parent. The search used is Breadth first search
         */
        public void append(Node<E> parent, Node <E> child)
        {
            //Node<E> temp = root;
            ArrayList<Node<E>> frontier = new ArrayList<Node<E>>();
            frontier.add(root);
            while(!frontier.isEmpty())
            {
                Node<E> N = frontier.get(0);//get a Node
                frontier.remove(0);
                if(N.getData().toString().equals(parent.getData().toString()) &&
                        N.getgcost() == parent.getgcost())//is this the parent?
                {
                    parent.append(child);//if yes add child
                    break;//no more work to be done!
                }
                final int SIZE = N.getNeighbors().size();
                for(int i = 0; i < SIZE;i++)//get neigbors
                    frontier.add(N.getNeighbors().get(i));
     
            }
        }
    }
    Last edited by javaman87; March 28th, 2010 at 02:32 PM. Reason: added tree and node classes


Similar Threads

  1. Genetic algorithm
    By rpsaranya in forum Algorithms & Recursion
    Replies: 2
    Last Post: March 5th, 2010, 11:00 PM
  2. breakout paddle algorithm
    By Brain_Child in forum Algorithms & Recursion
    Replies: 0
    Last Post: December 30th, 2009, 05:24 AM
  3. I have algorithm problem
    By Newoor in forum What's Wrong With My Code?
    Replies: 3
    Last Post: November 11th, 2009, 08:11 PM
  4. algorithm
    By AmmrO in forum Algorithms & Recursion
    Replies: 13
    Last Post: September 24th, 2009, 10:18 PM
  5. [SOLVED] Problem in implementation of Fifteen Puzzle with 2D Arrays
    By bruint in forum Collections and Generics
    Replies: 8
    Last Post: May 3rd, 2009, 11:37 PM