即使在实现Comparator之后，TreeSet对象删除也不起作用

Question

我试图用Eclipse在Java中实现AStar算法。我在图表中的位置由对象表示。我使用TreeSet来存储位置，并为对象特定的排序实现了比较器。但是在一行中，代码应该从TreeSet中删除当前对象，这不起作用。我设法使用pollFirst（）代替，算法工作。但是我找不到treeSet.remove（Object）不起作用的原因。

我添加了boolean equals和compareTo。两者都是真的，所以根据equals和compareTo current等于openSet.first（）但是openSet.remove（current）无法从openSet中删除当前值

我添加了整个代码！我在带有大量测试用例的代码检查中对它进行了测试，因此如果我使用pollFirst（）而不是remove（current），代码就可以工作

编辑：在阅读JavaDoc for Set Interface（https://docs.oracle.com/javase/7/docs/api/java/util/Set.html）后，我发现了以下警告：

如果将可变对象用作集合元素，则必须非常小心。如果在对象是集合中的元素的同时以影响等于比较的方式更改对象的值，则不指定集合的​​行为。

我怀疑这与我的问题有关。但是，当我用openSet.pollFirst（）替换openSet.remove（current）时程序的工作原理仍然很奇怪

编辑2：我根据Loris Securo的建议更改了比较器。不幸的是它仍然没有用

public class Finder implements Comparable<Finder> {

public int i; // All integers are initialized to zero.
public int j;
public int id;
public int fScore; 
public int gScore;
public ArrayList<Finder> neighbours = new ArrayList<Finder>();
public Object character;

@Override
public String toString() {
    return "Finder [i=" + i + ", j=" + j + ", gScore=" + gScore + ",fScore =" + fScore + ", id=" + id
            + ", character=" + character + "]";
}

public static void main(String[] args) {


    String a = "......\n" + "......\n" + "......\n" + "......\n" + "......\n" + "......";
    Object[] mazeParts = a.split("\n");
    System.out.println("mazeParts is " + Arrays.toString(mazeParts));
    Object[][] maze = new Object[mazeParts.length][];

    int r = 0;
    for (Object t : mazeParts) {
        System.out.println("t is " + t);
        maze[r++] = ((String) t).split("");
    }
    Finder[][] mazeOfnodes = new Finder[mazeParts.length][maze[0].length];
    int id = 0;
    for (int i = 0; i < maze.length; i++) {
        for (int j = 0; j < maze[i].length; j++) {
            System.out.println("maze" + i + j + " is " + maze[i][j]);
            Finder node = new Finder(); 
            node.character = maze[i][j];
            node.i = i;
            node.j = j;
            node.id = id;
            mazeOfnodes[i][j] = node;
            id++;
            if (i == 0 && j == 0) {
                node.fScore = heuristic(i, j, mazeOfnodes);
                node.gScore = 0;
            } else {
                node.fScore = Integer.MAX_VALUE;
                node.gScore = Integer.MAX_VALUE;
            }
        }
    }
    for (int i = 0; i < mazeOfnodes.length; i++) { 
        for (int j = 0; j < maze[i].length; j++) {
            mazeOfnodes[i][j].neighbours = mazeOfnodes[i][j].findNeighbours(i, j, mazeOfnodes);
            System.out.println("mazeOfnodes is " + mazeOfnodes[i][j]);
        }
    }


}

public static int findWay(Finder[][] myMaze) {
    Finder goal = myMaze[myMaze.length - 1][myMaze.length - 1];
    TreeSet<Finder> openSet = new TreeSet<Finder>();
    openSet.add(myMaze[0][0]);
    TreeSet<Finder> closedSet = new TreeSet<Finder>();
    while (openSet.size() != 0) {
        Finder current = openSet.first();
        if (current == goal) {
            return current.gScore;
        }
        boolean equals = current.equals(openSet.first());
        boolean compareTo = (current.compareTo(openSet.first()) == 0);
        openSet.remove(current); //if I use openSet.pollFirst() the code   works fine. I tested it on Codewars with several huge test cases
        boolean success = openSet.remove(current);
        System.out.println("success is " + success);

        closedSet.add(current);
        for (Finder s : current.neighbours) {
            if (closedSet.contains(s)) {
                continue;
            }
            int tentative_gScore = current.gScore + 1;
            if (tentative_gScore >= s.gScore) {
                continue;
            }
            s.gScore = tentative_gScore;
            s.fScore = s.gScore + heuristic(s.i, s.j, myMaze);
            if (!openSet.contains(s) && !s.character.equals("W")) {
                openSet.add(s);
            }
        }
    }
    return -1;
}

private ArrayList<Finder> findNeighbours(int i, int j, Finder[][] maze) {
    if (i > 0) {
        neighbours.add(maze[i - 1][j]);
    }
    if (i < maze.length - 1) {
        neighbours.add(maze[i + 1][j]);
    }
    if (j < maze.length - 1) {
        neighbours.add(maze[i][j + 1]);
    }
    if (j > 0) {
        neighbours.add(maze[i][j - 1]);
    }
    return neighbours;
}

public static int heuristic(int i, int j, Object[][] mazeFinal) {
    int distance = (int) Math.sqrt(Math.pow(mazeFinal.length - 1 - i, 2) + Math.pow(mazeFinal.length - 1 - j, 2));
    return distance;


    public int compareTo(Finder2 arg0) {
    if (this.fScore < arg0.fScore) {
        return -1;
    } else if (this.id == arg0.id) { // If id is the same, fScore is the same too
        return 0;
    } else if (this.fScore == arg0.fScore) { //If id is different, fScore could still be the same
        return 0;
    } else {
        return 1;
    }
}

Answer 1

你的compareTo方法在TreeSet上不能正常工作，因为它不符合A> B然后B <A的规则。

在你的情况下，如果fScore等于（和id不同）那么A> B，但也B> A.

TreeSet由基于compareTo方法构建的自平衡二叉树支持。

由于这种不一致性，树可能无法找到特定对象，因为它无法正确选择在左侧分支或右侧分支上执行搜索。

例如，如果您有3个对象A，B和C具有相同的fScore：

1. 你添加A，现在它是根
2. 然后你添加B，compareTo说它大于A，所以它可以生成这个树（现在根是B）：

     B
    /
   A

3. 然后你添加C，compareTo说它大于B，所以它可以生成这个树：

     B
    / \
   A   C

4. 现在你要删除A，它存在，但是，使用比较器，A大于B，所以树检查右分支，在那里它找到C并且它停止，所以该方法无法找到并删除A

pollFirst可以简单地选择最左边的对象，因此它总是能够删除某些东西，但被删除的对象将取决于实现。

这个问题也在这篇博客文章中讨论过：Algosome - Java: The misouse of a TreeSet基于这个论坛帖子：Java Programming Forum - TreeSet contains(obj) doe not behave as expected。