序文
A*検索アルゴリズムは、一般にA-STARアルゴリズムとして知られています。これは、グラフ平面上に複数のノードを備えたアルゴリズムで、最低の合格コストを見つけます。ゲームで一般的に使用されます
2次元配列を介して構築された迷路「％」は壁を表し、Aは出発点、Bはエンドポイント、 "＃"は障害を表し、「*」はアルゴリズムによって計算されたパスを表します。
この記事のコード構造：
％％％％％％％％％OOOO％OO＃OO％％A O＃O B％％OO＃OO％OOOO％％％％％％％ ======================================================================================================================= oo * oo％％o *＃ * o％％a o＃o b％oo＃oo％oo％％％％％％<
アルゴリズム理論
アルゴリズムのコア式は次のとおりです。F= g+h
マップ上のノードをグリッドと考えてください。
g =生成されたパスに沿った開始点Aからグリッド上の指定されたノードに移動する移動消費。この例では、水平または垂直の動きコスト10を作成し、対角線方向は14になります。
距離は、ルート番号2または水平または垂直に移動するために取られた量の約1.414倍です。簡単にするために、10と14を使用して近似します。
特定の経路に沿って正方形につながるG値を計算しているため、評価の方法は、親ノードのG値を取得し、親ノードに対する対角方向または直角（非対角角）に従ってそれぞれ14と10を追加することです。例では、これ
各メソッドの需要は、開始グリッドの外側から複数の正方形を取得したため、より多くなります。
h =現在のグリッドからエンドポイントBまでの推定移動消費はなぜ「推定」と呼ばれるのですか？事前にパスの長さを知る方法がないからです。ここでは、現在のグリッドから宛先グリッドまでの水平および垂直を計算するマンハッタン法を使用します。
斜めの方向を無視して、正方形の正方形の数の合計。次に、結果に10を掛けます。
fの値はgとhの合計であり、これは優先パスを判断するために使用する標準です。 Fの最小値を持つグリッドは、優先パスノードと見なされます。
実装手順
アルゴリズムはJavaで記述され、最初にノードクラスの内容を見てください
パッケージa_star_search; / ** * node class * @author zx * */ public class node {private int x; // Xはプライベートインターを調整します。 // yはプライベート文字列値を調整します。 //ノードプライベートダブルfValue = 0の値; // f値private double gvalue = 0; // g値プライベートダブルHバリュー= 0; // H値プライベートブールンリーチブル; //到達可能ですか（それは障害物ですか）プライベートノードpnodeです。 //親ノードパブリックノード（int x、int y、string value、boolean reachable）{super（）; this.x = x; this.y = y; this.value = value; Reachable = Reachable; } public node（）{super（）; } public int getX（）{return x; } public void setx（int x）{this.x = x; } public int gety（）{return y; } public void sety（int y）{this.y = y; } public string getValue（）{return値; } public void setValue（string value）{this.value = value; } public double getFalue（）{return fvalue; } public void setFValue（double fvalue）{fvalue = fvalue; } public double getGValue（）{return gValue; } public void setGValue（double gValue）{gValue = gValue; } public double gethvalue（）{return hvalue; } public void sethvalue（double hvalue）{hvalue = hvalue; } public boolean isReachable（）{Return Reachable; } public void setReachable（boolean Reachable）{Reachable = Reachable; } public node getpnode（）{return pnode; } public void setpnode（node pnode）{pnode = pnode; }}マップクラスも必要です。マップ構築方法では、開始点とエンドポイントを含む2次元のノードを作成して迷路マップを実装します。
パッケージa_star_search; public class map {private node [] [] [] map; // node array private node startnode; //開始プライベートノードendnode; // end point public public map（）{new node [7] [7]; for（int i = 0; i <7; i ++）{for（int j = 0; j <7; j ++） node（i、j、 "o"、true）;}} for（int d = 0; d <7; d ++）{map [0] [d] .setValue（ "％"）; map [0] [d] .setReachable（false）; map [d] [0] .setValue（ "％"）; map [d] [0] .setReachable（fal se）; map [6] [d] .setValue（ "％"）; map [d] [6] .setValue（ "％"）; map [d] [6] .setReachable（false）;} Map [3] [1] .setValue（ "a"）; startNode = map [3] [1]; map [3] [5] .setValue（ "b"）; endnode = map = map [3] [5]; for（int k = 1; k <= 3; k ++）{map [k+1] [3] .setvalue（ "＃"）; map [k+1] [3] .setreachable（span> </span = </</</</</</</span = "> <pibleachable）; void showmap（）{for（int i = 0; i <7; i ++）{for（int j = 0; j <7; j ++）{system.out.print（map [i] [j] .getvalue（）+""） setMap（node [] [] map）{this.map = map;} public node getStartNode（）{return startNode;} public void setStartNode（node startNode）{this.startnode = startnode;} public node getEndnode（）{return endnode;} public void setendnode（ endnode;}}これが最も重要なAstarクラスです
操作プロセス
1開始点Aから始めて、保留中のポイントとして「オープンリスト」に保存します。これは、チェックする正方形のリストです。
2開始点の周りにアクセス可能なすべての正方形または通過可能な正方形を見つけて、控えめな正方形をスキップします。それらをオープニングリストにも追加します。これらすべてのグリッドのポイントAを「親グリッド」として保存します。パスを説明したいとき、親の広場
素材は非常に重要です。その特定の目的については後で説明します。
3オープンリストから開始点Aを削除し、「閉じるリスト」に追加して、再度チェックする必要のないすべての正方形を保存します。
上記の手順の後、「オープンリスト」には、障害物を除いて、出発点Aの周りのすべてのノードが含まれています。彼らの親ノードはすべてAです。前述の式f = g+hを通じて、各ノードのg、h、fの値を計算し、fの値に従って、それらは小さいです
大規模にソート。そして、最小のf値でノードで次の操作を行います
4。オンリストから削除し、オフリストに追加します。
5.隣接するすべてのグリッドを確認します。渡されないものをスキップし（1。「閉じる」、2。障害物で）、まだ存在していない場合はオープンリストに追加します。選択した正方形を新しい正方形の親ノードとして取ります。
6.隣接するグリッドがすでにオープンリストにある場合は、現在のパスの方が良いかどうかを確認してください。つまり、新しいパスで到達した場合、G値が低くなるかどうかを確認します。そうでない場合は、何もありません
する。 （ここでは、私のコードには判断がありません）
7.ターゲットグリッド（エンドポイント「B」）が「オープンリスト」に追加されるまでこのプロセスを繰り返し、エンドポイントBがすでに「クローズリスト」に追加された前のノードの周りにあることを示します。エンドポイントBに到達するには、1つのステップを踏むだけです。
8。エンドポイントBを「クローズリスト」に追加します
9。最後のステップでは、出発点AからエンドポイントBまでのパスを表す必要があります。親ノードの役割が表示されます。 「リストを閉じる」のエンドポイントノードの親ノードの値を変更することにより、手がかりに従ってパスを表示できます。
コードをチェックしてください
パッケージa_star_search; Import java.util.arraylist; public class astar {/*** arraylist配列を「オープンリスト」および「クローズリスト」として使用します*/arraylist <node> open = new arraylist <node>（）; arraylist <node> close = new arraylist <node> new rund********** endnode：end point* @return*/public double gethvalue（node currentnode、node endnode）{return（math.abs（currentnode.getx（） - endnode.getx（）） + math.abs（currentnode.get.get（） - endnode.gety（））* 10;} getGValue（node currentNode）{if（currentNode.getPnode（）！= null）{if（currentNode.getX（）== currentNode.getPnode（）。getx（） currentNode.getGValue（）+10;} return currentNode.getGValue（）+14;} return currentNode.getGalue（）;}/** * get f値：g+h * @param currentnode * @return */public double getFalue（node currentnode）{return currentnode.getgvalue選択したノードの「オープンリスト」 * @param node * @param map */public void inopen（node node、map map）{int x = node.getx（）; int y = node.get（）;閉じたリストではなく障害物）、冒頭リストは含まれておらず、選択されていませんif（map.getMap（）[x-1+i] [y-1+j] .isreachable（）&&！open.contains（map.getmap（）[x-1+i] [y-1+j]＆ ＆！（x ==（x-1+i）&& y ==（y-1+j）））{map.getmap（）[x-1+i] [y-1+j] .setpnode（map.getmap（）[x] [y]）; // the選択したノードは、親ノードmap.getMap（）[x-1+i] [y-1として使用されます+j] .SetGValue（getGValue（map.getMap（）[x-1+i] [y-1+j]））; map.getMap（）[x-1+i] [y-1+j] .sethvalue（gethvalue（map.getMap（）[x-1+i] [y-1+j]、map.ge tendnode（）））; map.getMap（）[x-1+i] [y-1+j] .setfvalue（getf.getmap（）[x-1+j]）; open.add（map.getmap（）[x-1+i] [y-1+j];}}}}/*****（ *オープンリストのノードを小さいものからf値まで並べ替えます * @param arr */public voidソート（arraylist <node> arr）{for（int i = 0; i <arr.size（） - 1; i ++）{for（int j = i+1; j <arr.size（）; j ++）{if（arr.get（i）.getfval（）>> arr.get（j）.getfvalue（））{node tmp = new node（）; tmp = arr.get（i）; arr.set（i、arr.get（j））; arr.set（j、tmp）;}}}/** *ノードを「閉じるリストにノードを追加」 open）{if（open.Contains（node））{node.setReachable（false）; // set uneachable open.remove（node）; close.add（node）;}} public void search（map map）{//出発点の周りにノードを操作します。 inopen（map.getMap（）[map.getStartNode（）。getX（）] [map.getStartNode（）。gety（）]、map）; close.add（map.getMap（）[map.getStart node（）。getx（）] [map.getStartNode（）。getX（）] [map.getStartNode（）。gety（）]; map.getMap（）[map.getStartNode（）。getX（）] [map.g etstartnode（）。gety（）]。setReachable（false）; map.getMap（）[map.getStartNode（）。getX（）] [map.getStartNode（）。gety（） {inopen（open.get（0）、map）; inclose（open.get（0）、open）; sort（open）;} while（！open.contains（map.getMap（）[map.getNnode（）。getx（）。 inclose（map.getmap（）[map.getendnode（）。getx（）] [map.getendnode（）。gety（）]、open）; showpath（close、map）;}/** * @param arr * @param map */public void showpath（arraylist <node> arr、map）{node node odize（node） node（）; // <span style = "pre"> </span> node = map.getMap（）[getx（）] [map.getNnode（）。 == getStartNode（）。gety（）））{// <span style = "> </span> node.getPnode（）。setValue（"*"）; style = "white-space：pre"> </span> map.getMap（）[map.getStartNode（）。getX（）] [map.getStartNode（）。gety（）]。setValue（ "a"）;}}}}最後にメイン方法を書きます
パッケージa_star_search; public class maintest {public static void main（string [] args）{map map = new Map（）; Astar Astar = new Astar（）; map.showmap（）; astar.search（map）; System.out.println（ "================================================================================= ====================================================================================================================================== ====================================================================================================================================== ========================================================================================================== map.showmap（）;マップを変更してテストして効果を確認します
％％％％％％％％％OOOO％OO＃OO％％A O＃O B％％OO＃OO％OOOO％％％％％％％％ ======================================================================================================================================================== ％％％％％
要約します
最短パス（最適解）が見つかるようにするために、鍵はターゲットノードへの推定値h（n）<= nの実際の距離値h（n）の選択にあります。この場合、検索された多くのポイントがあり、検索範囲は大きく、効率は低いです。しかし、得ることができます
最適なソリューション。推定値>実際の値>実際の値の場合、ポイントの検索数は小さく、検索範囲は小さく、効率が高くなりますが、最適なソリューションが得られることを保証することはできません。
最大の感覚は、ネットを乾燥させてから3日間と2日間の釣りで最もタブーなことです。量は大きくないかもしれませんが、継続性でなければならず、鍵は永続性です。
すべてのプログラマーがコードを喜んで入力し、彼がやりたいことをすることができることを願っています。
上記は、JavaプログラミングとA*アルゴリズムの完全なコードの実装に関するこの記事のすべての内容です。私はそれが誰にでも役立つことを願っています。興味のある友人は、このサイトの他の関連トピックを引き続き参照できます。欠点がある場合は、それを指摘するためにメッセージを残してください。