Algoritma Pencarian Greedy Best First pada Kecerdasan Buatan

Peta sederhana Romania sebagai contoh kasus untuk pencarian greedy best first

Pencarian greedy best-first akan menurunkan node yang paling dekat dari tujuan, dengan alasan bahwa hal ini cenderung mengarah pada solusi dengan cepat. Dengan demikian, algoritma ini akan mengevaluasi node hanya dengan menggunakan fungsi heuristik; yaitu, f (n) = h (n).

Mari kita lihat bagaimana algoritma ini bekerja untuk problem pencarian rute di Romania; kita menggunakan fungsi heuristik jarak garis lurus, yang akan kita sebut h_SLD. Misalkan jika tujuannya adalah Bucharest, kita perlu mengetahui jarak garis lurus ke Bucharest, yang ditunjukkan pada gambar tabel di bawah ini.

Tabel daftar nilai h_SLD untuk jarak terdekat ke Bucharest

Misalnya, h_SLD (In(Arad)) = 366. Perhatikan bahwa nilai-nilai dalam h_SLD tidak dapat dihitung dari deskripsi problem itu sendiri. Selain itu, perlu sejumlah pengalaman untuk mengetahui bahwa h_SLD berkorelasi dengan jarak jalan yang sebenarnya dan, oleh karena itu, ini adalah heuristik yang berguna.

Gambar di bawah ini menunjukkan proses pencarian greedy best-first menggunakan h_SLD untuk menemukan jalur dari Arad ke Bucharest.

Tahapan-tahapan dalam pencarian greedy best-first dalam pohon pencarian ke Bucharest berdasarkan fungsi heuristik jarak garis lurus 

Node pertama yang akan diturunkan dari Arad adalah Sibiu karena lebih dekat ke Bucharest dibanding dengan Zerind atau Timisoara. Node berikutnya yang akan diturunkan adalah Fagaras karena paling dekat. Fagaras pada gilirannya menghasilkan Bucharest, yang merupakan tujuannya. Untuk problem khusus ini, pencarian greedy best-first menggunakan h_SLD untuk menemukan solusi tanpa pernah menurunkan node yang tidak ada pada jalur solusi; karenanya, cost pencariannya minimal. Namun pencarian ini tidak optimal: karena jalur melalui Sibiu dan Fagaras ke Bucharest adalah 32 kilometer lebih panjang dari jalur melalui Rimnicu Vilcea dan Pitesti. Inilah mengapa algoritma ini disebut "greedy" karena pada setiap langkahnya algoritma ini hanya mencoba node yang terdekat dengan tujuan.

Pencarian pohon greedy best-first juga tidak complete bahkan dalam state space yang terbatas, sama seperti pada pencarian depth-first. [Untuk memahami tentang complete/completeness silahkan lihat kriteria kinerja algoritma pencarian pada artikel Pencarian Breadth First dalam Kecerdasan Buatan  di bagian catatan akhir].

Pertimbangkan problem lain misalkan dari Iasi ke Fagaras. Heuristik menunjukkan bahwa Neamt akan diturunkan terlebih dahulu karena paling dekat dengan Fagaras, tetapi jalur itu adalah jalan buntu. Solusinya adalah pergi dulu ke Vaslui — suatu jarak yang sebenarnya lebih jauh dari tujuan berdasarkan heuristik — dan kemudian melanjutkan ke Urziceni, Bucharest, dan Fagaras. Tetapi, algoritma ini tidak akan pernah menemukan solusi pada problem seperti ini, karena menurunkan Neamt kemudian akan menempatkan kembali Iasi ke jalur, Iasi lebih dekat ke Fagaras dbandingkan Vaslui, dan Iasi akan diturunkan lagi, yang mengarah ke loop yang tak akan berhenti.

Dalam kasus terbutuk tentang kompleksitas ruang/memori dan waktu (execution time) untuk pohon ini adalah O(b^m), di mana m adalah kedalaman maksimum node pencarian. Namun, dengan fungsi heuristik yang baik, kompleksitasnya dapat dikurangi secara substansial. Jumlah pengurangan tergantung pada problem tertentu yang dihadapi dan pada kualitas heuristik-nya.