Source Code Pencarian Rute (Path Finder) Metode A* (A Star) Dengan Visual Basic.Net

Metode A* (Astar) adalah metode pencarian rute dengan menggunakan teknik heuristik.   
Tteknik heuristik digunakan untuk meningkatkan evisiensi waktu terhadap pencarian rute. Rute yang dicari hanyalah dua lokasi saja, yaitu lokasi awal dan lokasi akhir.

Dalam ilmu komputer , A * (diucapkan sebagai "Bintang" ( dengarkan )) adalah algoritma komputer yang banyak digunakan dalam merintis jalan dan grafik traversal , proses merencanakan jalur efisien dijelajahi antara beberapa titik, yang disebut node. Terkenal karena kinerja dan akurasi, itu menikmati digunakan secara luas. Namun, dalam sistem-perjalanan routing yang praktis, umumnya mengungguli oleh algoritma yang dapat pra-proses grafik untuk mencapai kinerja yang lebih baik, meskipun pekerjaan lain telah menemukan A * lebih unggul dengan pendekatan lain

A * menggunakan pencarian terbaik pertama dan menemukan jalan untuk penerbangan setidaknya dari awal yang diberikan simpul untuk satu simpul tujuan (dari satu atau lebih tujuan mungkin). Sebagai * melintasi grafik, ia mengikuti jalan yang diharapkan total biaya terendah atau jarak, menjaga diurutkan prioritas antrian dari segmen jalur alternatif di sepanjang jalan.

Menggunakan pengetahuan-plus heuristik fungsi biaya dari simpul x (biasanya dilambangkan f (x)) untuk menentukan urutan di mana kunjungan pencarian node di pohon. Fungsi biaya adalah jumlah dari dua fungsi:

• Fungsi jalan-biaya masa lalu, yang merupakan jarak yang dikenal dari node mulai node saat x (biasanya dilambangkan g (x))
• Fungsi jalan-biaya masa depan, yang merupakan diterima "estimasi heuristik" dari jarak dari x ke tujuan (biasanya dilambangkan h (x)).

H (x) bagian dari f (x) fungsi harus menjadi heuristik diterima ; yaitu, tidak harus melebih-lebihkan jarak ke tujuan. Dengan demikian, untuk aplikasi seperti routing yang , h (x) mungkin mewakili jarak garis lurus ke tujuan, karena itu adalah fisik mungkin jarak terkecil antara dua titik atau node.

Jika heuristik h ​​memenuhi kondisi tambahan h (x) \ le d (x, y) + h (y) untuk setiap tepi (x, y) dari grafik (di mana d menunjukkan panjang tepi itu), maka h disebut monoton, atau konsisten . Dalam kasus seperti itu, A * dapat diimplementasikan lebih efisien-berbicara kasar, tidak ada simpul perlu diproses lebih dari sekali (lihat set tertutup di bawah) -dan A * setara dengan berjalan algoritma Dijkstra dengan mengurangi biaya d '(x, y): = d (x, y) + h (y) - h (x).

Contoh

Contoh dari bintang A (A *) algoritma dalam tindakan di mana node kota terhubung dengan jalan dan h (x) adalah jarak garis lurus ke titik sasaran:

Key: hijau: mulai; biru: Tujuan; orange: mengunjungi
A * algoritma juga memiliki aplikasi dunia nyata. Dalam contoh ini, ujung-ujungnya rel kereta api dan h (x) adalah jarak besar-lingkaran (mungkin jarak terpendek pada sebuah bola) ke target. Algoritma ini mencari jalan antara Washington, DC dan Los Angeles.





 

Inggris: Ilustrasi Algoritma * pencarian . The grafik dibuat oleh diskritisasi persegi seragam wilayah planar 2-dimensi, menempatkan node di setiap sel discretized, dan menghubungkan setiap node dengan 8 tetangganya menggunakan tepi dua arah. Biaya-ujungnya sama dengan panjang Euclidean mereka. Bentuk abu-abu merupakan kendala. Lingkaran yang diisi dengan merah & hijau mewakili diperluas node (node ​​di set tertutup). Warnanya menunjukkan nilai g (merah: rendah g-nilai, hijau: tinggi g-nilai). Node kosong dengan batas biru adalah orang-orang di set terbuka. Node dari grafik yang dihasilkan dengan cepat, dan node jatuh dalam hambatan yang dibuang sebagai tidak dapat diakses. Tujuannya adalah untuk menemukan jalan biaya setidaknya (terbatas grafik) dari awal diberikan untuk tujuan tertentu koordinat. The heuristik (konsisten) yang digunakan oleh sebuah node adalah yang Euclidean jarak ke tujuan. Artinya, h _(n) = | g - n | _2, dimana n merupakan Euclidean koordinat node n, g adalah simpul tujuan, dan |. | ₂ adalah 2-norma . Ini adalah contoh khas dari perencanaan gerak di robotika menggunakan algoritma A * pencarian. Dibuat menggunakan YGSBPL perpustakaan grafik-pencarian dan OpenCV .

Link : Source Code Pencarian Rute (Path Finder) Metode A* (A Star) Dengan Visual Basic.Net

(* Artikel oleh wikipedia.org (translate) :)