Javaの二分ヒープ（ソートされていない）

Question

は、私は*アルゴリズムのためにヒープのこの実装を使用しています：

https://courses.cs.washington.edu/courses/cse373/11wi/homework/5/BinaryHeap.java

私は少し、それを修正だけcontainsメソッドを追加し、pollにremoveの名前を変更します以前はPriorityQueueを使用していたため動作しませんでした。

1. 176.0 
2. 175.0 
3. 180.0 
4. 176.0 
5. 223.0 
6. 182.0 
7. 146.0 
8. 177.0 
9. 87.0 
10. 202.0 
... 

：私はこれを参照してくださいすべての getF()秒でヒープを印刷するとき

@Override 
public int compareTo(Spot o) { 
    Double.compare(getF(), o.getF()); 
} 

getF()戻り、二重...しかし

：ここ

は Comparable<Spot>インタフェースの私の実装です

175は176よりも低いので間違っています、87も間違っています...

PriorityQueueとまったく同じことが起こったのですが、何が間違っていますか？

public List<Spot> process(GameBodyObject me, Point target, ArrayList<GameBodyObject> others) throws Exception { 

    if(grid == null) { 
     throw new Exception("You have to initialize AStar first."); 
    } 

    grid.unsetObstacleForObject(me); 

    Spot start = grid.getSpotAtPosition(me.getPosition().getX(), me.getPosition().getY()); 
    Spot end = grid.getSpotAtPosition(target.getX(), target.getY()); 

    end = grid.moveSpotSoThatItDoesntCollide(end, me.getRadius()); 

    Heap<Spot> openSet = new Heap<Spot>(grid.getMaxSize()); 
    List<Spot> closedSet = new ArrayList<>(); 
    List<Spot> path = new ArrayList<>(); 

    openSet.add(start); 

    while(openSet.size() > 0) { 

     /*int winner = 0; 
     for(int i = 1; i < openSet.size(); i++) { 
      if(openSet.get(i).getF() < openSet.get(winner).getF()) { 
       winner = i; 
      } 
     }*/ 

     Spot current = openSet.poll(); //openSet.get(winner); 

     int i = 1; 
     for(Spot s : Arrays.asList(openSet.getArray())) { 
      if(s != null) { 
       System.out.println(i + ". " + s.getF()); 
       i++; 
      } 
     } 

     if(current.equals(end)) { 
      // We are done, reconstruct the path... 
      Spot temp = current; 
      path.add(temp); 
      while(temp.getPrevious() != null) { 
       path.add(temp.getPrevious()); 
       temp = temp.getPrevious(); 
      } 

      grid.resetObstacles(); 
      return path; 
     } 

     closedSet.add(current); 

     List<Spot> neighbors = current.getNeighbors(); 

     for(Spot neighbor : neighbors) { 
      if(!closedSet.contains(neighbor) && !grid.isCollidingWithObstacle(neighbor, me.getRadius())) { 
       double tempG = current.getG() + 1; 
       if(openSet.contains(neighbor)) { 
        if(tempG < neighbor.getG()) { 
         neighbor.setG(tempG); 
        } 
       } else { 
        neighbor.setG(tempG); 
        openSet.add(neighbor); 
       } 

       neighbor.setH(heuristic(neighbor, end)); 
       neighbor.setF(neighbor.getG() + neighbor.getH()); 
       neighbor.setPrevious(current); 
      } 
     } 

    } 

    grid.resetObstacles(); 
    return new ArrayList<>(); 
} 

Answer 1

ダイクストラまたは*アルゴリズムを実装するJavaの優先度つきキューまたは類似のヒープ実装を使用して共通の問題がdecreaseKey法の欠落である：

EDIT は、ここに私のA *実装です。 DijkstraまたはA *は、ヒープに挿入された要素の優先度を変更する必要があることがあります。この機能の欠落を回避する唯一の方法は、要素（JavaのPriorityQueue実装では遅い要素）を削除してから、再度挿入することです。

しかし、これには1つの問題があります：PQ /ヒープからオブジェクトを削除するときには、 "古い"優先度が含まれていなければなりません（getF()はあなたのケースで古い値を返さなければなりません）見つけられた。要素に既に新しい値が含まれている場合、PQ /ヒープは古い値に一致する場所ではなく、削除する新しい場所でPQ /ヒープを探します。

したがって、シーケンスは、（1）PQから要素を削除し、（2）その重み/優先度を適用し、（3）PQに再挿入する必要があります。あなたのコードで

、あなたは以下の部分があります：あなたはそれをよく見ると

  if(openSet.contains(neighbor)) { 
       if(tempG < neighbor.getG()) { 
        neighbor.setG(tempG); // *1 
       } 
      } else { 
       neighbor.setG(tempG); 
       openSet.add(neighbor); 
      } 

      neighbor.setH(heuristic(neighbor, end)); 
      neighbor.setF(neighbor.getG() + neighbor.getH()); // *2 
      neighbor.setPrevious(current); 

を、あなたはラインでneighborの重量を変更するため、ライン*1の変化に*2をマーク。それを修正するには、次のことを試みることができる：それはすでにそこ（*3）だと重量が正しく（*4、*5を）計算された後にのみ、それを挿入した場合

  if(openSet.contains(neighbor)) { 
       if(tempG < neighbor.getG()) { 
        openset.remove(neighbor); // *3 
        neighbor.setG(tempG); 
       } 
      } else { 
       neighbor.setG(tempG); 
       // openSet.add(neighbor); // *4 
      } 

      neighbor.setH(heuristic(neighbor, end)); 
      neighbor.setF(neighbor.getG() + neighbor.getH()); 
      openSet.add(neighbor); // *5 
      neighbor.setPrevious(current); 

これは、ヒープから要素を削除します。

問題が発生しました：ヒープ実装では、このようなremove(Object)メソッドは提供されていません。 JavaのPriorityQueue does。したがって、JavaのPriorityQueueまたはremove(Object)メソッドを提供する別のヒープ実装に変更する必要があります。 （あるいは、さらに良い方法：decreaseKeyメソッドなので、要素を取り除く必要はありません）。

多くのDijkstra/A *実装では、JavaのPQを使用していましたが、これは最初の試みでは間違って行われ、ヒープの順序が正しくありません。

tl; dr： PriorityQueueまたはヒープに既に挿入されている要素の重み付け/優先度を変更しないでください。