6

そこで、C で A* アルゴリズムを実装しています。手順は次のとおりです。

開いているすべてのノードに対して [配列を使用して] プライオリティ キューを使用しています。重複した距離、つまり同じ距離/優先度を持つ複数のノードがあるため、PQ にノードを挿入するときに、挿入されたノードの親の優先度が同じ場合は、両方を交換します。入力したメンバーは一番上（またはできるだけ高い位置）にとどまり、特定の方向をたどり続けます。また、削除時に、一番上の要素を最後の要素と交換すると、交換された最後の要素がその子の 1 つと同じである場合、一番下に交換されます。(これが影響するかどうかはわかりません)いずれにせよ）。

問題は、100*100 の行列があり、移動している 2D 配列の (0,20) から (15,20) までの障害があるとします。開始位置 (2,2) と終了位置 (16,20) の場合、直線パスが得られます。つまり、最初に右に完全に移動し、次に 15 まで下ってから右に 1 つ移動すると完了です。

しかし、(2,2) として開始し、(12,78) として終了した場合、つまり、ポイントが障害物で区切られていて、パスがそれを迂回する必要がある場合でも、(16,20) を経由し、その後のパスを通過します。 (16,20) はまだ直線ですが、(16,20) までの経路はジグザグです。つまり、ある距離をまっすぐ下に移動し、次に右に移動し、次に下に移動して右に移動し、最終的に (16,20) に到達し、その後直行。

距離の前半がこのジグザグ パスである理由は、目的地が (16,20) であり (12,78) ではない場合、パスがそのままの状態でまっすぐであることを確認するにはどうすればよいかということです。

ありがとう。

void findPath(array[ROW][COLUMN],sourceX,sourceY,destX,destY) {
  PQ pq[SIZE];
  int x,y;

  insert(pq,sourceX,sourceY);

  while(!empty(pq)) {
    remove(pq);
    if(removedIsDestination)
        break;                  //Path Found
    insertAdjacent(pq,x,y,destX,destY);
  }
}

void insert(PQ pq[SIZE],element){
  ++sizeOfPQ;
  PQ[sizeOfPQ]==element
  int i=sizeOfPQ;
  while(i>0){
    if(pq[i].priority <= pq[(i-1)/2].priority){
      swapWithParent
      i=(i-1)/2;
    }
    else
      break;
  }
}
4

1 に答える 1