Algoritma Pencarian Uniform-Cost dalam Kecerdasan Buatan

Algoritma ini adalah pengembangan atau modifikasi dari algoritma pencarian breadth-first. Andaikan semua cost pada semua langkah/node adalah sama, maka algoritma pencarian breadth-first adalah optimal karena selalu menurunkan node yang terdangkal. Dengan sedikit pengembangan algoritma, kita dapat menemukan algoritma yang optimal dengan menerapkan suatu fungsi step-cost (menerapkan suatu cost pada tiap-tiap langkah pencarian atau pada tiap-tiap node). Alih-alih menurunkan node yang terdangkal (yaitu node di lapisan/jalur berikutnya), pencarian uniform-cost menurunkan node n berdasarkan fungsi cost yang terendah dalam suatu jalur, misalkan saja fungsi g(n). Ini dilakukan dengan menyimpan antrian dalam suatu jalur yang diurutkan berdasarkan fungsi g(n). Algoritma pencarian uniform-cost ditunjukkan pada gambar di bawah ini. 

Algoritma pencarian uniform-cost

Selain mengurutkan antrian berdasarkan cost dalam lapisan/jalur yang sama, masih ada dua hal penting lainnya yang membedakan algoritma pencarian uniform-cost dengan algoritma pencarian breadth-first. Yang pertama adalah bahwa tes terhadap goal diterapkan ke node saat dipilih untuk diturunkan/ekspansi dan bukan saat setelah turunan/ekspansinya dihasilkan. Alasannya adalah bahwa node goal pertama yang dihasilkan mungkin bukan goal yang optimal. Perbedaan kedua adalah bahwa tes goal dilakukan lagi jika jalur/ yang lebih baik ditemukan di suatu node yang ada dalam lapisan/jalur saat ini. 

Kedua modifikasi ini bisa dilihat pada contoh yang ditunjukkan pada gambar di bawah ini, di mana  problemnya adalah perjalanan dari Sibiu ke Bucharest. 

Kota-kota di Romania untuk ilustrasi contoh algoritma pencarian uniform-cost

Node penerus Sibiu adalah Rimnicu Vilcea dan Fagaras, dengan cost masing-masing 80 dan 99. Node paling hemat/rendah, yaitu Rimnicu Vilcea, selanjutnya diturunkan/ekspansi, sehingga menambahkan Pitesti dengan cost 80 + 97 = 177. Sehingga node yang paling hemat/rendah sekarang adalah Fagaras, sehingga kemudian diturunkan, dengan menambahkan Bucharest dengan cost 99 + 211 = 310. Sekarang node goal telah dihasilkan, tetapi algoritma pencarian uniform-cost terus berjalan, yaitu memilih Pitesti untuk diturunkan/ekspansi dan menambahkan jalur kedua menuju Bucharest dengan cost 80 + 97 + 101 = 278. Sekarang algoritma akan memeriksa apakah jalur baru ini lebih baik daripada yang sebelumnya; hasilnya adalah ya, jadi yang jalur yang sebelumnya dibuang. Bucharest, sekarang dicapai dengan g-cost 278, dan solusinya dihasilkan. 

Sangat mudah untuk melihat bahwa algoritma pencarian uniform-cost secara umum adalah optimal. Pencarian dengan uniform-cost tidak peduli tentang jumlah langkah atau node yang dimiliki suatu jalur, tetapi hanya peduli dengan total cost yang dicapai. Completeness dijamin selama cost setiap langkah (node) melebihi suatu konstanta positif kecil Є. [Catatan: Completeness adalah salah satu kriteria pengukuran  kinerja suatu algoritma pencarian. Lihat kriteria kinerja algoritma pencarian pada artikel Pencarian Breadth First dalam Kecerdasan Buatan  di bagian catatan akhir artikel]

Pencarian uniform-cost dituntun oleh cost pada jalur pencarian dan bukan oleh kedalaman jalur/lapisannya, jadi kompleksitasnya tidak mudah dikarakterisasi dengan b (branching atau jumlah pencabangan pohon) dan d (depth atau tingkat kedalaman pohon). Jadi, misalkan C^∗ adalah cost dari solusi yang optimal, dan anggap setiap tindakan paling tidak menghasilkan memiliki cost Є. Maka kompleksitas waktu eksekusi dan ruang/memori terburuk dari algoritma ini adalah O(b^{1 + [C∗ / Є]}), yang bisa jauh lebih besar dari b^d. Ini karena pencarian uniform-cost dapat menjelajahi pohon besar melalui langkah-langkah kecil sebelum menjelajahi jalur yang melibatkan langkah-langkah besar yang mungkin bermanfaat. Ketika semua cost pada node adalah sama, b^{1 + [C∗ / Є]}, berarti hanya b^d+1. Ketika semua cost pada node-node adalah sama, algoritma pencarian uniform-cost menjadi mirip dengan pencarian breadth-first, kecuali bahwa breadt-first berhenti segera setelah menghasilkan goal, sedangkan pencarian uniform-cost memeriksa semua node pada kedalaman goal untuk melihat apakah ada yang memiliki cost lebih rendah; sehingga pencarian dengan uniform-cost melakukan lebih banyak pekerjaan dengan menurunkan/ekspansi node-node pada kedalaman d yang kadang tidak diperlukan.