Bi-Directional A* (BDA*)
Pencarian Bi-Directional
Pencarian dua arah adalah algoritma yang menggunakan dua pencarian yang terjadi pada saat yang sama untuk mencapai tujuan. Pencarian dua arah umumnya tampaknya menjadi pencari grafik karena bukan pencarian melalui pohon besar, satu pencarian dilakukan mundur dari tujuan dan satu pencarian dilakukan ke depan dari awal. Alasan bahwa ini lebih cepat karena pohon-pohon tumbuh secara eksponensial dengan kedalaman mereka dan karena itu dua pohon kecil memiliki area yang lebih kecil dari satu pohon besar. Setelah kedua pencarian telah dilakukan, mereka akan berpotongan di tengah untuk menyelesaikan jalan. Bagian dari pencarian sebelum mereka bertemu disebut fase utama dan setelah persimpangan, hal itu disebut phase. Itu merupakan pengolahan pasca penting untuk dicatat bahwa sebagian besar banyak pencarian dua arah menggunakan heuristik yang berarti bahwa tidak ada cara untuk mengkonfirmasi apakah solusi yang ditemukan adalah solusi yang paling optimal.
Algoritma dari pencarian grafik melewati node dalam grafik secara sistematis sampai solusi optimal ditemukan sedangkan pencarian heuristik hanya akan mengkonfirmasi beberapa jenis solusi dalam waktu singkat. Jalur pencarian dua arah umumnya ditentukan berdasarkan beberapa jenis pencarian lainnya yang meliputi:
1. Breadth-first: Menambahkan node ke daftar setiap kali memeriksa node tujuan menggunakan struktur pohon sampai tercapai.
2. Best-first: Akan memilih simpul berikutnya menggunakan skor node (sering merupakan nilai f) yang memperhitungkan biaya dan panjang.
3. A *: mirip dengan pesawat-pertama, tetapi akan memperhitungkan biaya jalan dari awal ke node tertentu serta biaya dari simpul tersebut ke tujuan.
Contoh Pencarian & Pseudo Kode
Road Map:
Gambar 1: Jalur dari alamat awal dan alamat tujuan terhubung untuk menyelesaikan pencarian.
Yang paling efektif pencarian peta akan dua arah dikombinasikan dengan A *
POSA (x, y, f) dan POSB (x, y, f)
Buat posisi untuk demonstrasi di mana Anda berada pada saat itu di kedua pohon pencarian yang akan memiliki koordinat x, y koordinat dan nilai f untuk menjelaskan biaya jalan.
Startpoint (coordX, coordY)
Mulailah dengan node dimulai dengan pilihan untuk perjalanan lebih lanjut: Juga memiliki daftar koordinat dengan node menunjukkan pilihan gerakan menuju persimpangan tujuan.
Endpoint (coordX, coordY)
Mulailah dengan posisi akhir (node) dengan beberapa pilihan yang mengarah ke sana, juga memiliki daftar koordinat dengan node menunjukkan pilihan gerakan menuju start persimpangan.
jika POSA = POSB (x, y)
Ini berarti persimpangan sehingga pencarian akhir.
else bergerak POSA dari startpoint ke node berikutnya dengan terkecil f-valueA && bergerak POSB dari Endpoint ke node berikutnya dengan terkecil f-valueB sampai dua titik berpotongan
Catatan:
1. Hijau node menunjukkan jalur yang harus diambil, simpul merah menunjukkan persimpangan berharap.
2. Garis tebal menunjukkan biaya yang lebih tinggi, garis putus-putus menunjukkan pemisahan antara gerakan POSA dan POSB ini.
3. f-valueA akan memperhitungkan biaya dari startpoint ke POSA dan biaya dari POSA ke POSB.
4. f-valueB akan memperhitungkan biaya dari Endpoint ke POSB dan biaya dari POSB ke POSA.
Main problems with bidirectional search
1. Informasi konrkit mengenai tujuan akhir
2. Titik temu sulit untuk menjamin ketika ada banyak pilihan
3. Penyimpanan komputasi
Spesifikasi Model / Solusi untuk Masalah
Meskipun pencarian dua arah tampaknya menjadi salah satu dari pencarian tercepat, ada banyak kasus yang tidak akan praktis. Misalnya, jika Anda mencoba untuk menemukan item yang hilang, tidak akan ada cara untuk memulai pencarian dari tempat Anda berada serta di mana item tersebut karena Anda tidak memiliki informasi lokasinya. Sebuah skenario yang bagaimanapun bisa menggunakan desain pencarian dua arah ditunjukkan dalam contoh di atas jika Anda mencoba untuk mendapatkan dari satu alamat ke lokasi lain yang dikenal.
Des Champeaux (1983) menciptakan algoritma untuk mengatasi masalah persimpangan. Solusinya pada dasarnya melakukan dua depan untuk pencarian depan yang idealnya bertujuan sama lain. Ini heuristik depan dua arah untuk algoritma depan (BHFFA) namun ternyata mengambil terlalu banyak ruang komputasi. Model lain, yang dirancang oleh Politowisky dan Pohl (1984), diciptakan untuk mengatasi masalah yang ditimbulkan oleh Champeaux. Algoritma ini, yang disebut d-Node retargeting, bisa menggunakan ruang kurang komputasi serta menemukan cara yang efektif untuk bertemu di tengah. Menggunakan ide yang disarankan dari model Champeaux ini, Politowisky dan Pohl menggunakan depan untuk desain depan di mana jalur awal node bertujuan node yang paling menjanjikan dari jalur tujuan dan sebaliknya. Sayangnya, lebih banyak masalah dengan membangkitkan algoritma ini karena hanya bisa digunakan untuk heuristik tidak dapat diterima, dan bahkan kemudian, solusinya tidak selalu cukup jelas. Ketika algoritma pencarian dapat diterima, itu berarti bahwa pencarian akan berakhir di cabang dengan biaya terendah.
Ghosh dan Mehanti (1991) kemudian mencoba untuk memecahkan masalah ini dengan saran yang belum depan lain untuk algoritma heuristik depan bi-directional pencarian. Algoritma ini digunakan parameter standar yang mengurangi penyimpanan komputer. Algoritma mereka adalah kombinasi dari luas-pertama dan paling pertama pencarian. 15-puzzle dipilih untuk menguji algoritma mereka. 15-puzzle terdiri dari dewan ubin dengan nomor acak ditempatkan pada mereka dan sistem pencarian harus melalui dan menempatkan ubin dalam rangka. Hasil penelitian menunjukkan bahwa algoritma mereka adalah yang paling sukses dari algoritma yang telah disebutkan sebelumnya ketika menilai kualitas solusi.
Sumber:
http://en.wikibooks.org/wiki/Artificial_Intelligence/Search/Heuristic_search/Bidirectional_Search
No comments:
Post a Comment