Я пытался реализовать алгоритм AStar в Java с Eclipse. Мои позиции на графике представлены объектами. Я использую TreeSet для хранения позиций и реализовал компаратор для конкретной сортировки объектов. Однако в одной строке код должен удалить текущий объект из TreeSet, который не работает. Мне удалось использовать pollFirst () вместо этого, и алгоритм работал. Однако я не смог найти причину, по которой treeSet.remove (Object) не должен работать.
Я добавил логическое равенство и сравнение. Оба имеют значение true, поэтому согласно equals и currentTo current равен openSet.first (), однако openSet.remove (current) не может удалить ток из openSet
Я добавил весь код! Я тестировал его на кодовых войнах с огромными тестовыми примерами, поэтому код работает, если я использую pollFirst () вместо remove (current)
Редактировать: после прочтения JavaDoc для Set Interface (https://docs.oracle.com/javase/7/docs/api/java/util/Set.html) я обнаружил следующее предупреждение:
Следует соблюдать особую осторожность, если в качестве заданных элементов используются изменяемые объекты. Поведение набора не указывается, если значение объекта изменяется таким образом, что это влияет на сравнение равных, в то время как объект является элементом в наборе.
Я подозреваю, что это связано с моей проблемой. Однако все еще странно, почему программа работает, когда я заменяю openSet.remove (current) на openSet.pollFirst ()
Edit2: я сменил компаратор в соответствии с предложениями Лориса Секуро. К сожалению, это все еще не работает
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;
}
}