GENERAL FIRST TES

general first test

cari dua arah adalah algoritma pencarian grafik yang menemukan jalur terpendek dari awal simpul ke sebuah node tujuan dalam grafik diarahkan . Berjalan dua pencarian simultan: satu maju dari keadaan awal, dan satu mundur dari tujuan, berhenti ketika kedua bertemu di tengah. Alasan untuk pendekatan ini adalah bahwa dalam banyak kasus lebih cepat: misalnya, dalam sebuah model yang disederhanakan dari kompleksitas masalah pencarian di mana kedua pencarian memperluas pohon dengan percabangan faktor b, dan jarak dari awal sampai tujuan adalah d, masing-masing dua pencarian memiliki kompleksitas O (b d / 2) (dalam notasi Big O ), dan jumlah ini dua kali pencarian jauh lebih kecil dari O (b d) kompleksitas yang akan dihasilkan dari satu pencarian dari awal sampai tujuan .
speedup ini tidak datang tanpa suatu harga: algoritma pencarian bidirectional harus mencakup logika tambahan untuk memutuskan pohon pencarian untuk memperpanjang pada setiap langkah, meningkatkan kesulitan pelaksanaan. Negara Tujuan harus diketahui (bukan memiliki kriteria tujuan umum yang mungkin dipenuhi oleh negara yang berbeda), algoritma tersebut harus dapat melangkah mundur dari tujuan untuk keadaan awal (yang mungkin tidak dapat dilakukan tanpa kerja ekstra), dan kebutuhan algoritma cara yang efisien untuk menemukan persimpangan kedua pohon pencarian. Kompleksitas tambahan melakukan pencarian bidirectional berarti bahwa algoritma pencarian A * sering merupakan pilihan yang lebih baik jika kita memiliki heuristik yang wajar.
Seperti di Sebuah pencarian *, cari bi-directional dapat dipandu oleh perkiraan heuristik dari jarak yang tersisa untuk tujuan (di pohon depan) atau dari awal (di pohon belakang). Sebuah heuristik diterima juga akan menghasilkan solusi terpendek, seperti yang terbukti awalnya untuk A *.
node A, yang diperluas adalah dipilih dari perbatasan yang memiliki jumlah terkecil node terbuka dan yang paling menjanjikan. Pemutusan terjadi ketika sebuah node seperti juga berada di perbatasan lainnya. Sebuah simpul keturunan's f-nilai harus mempertimbangkan g-nilai dari seluruh node terbuka di perbatasan lainnya. Oleh karena itu perluasan node lebih mahal daripada untuk A *. Pengumpulan node yang akan dikunjungi bisa lebih kecil seperti diuraikan di atas. Sehingga satu perdagangan di ruang kurang untuk perhitungan lebih. Referensi 1977 menunjukkan bahwa algoritma bi-directional menemukan solusi mana * A sudah kehabisan ruang. jalan yang lebih pendek juga ditemukan saat diterima non heuristik digunakan. Tes ini dilakukan pada teka-teki 15-digunakan oleh Ira Pohl.
Ira Pohl adalah orang pertama untuk merancang dan mengimplementasikan suatu algoritma pencarian heuristik bi-directional. Sebuah node keturunan di sebuah perbatasan hanya dievaluasi mengenai target di sisi lain. Dia melaporkan bahwa dua pohon pencarian hilang sama lain dan tidak bertemu di tengah-tengah dari ruang pencarian. Kemudian, ia dan muridnya, George Politowski ditingkatkan metode ini dengan memilih D - simpul sebagai perantara alam.