2

私はTreeSet、A* アルゴリズムの実行中に使用されるパス検索の場所を格納するための を使用しています。

基本的に、「開いている」要素が存在するまで (まだ徹底的に調査する必要があります)、すべての開いている要素の隣接要素が考慮さSortedSetれ、コストとヒューリスティック コストによって並べ替えられた に追加されます。これは、次のようなクラスがあることを意味します。

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

に追加した後、要素の「Comparable」値を変更しないように注意してください。に追加した後で値を変更すると、新しい順序を維持できなくなります。TreeSetTreeSetTreeSet

この場合、オーバーライドは必要ありませんがPathTileInfo、あなたは正しいと思います。equals()

于 2011-01-08T02:47:01.903 に答える
0

TreeSet はデフォルトで、自然な順序付けを使用して追加する要素を並べ替えます。これがあなたのケースで起こっていることです。TreeSet を作成するときにカスタム コンパレータを使用するように指示していますか?

于 2011-01-08T01:18:02.387 に答える