2

我正在使用一个TreeSet用于存储在执行 A* 算法期间使用的寻路位置的方法。

基本上，直到有“开放”元素（仍然要彻底访问），每个开放元素的邻居都会被考虑并添加到 aSortedSet中，以使它们按成本和启发式成本排序。这意味着我有一个像这样的课程：

public class PathTileInfo implements Comparable<PathTileInfo>
{
  int cost;
  int hCost;
  final int x, y;

  @Override
  public int compareTo(PathTileInfo t2) {
    int c = cost + hCost;
    int c2 = t2.cost + t2.hCost;
    int costComp = c < c2 ? -1 : (c > c2 ? 1: 0);

    return costComp != 0 ? costComp : (x < t2.x || y < t2.y ? -1 : (x > t2.x || y > t2.y ? 1 : 0));
  }

  @Override
  public boolean equals(Object o2) {
    if (o2 instanceof PathTileInfo) {
      PathTileInfo i = (PathTileInfo)o2;
      return i.cost + i.hCost == cost + hCost && x == i.x && y == i.y;
    }

    return false;
  }
}

以这种方式，首先考虑总成本，然后，由于需要总排序（与 equals 一致），因此要考虑根据 x,y 坐标的排序。

这应该有效，但如果我在算法执行期间迭代 TreeSet 就像在

for (PathTileInfo t : openSet)
  System.out.print("("+t.x+","+t.y+","+(t.cost+t.hCost)+") ");

我得到的结果没有保持正确的顺序，例如：

(7,7,6) (7,6,7) (6,8,6) (6,6,7) (5,8,7) (5,7,7) (6,7,6) ( 6,6,7) (6,5,7) (5,7,7) (5,5,8) (4,7,7) (4,6,8) (4,5,8)

我错过了什么微妙的东西吗？谢谢！

4

2 回答 2

1

请确保在添加到TreeSet. 如果添加后更改值TreeSet，TreeSet则无法保持新顺序。

我认为您PathTileInfo是正确的，尽管equals()在这种情况下不需要覆盖。

于 2011-01-08T02:47:01.903 回答
0

TreeSet 默认情况下使用自然顺序对您添加的元素进行排序，这就是您的情况。您是在告诉 TreeSet 在创建时使用您的自定义比较器吗？

于 2011-01-08T01:18:02.387 回答