Pencarian dilakukan dari dua arah : pencarian maju (dari start ke goal) dan pencarian mundur (dari goal ke start). Ketika dua arah pencarian telah membangkitkan simpul yang sama, maka solusi telah ditemukan, yaitu dengan cara menggabungkan kedua jalur yang bertemu.
Pencarian dua arah adalah mesin pencarian grafik algoritma yang menemukan jalur terpendek dari titik awal ke titik tujuan dalam grafik diarahkan. Ini berjalan dua pencarian simultan: satu maju dari keadaan awal, dan satu mundur dari tujuan, berhenti ketika dua bertemu di tengah. Alasan untuk pendekatan ini adalah bahwa dalam banyak kasus itu lebih cepat: misalnya, dalam model yang disederhanakan dari kompleksitas masalah pencarian di mana kedua pencarian memperluas pohon dengan percabangan b faktor, dan jarak dari awal sampai tujuannya adalah d, masing-masing dua pencarian memiliki kompleksitas O (bd / 2) (dalam notasi Big O), dan jumlah ini dua kali pencarian jauh lebih sedikit dibandingkan kompleksitas (bd) O yang akan dihasilkan dari satu pencarian dari awal ke tujuan.
Seperti dalam Sebuah pencarian *, bi-directional pencarian dapat dipandu oleh perkiraan heuristik dari jarak yang tersisa untuk tujuan (di pohon maju) atau dari awal (di pohon belakang).
Ira Pohl adalah yang pertama untuk merancang dan menerapkan algoritma bi-directional heuristik pencarian. Andrew Goldberg dan lain-lain menjelaskan kondisi terminasi yang benar untuk versi bidirectional Algoritma Dijkstra.
Description
Sebuah Heuristic Search dua arah adalah pencarian ruang dari beberapa negara ke negara bagian lain, mencari dari ke dan dari untuk secara bersamaan (atau quasi-secara bersamaan jika dilakukan pada mesin sekuensial). Ini mengembalikan daftar yang sah dari operator bahwa jika diterapkan akan memberi kita.
Meskipun mungkin tampak seolah-olah operator harus dibalik untuk pencarian mundur, hanya diperlukan untuk dapat menemukan, mengingat setiap node, himpunan node induk seperti bahwa ada beberapa operator yang sah dari masing-masing node induk untuk. Hal ini sering disamakan dengan sebuah jalan satu arah dalam domain rute-temuan: tidak perlu untuk dapat melakukan perjalanan ke kedua arah, namun perlu ketika berdiri di ujung jalan untuk menentukan awal jalan sebagai rute yang mungkin.
Demikian pula, bagi mereka yang memiliki tepi busur terbalik (yaitu busur yang terjadi di kedua arah) itu tidak perlu bahwa setiap arah menjadi biaya yang sama. Pencarian sebaliknya akan selalu menggunakan biaya terbalik (yaitu biaya busur ke arah depan). Lebih formal, jika adalah node dengan orang tua, maka, yang didefinisikan sebagai biaya dari untuk. (Auer Kaindl 2004)
Terminologi dan notasi
faktor percabangan dari pohon pencarian
biaya yang terkait dengan bergerak dari node ke node
biaya dari akar ke node
perkiraan heuristik dari jarak antara node dan tujuan
negara awal
negara tujuan (kadang-kadang, tidak menjadi bingung dengan fungsi)
arah arus pencarian. Dengan konvensi, adalah sama dengan 1 untuk arah maju dan 2 untuk arah mundur (Kwa 1989)
arah yang berlawanan penelusuran (yakni)
pohon pencarian di d arah. Jika, akar, jika, akar adalah
daun (kadang-kadang disebut sebagai). Ini adalah dari set ini bahwa sebuah node dipilih untuk ekspansi. Dalam pencarian dua arah, ini kadang-kadang disebut 'perbatasan' pencarian atau 'muka gelombang', mengacu pada bagaimana mereka muncul saat pencarian diwakili grafis. Dalam metafora ini, sebuah 'tabrakan' terjadi ketika, selama fase ekspansi, sebuah node dari satu wavefront yang ditemukan memiliki penerus dalam wavefront lawan.
non-daun node. Set ini berisi node yang sudah dikunjungi oleh pencarian
Pendekatan untuk Heuristic Search dua arah
Algoritma dua arah secara garis besar dapat dibagi menjadi tiga kategori: Front-to-Front, Front-to-Back (atau Front-to-End), dan Perimeter Cari (Kaindl Kainz 1997). Ini berbeda dengan fungsi yang digunakan untuk menghitung heuristik.
Front-to-Back
Front-to-Back algoritma menghitung nilai node dengan menggunakan perkiraan heuristik antara dan akar dari pohon pencarian yang berlawanan, atau.
Front-to-Back adalah yang paling aktif diteliti dari tiga kategori. Algoritma terbaik saat ini (setidaknya dalam domain puzzle Lima belas) adalah BiMAX-BS * F algoritma, yang diciptakan oleh Auer dan Kaindl (Auer, Kaindl 2004).
Front-to-Front
Front-to-Front algoritma menghitung nilai node dengan menggunakan perkiraan heuristik antara dan beberapa subset dari. Contoh kanonik adalah bahwa dari BHFFA (Algoritma Heuristic Front-to-Front Bidirectional) (de Champeaux 1977/1983), di mana fungsi ini didefinisikan sebagai minimum semua perkiraan heuristik antara node saat ini dan node di depan lawan. Atau, secara resmi:
mana mengembalikan sebuah estimasi (yaitu tidak melebih-lebihkan) heuristik diterima dari jarak antara node dan.
Front-to-Front menderita menjadi berlebihan menuntut komputasi. Setiap kali sebuah node dimasukkan ke dalam daftar terbuka, nilainya harus dihitung. Ini melibatkan menghitung perkiraan heuristik dari untuk setiap node di set berlawanan, seperti dijelaskan di atas. Set bertambah besar secara eksponensial untuk semua domain dengan.
Tidak ada komentar:
Posting Komentar