2

i'm making a school project wehere we have to implement the A* algorithm to solthe the 8-puzzle problem. When creating a Node and adding it to the queue, there is no problem, but when I create a second one, and try to add it to the queue, it can't compate them both, to check wich has the lowest f-cost.

private class Node implements Comparable<Node>{
    private Node parent;
    private int distance;
    private int moves;
    private Board board;

    public Node(Node parent, Board board, int moves) {
        this.parent = parent;
        this.board = board;
        this.moves = moves;
        distance = board.manhattan();
    }

    @Override
    public int compareTo(Node node) {
        return this.moves + this.distance - node.moves - node.distance;
    }
}

this is the class where I create my Node's. Now when trying to test if this works, I created a slamm JUnit test to see if it would work, but I get the error that my Node class cannot be cast to a comparable. Here is the code of the test I'm trying to run:

import java.util.PriorityQueue;
import org.junit.Test;    

public class UnitTests {
private PriorityQueue<Node> closedPQ =  new PriorityQueue<Node>();
@Test
public void pqTest() {
    int N = 3, counter = 1;
    int[][] tiles = new int[N][N];

    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            tiles[i][j] = counter++;
        }
    }
    tiles[2][2] = 0;
    tiles[1][1] = 6;
    tiles[1][2] = 5;

    Board initial = new Board(tiles);

    tiles[1][1] = 5;
    tiles[1][2] = 6;

    Board initial2 = new Board(tiles);

 System.out.println(initial.manhattan());
 System.out.println(initial2.manhattan());

 closedPQ.add(new Node(null, initial, 0));
 closedPQ.add(new Node(null, initial2, 0));

 Node n = closedPQ.remove();
 System.out.println(n.distance);
}
}

First u just make a new board, and then change some nubers to get different costs. The error i get is when I try to add the second Node to the PQ. Anyone got an idea of how to fix this? I'm expecting that the Node with the smallest f ost is returned to me at the remove operation. This is the second Node I add to the queue, because its manhatten-score is 0, while the firsts Node's board has a manhatten-score of 0.

The Failure trace I get is:

java.lang.ClassCastException: gna.UnitTests$Node cannot be cast to   java.lang.Comparable
at java.util.PriorityQueue.siftUpComparable(Unknown Source)
at java.util.PriorityQueue.siftUp(Unknown Source)
at java.util.PriorityQueue.offer(Unknown Source)
at java.util.PriorityQueue.add(Unknown Source)
at gna.UnitTests.pqTest(UnitTests.java:100)
8
  • Post a stacktrace.
    – Roman C
    Apr 16, 2016 at 9:58
  • Do you mean a Failure Trace? edited it in
    – Milebril
    Apr 16, 2016 at 10:00
  • It doesn't help that we can't see the declaration of closedPQ. Please add a minimal reproducible example rather than just snippets. (Hint: with the exception you're getting, none of the board parts are actually relevant...)
    – Jon Skeet
    Apr 16, 2016 at 10:05
  • This still isn't a minimal reproducible example. We want to be able to copy, paste, compile and run. It sounds like either you're using the wrong Node class, or something else odd is going on. Is the Node class you've shown us really a nested type in UnitTests?
    – Jon Skeet
    Apr 16, 2016 at 10:19
  • The Node class is officialy in my Solver.java, but took it and out it in my UnitTests, and okay, now I got what you want, i'm on it!
    – Milebril
    Apr 16, 2016 at 10:23

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.