A *アルゴリズムの実装

Question

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

すべての開いているノードに優先度キュー[using array]を使用しています。私は距離が重複しているので、同じ距離/優先度を持つ複数のノードであるため、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）はジグザグです。つまり、私はある距離をまっすぐに、次にいくつかの右に、そして次に右に、そしてそちらに行って、最終的に、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; 
    } 
} 

Answer 1

スコアリング部分を変更する必要があります。今、あなたは絶対距離を計算します。代わりに、最小移動距離を計算します。あなたは一人として、それぞれの動きを数える場合は、（x、y）にしたと（dXを、dYの）に行くならば、

distance moved + (max(x,dX) - min(x,dx) + max(y,dY) - min(y,dY)) 

されるという低い値は、より高いスコアと考えられています。

このヒューリスティックは、何も途中でなければ何回動くかという推測です。

---

ヒューリスティックのいいところは、あなたがお勧めのように直線的に移動することを好む場合たとえば、あなたはこの変更を行うことができ、あなたが望む結果を得るためにそれを変更することができます：

= distance moved + (max(x,dX) - min(x,dx) + max(y,dY) - min(y,dY)) 
    + (1 if this is a turn from the last move) 

これにより、同じ方向に進む傾向のある解決策を見つけることができます。

あなたができるだけ少ないターンを強制したい場合：これは*についての素晴らしい何であるかである

= distance moved + (max(x,dX) - min(x,dx) + max(y,dY) - min(y,dY)) 
    + (1 times the number of turns made) 

- ヒューリスティック検索を通知します - あなたはまだ、常に解決策を見つけるだろうが、場合あなたが最初に見える場所に影響を与えることができる人が複数います - これはAIの動作をシミュレートするのに適しています。

---

・ダウト：どのように最初の1と第二 互いに異なる方法で計算していますか？

最初の1つは、ターンである移動に低い優先順位を付けます。 2つめのパスは、より多くのターンを持つパスに優先度を低くします。いくつかの場合（例えば、最初のターン）、値は同じになりますが、2番目のものすべてでは、できるだけターン数の少ないパスが選択されます。

また

、1これが最後の動きからのターンであれば、このために、 は今私 パスは、通常、左、左、左されるだろう、私は右下の左上の送信元と送信先を持っていると言います。 .. down、down、down .... これは最後の動きから順番になっています。これに応じて、私が を左から下に変更すると、1を追加しますか？

はい

それはダウンのために、より優先順位の合計値が減少します作る文句を言いません。

はい、正確です。最初にターンがある選択肢を見ないといいでしょう。これにより優先度が低くなり、アルゴリズムは優先度の高い他のオプションを正確に調査します。

最後に移動したときに1回移動した場合は、以前に処理したセルに隣接していないセルに移動しますか？ Thnks -

いいえ、この文脈では意味がないと思います。すべての動きが前のセルに接しなければならない、斜めの動きは許されません。あなたは私の第一及び第二の方法が異なる答えを与えるのインスタンスを伝えることができれば

---

けれども、私は本当に感謝します。できれば。どうもありがとう。 :)あなたのアルゴリズムの詳細を見ることなく

そう簡単ではないが、次はうまくいくかもしれない：

赤がブロックされています。緑は私が最初にやってくれると期待しているもので、それはローカルで最もターンを見つけようとします。青は最低のターンソリューションです。赤い領域同士がどのくらい離れているか、アルゴリズムがどのように影響するかについての詳細を確認してください。上記のように、余分なターンを持っているのはヒューリスティックで1にすぎません。 25は緑のパスで2番目にターンを乗り越えるために距離よりも大きい場合には

= distance moved + (max(x,dX) - min(x,dx) + max(y,dY) - min(y,dY)) 
    + (25 times the number of turns made) 

：あなたが確認したい場合はSO、これはこのようなヒューリスティックを変更する動作します。 （2ターン目の後、青色のパスが検索されます）