Kata pengantar
Algoritma pencarian A* umumnya dikenal sebagai algoritma A-STAR. Ini adalah algoritma yang memiliki banyak node pada bidang grafik untuk menemukan biaya kelulusan terendah. Biasa digunakan dalam game
Labirin yang dibangun melalui array dua dimensi, "%" mewakili dinding, A adalah titik awal, B adalah titik akhir, "#" mewakili hambatan, dan "*" mewakili jalur yang dihitung oleh algoritma
Struktur kode artikel ini:
% % % % % % % % % % oooo % oo # oo % % a o # o b % % oo # oo % % oooo % % % % % % % =============================================================================================================================================== OO * oo % % o * # * o % % a o # b % % oo # oo % % oo % % % % % % % % <
Teori Algoritma
Formula inti dari algoritma adalah: f = g+h
Pikirkan node di peta sebagai kisi.
G = Konsumsi gerakan bergerak ke simpul yang ditentukan pada kisi dari titik awal A di sepanjang jalur yang dihasilkan. Dalam contoh ini, kami membuat biaya gerakan horizontal atau vertikal 10 dan biaya arah diagonal 14. Kami mengambil nilai -nilai ini karena kami berada di sepanjang diagonal
Jarak adalah nomor akar 2 atau sekitar 1,414 kali jumlah yang diambil untuk bergerak secara horizontal atau vertikal. Untuk kesederhanaan, kami mendekati menggunakan 10 dan 14.
Karena kami menghitung nilai G yang mengarah ke kuadrat di sepanjang jalur tertentu, metode evaluasi adalah untuk mengambil nilai G dari simpul induknya, dan kemudian menambahkan 14 dan 10 masing-masing sesuai dengan arah diagonal atau sudut kanan (non-diagonal) relatif terhadap simpul induk. Dalam contoh, ini
Permintaan untuk setiap metode menjadi lebih karena kami telah memperoleh lebih dari satu kotak dari luar jaringan awal.
H = Perkiraan konsumsi gerakan dari kisi saat ini ke titik akhir B. Mengapa disebut "estimasi"? Karena kita tidak punya cara untuk mengetahui panjang jalan terlebih dahulu. Di sini kita menggunakan metode Manhattan, yang menghitung horizontal dan vertikal dari kisi saat ini ke kisi tujuan.
Jumlah jumlah kotak kotak, mengabaikan arah diagonal. Kemudian lipat gandakan hasilnya dengan 10.
Nilai F adalah jumlah G dan H, yang merupakan standar yang kami gunakan untuk menilai jalur prioritas. Kisi dengan nilai f terkecil dianggap sebagai simpul jalur prioritas.
Langkah Implementasi
Algoritma ini ditulis dalam java, lihat konten kelas node pertama
paket a_star_search; / ** * Node kelas * @author zx * */ node kelas publik {private int x; // x mengoordinasikan int y pribadi; // y mengoordinasikan nilai string pribadi; // Nilai node private fvalue ganda = 0; // F Nilai Private GLOBER GVALUE = 0; // G nilai hvalue ganda pribadi = 0; // h nilai boolean pribadi dapat dijangkau; // Apakah dapat dijangkau (apakah itu hambatan) simpul pribadi pnode; // node node publik (int x, int y, nilai string, boolean dapat dijangkau) {super (); this.x = x; this.y = y; this.value = nilai; Dapat dijangkau = dapat dijangkau; } node publik () {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 () {nilai kembali; } public void setValue (nilai string) {this.value = value; } public double getFvalue () {return fvalue; } public void setFvalue (double fvalue) {fvalue = fvalue; } public double getGValue () {return gValue; } public void setGvalue (gound gValue) {gValue = gValue; } public double getHValue () {return hValue; } public void setHvalue (double hValue) {hvalue = hvalue; } public boolean isReachable () {return dapat dijangkau; } public void setReachable (boolean dapat dijangkau) {dijangkau = jangkauan; } node publik getPnode () {return pnode; } public void setPnode (node pNode) {pnode = pNode; }}Juga membutuhkan kelas peta. Dalam metode konstruksi peta, saya mengimplementasikan peta labirin dengan membuat array dua dimensi node, yang mencakup titik awal dan akhir.
Paket a_star_search; peta kelas publik {private node [] [] peta; // node array node private startNode; // mulai node private endnode; // end point peta peta () {peta = node baru [7] [7]; untuk (int i = 0; i <7; i ++) {for (int j = 0; j <7; j <7; j <7; i <7; i ++ Node (i, j, "o", true);}} untuk (int d = 0; d <7; d ++) {peta [0] [d] .setValue ("%"); peta [0] [d] .setreachable (false); peta [d] [0] .setValue ("%"); peta [d] [0] .setreachable (fal se); peta [6] [d] .setValue ("%"); peta [d] [6] .setValue ("%"); peta [d] [6] .Setreachable (false);} peta [3] [1] .setValue ("a"); startNode = peta [3] [1]; peta [3] [5] .setValue ("b"); endnode = peta [3] [5]; untuk (int k = 1; k <= 3; k ++) {peta [k+1] [3] .setValue ("#"); peta [k+1] [3]. peta public void showMap () {for (int i = 0; i <7; i ++) {for (int j = 0; j <7; j ++) {System.out.print (peta [i] [j] .getValue ()+");} System.out.println (" ");}} node public () (] (] {{{{oMaP;"); 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(Node endNode) {this.endNode = endnode;}}Berikut adalah kelas Astar yang paling penting
Proses operasi
1 Mulai dari titik awal A dan simpan sebagai titik tertunda ke "daftar terbuka", yang merupakan daftar kotak yang akan diperiksa.
2 Temukan semua kotak yang dapat diakses atau lumayan di sekitar titik awal dan lewati kotak yang tidak dapat diakses. Tambahkan ke daftar pembuka juga. Simpan titik A untuk semua kisi -kisi ini sebagai "grid induk". Saat kita ingin menggambarkan jalan, kuadrat induk
Materi sangat penting. Tujuan spesifiknya akan dijelaskan nanti.
3 Hapus titik awal A dari daftar terbuka dan tambahkan ke "daftar tutup" untuk menyimpan semua kotak yang tidak perlu diperiksa lagi.
Setelah langkah -langkah di atas, "daftar terbuka" berisi semua node di sekitar titik awal A kecuali untuk hambatan. Node induknya adalah semua A. melalui rumus f = g+h yang disebutkan sebelumnya, mereka menghitung nilai g, h, dan f dari masing -masing node, dan sesuai dengan nilai f, mereka kecil
Memilah ke besar. Dan lakukan operasi berikut pada node dengan nilai F terkecil
4. Hapus dari daftar ON dan tambahkan ke daftar off.
5. Periksa semua grid yang berdekatan. Lewati mereka yang tidak dilewati (1. Dalam "Daftar Tutup" dan 2. Hambatan) dan menambahkannya ke daftar terbuka jika mereka belum ada di dalamnya. Ambil kotak yang dipilih sebagai simpul induk dari kotak baru.
6. Jika jaringan yang berdekatan sudah ada dalam daftar terbuka, periksa apakah jalur saat ini lebih baik. Dengan kata lain, periksa apakah nilai G akan lebih rendah jika kita mencapainya dengan jalur baru. Jika tidak, maka tidak ada
Melakukan. (Di sini, tidak ada penilaian dalam kode saya)
7. Kami mengulangi proses ini sampai kisi target (titik akhir "B") ditambahkan ke "Daftar Terbuka", menunjukkan bahwa titik akhir B sudah ada di sekitar simpul sebelumnya yang ditambahkan ke "Daftar Tutup". Anda hanya perlu mengambil satu langkah untuk mencapai titik akhir B.
8. Kami menambahkan titik akhir B ke "Daftar Tutup"
9. Pada langkah terakhir, kita perlu mewakili jalur dari titik awal A ke titik akhir B. Peran simpul induk ditampilkan. Dengan mengubah nilai simpul induk dari simpul titik akhir di "Tutup daftar", Anda dapat menampilkan jalur dengan mengikuti petunjuk.
Lihat kodenya
package a_star_search;import java.util.ArrayList;public class AStar {/** * Use ArrayList array as "Open List" and "Close List" */ArrayList<Node> open = new ArrayList<Node>();ArrayList<Node> close = new ArrayList<Node>();/** * Get H value* @param currentNode: Current node* @param EndNode: titik akhir* @return*/public double getHvalue (node currentNode, node endnode) {return (math.abs (currentNode.getx () - endnode.getx ()) + math.abs (letternode.gety () - endnode.gety ()))* 10;}* goubeRet ** ** ** **: @pumnode: @parap: @gety ())* 10; @goubody* doublnode: @@gety ())* 10; getGvalue (node currentNode) {if (currentNode.getPnode ()! = null) {if (currentNode.getX () == curetnode.getPnode (). getx () || currentNode.gety () == currentNode.getpnode (). currentNode.getGValue ()+10;} return currentNode.getGValue ()+14;} return currentNode.getGValue ();}/** * Get Nilai F: g+h * @param currentNode * @return */public double getFvalue (node currentNode) {return letrentNode.get/get goubalue (node letternode) {return letrentNode. * Tambahkan node di sekitar node yang dipilih ke "Daftar Terbuka" * @param node * @param peta */public void inopen (node node, peta peta) {int x = node.getx (); int y = node.gety (untuk (int i = 0; i <3; i ++) {untuk (int j = 0; j <j <(j <3; i <3; i ++) {for (int j = 0; j <j <(j <3; (Artinya, ini bukan hambatan, bukan dalam daftar tertutup), daftar pembuka tidak termasuk, dan tidak dipilih 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 (peta.getMap () [x] [y]); // the Node yang dipilih digunakan sebagai peta node induk.getMap () [x-1+i] [y-1 +j] .setGvalue (getGvalue (Map.getMap () [x-1+i] [y-1+j])); peta.getMap () [x-1+i] [y-1+j] .sethvalue (getHvalue (peta.getMap () [x-1+i] [y-1+j], peta.ge tendnode ())); map.getMap () [x-1+i] [y-1+j] .setFvalue (getFvalue (peta.getMap () [x-1+i] [y-1+j])); open.add (map.getMap () [x-1+i] [y-1+j]);}}}}}}}}}}}}}}}}}}}} [y-1. * Urutkan node dalam daftar terbuka dari kecil ke besar dengan nilai f * @param arr */public void sort (arraylist <node> arr) {for (int i = 0; i <arr.size ()-1; i ++) {untuk (int j = i+1; j <arr.size (); j ++) {if (arr.get (i+1; arr.get(j).getFValue()){Node tmp = new Node();tmp = arr.get(i);arr.set(i, arr.get(j));arr.set(j, tmp);}}}}/** * Add node to "Close List" * @param node * @param open */public void inClose(Node node,ArrayList<Node> buka) {if (open.contains (node)) {node.setreachable (false); // atur open.remove (node) yang tidak dapat dijangkau (node); node);}} pencarian public void (peta peta) {// mengoperasikan node di sekitar titik awal, yaitu, yaitu, yaitu, yaitu, yaitu, yaitu, yaitu, yaitu, yaitu, yaitu, yaitu, yaitu, yaitu, yaitu, yaitu, yaitu, yaitu, yaitu, yaitu, yaitu inopen (map.getMap () [map.getStartNode (). getx ()] [map.getStartNode (). gety ()], peta); close.add (peta.getMap () [Map.getStart Node (). Getx ()] [map.getStartNode (). Getx ()] [map.getstartnode (). Gety ()]); peta.getMap () [map.getStartNode (). Getx ()] [map.g etStartNode().getY()].setReachable(false);map.getMap()[map.getStartNode().getX()][map.getStartNode().getY()].setPNode(map.getMap()[map.getStartNode().getX()][map.getStartNode().getY()]);sort(open);//Repeat the steps do {inopen (open.get (0), peta); inclose (open.get (0), open); sort (open);} while (! open.contains (peta.getMap () [map.getendNode (). getx ()] [peta.getendNode (). gety ()]); // Ketika Anda tahu titik endtendnode (). gety ()]); // Ketika Anda tahu titik endtennya di dalamnya di dalamnya di dalamnya di dalamnya di dalamnya di dalam poin endnode (). getY ()); inClose(map.getMap()[map.getEndNode().getX()][map.getEndNode().getY()], open);showPath(close,map);}/** * Mark the path* @param arr * @param map */public void showPath(ArrayList<Node> arr,Map map) {if(arr.size()>0){Node node = new Node (); // <span style = "White-space: pre"> </span> node = map.getMap () [map.getendNode (). Getx ()] [map.getendnode (). Gety ()]; == MAP.GetStartNode (). GetY ())) {// <span style = "White-space: pre"> </span> node.getpnode (). SetValue ("*"); style = "White-Space: Pre"> </span> map.getMap () [map.getStartNode (). getx ()] [map.getStartNode (). gety ()]. setValue ("a");}}Akhirnya tulis metode utama
paket a_star_search; Public Class Maintest {public static void main (string [] args) {peta peta = peta baru (); Astar astar = astar baru (); peta.showmap (); astar.search (peta); System.out.println ("========================================================================================================================= ==================================================================================================================================================== ==================================================================================================================================================== ============================================================================================================================================== peta.showmap ();Ubah peta dan uji untuk melihat efeknya
% % % % % % % % % % oooo % oo # oo % % a o # o b % % oo # oo % % oooo % % % % % % % % =========================================================. % % % % %
Meringkaskan
Untuk memastikan bahwa jalur terpendek (solusi optimal) ditemukan, kunci terletak pada pemilihan fungsi estimasi h (n): nilai jarak aktual dari nilai estimasi h (n) <= n ke simpul target. Dalam hal ini, ada banyak titik yang dicari, rentang pencariannya besar, dan efisiensinya rendah. Tapi bisa mendapatkan
Solusi optimal. Jika nilai estimasi> nilai aktual, jumlah poin pencarian kecil, kisaran pencarian kecil, dan efisiensinya tinggi, tetapi tidak dapat menjamin bahwa solusi optimal diperoleh.
Perasaan terbesar adalah: hal paling tabu tentang memancing selama tiga hari dan dua hari pengeringan jaring. Jumlahnya mungkin tidak besar, tetapi harus kontinuitas, dan kuncinya adalah kegigihan.
Saya berharap setiap programmer dapat dengan senang hati mengetik kode dan melakukan apa yang dia suka lakukan.
Di atas adalah semua konten artikel ini tentang pemrograman Java dan mengimplementasikan kode lengkap algoritma*. Saya harap ini akan membantu semua orang. Teman yang tertarik dapat terus merujuk ke topik terkait lainnya di situs ini. Jika ada kekurangan, silakan tinggalkan pesan untuk menunjukkannya.