Aplikasi Metode Best-First Search Pada Pencarian Rute Terpendek - Rina Harimurti, (Teknika, 2010)
Abstrak Menyelesaikan permasalahan dalam bidang kecerdasan buatan memerlukan beberapa teknik searching atau pencarian. Pertama adalah mendefinisikan ruang masalah, ke dua mendefinisikan aturan produksi yang digunakan, dan terakhir adalah memilih metode pencarian yang tepat sehingga dapat menemukan solusi terbaik dengan usaha minimal. Setiap metode mempunyai karakteristik yang berbeda-beda dengan kelebihan dan kekurangannya masing-masing. Metode Best-First Search (BFS)  ini sesuai dengan namanya membangkitkan simpul berikutnya dari sebuah simpul (yang sejauh ini) terbaik diantara semua leaf nodes (simpul-simpul pada level terdalam) yang pernah dibangkitkan. Algoritma  BFS ini digolongkan sebagai heuristic search atau informed search. Terdapat dua jenis BFS, yaitu algoritma Greedy Best First Search dan algoritma A*. Pada penyelesaian kasus pencarian rute terpendek dari 13 kota yang dinyatakan dengan simpul-simpul dalam suatu graph dua arah, setiap angka pada busur menyatakan biaya sebenarnya antara satu kota dengan kota lainnya. Dengan menggunakan metode Greedy Best-First Search  penelusuran rute terpendek yang dihasilkan adalah S-B-K-G dengan jarak 135 kilometer. Sedangkan dengan menggunakan metode A* (A Bintang) penelusuran menghasilkan rute   S-A-G = 120. g(G) = 120 & f(G) = 120. Rute yang dihasilkan dengan menggunakan metode A* merupakan rute terpendek yang ada di graph tersebut. Hal ini menunjukkan bahwa Greedy Best-First Search tidak optimal, sedangkan algoritma   A* adalah optimal. Tanpa ada batasan waktu dan memori, A* adalah complete (selalu menemukan solusi jika solusinya ada).