Uniform Cost Search (UCS) adalah salah satu algoritma pencarian yang banyak digunakan dalam Artificial Intelligence (AI) untuk menemukan jalur dengan biaya paling rendah pada sebuah graf berbobot. Algoritma ini menjadi dasar dalam berbagai sistem pencarian rute, navigasi, robotika, hingga optimasi jaringan karena mampu menghasilkan solusi yang optimal.
Dalam artikel ini kita akan membahas pengertian Uniform Cost Search, cara kerja algoritma UCS, contoh penerapannya, kelebihan dan kekurangan, serta perbedaannya dengan algoritma pencarian lainnya. Dengan memahami konsep ini, Anda dapat lebih mudah mempelajari berbagai teknik pencarian dalam kecerdasan buatan dan machine learning.
Apa Itu Uniform Cost Search (UCS)?
Uniform Cost Search (UCS) adalah algoritma pencarian uninformed search yang digunakan untuk menemukan jalur dengan biaya total paling rendah dari node awal menuju node tujuan pada sebuah graf berbobot. Menurut Stuart Russell dan Peter Norvig dalam buku Artificial Intelligence: A Modern Approach, Uniform Cost Search melakukan eksplorasi node berdasarkan biaya kumulatif terkecil yang telah ditempuh sehingga mampu menghasilkan solusi optimal selama seluruh bobot lintasan bernilai positif.
Secara sederhana, Uniform Cost Search bekerja dengan selalu memilih jalur yang memiliki biaya paling murah untuk dieksplorasi terlebih dahulu. Untuk mendukung proses tersebut, algoritma ini menggunakan struktur data priority queue sehingga node dengan biaya terendah selalu berada pada prioritas utama. Karena mampu menemukan jalur optimal, UCS banyak digunakan dalam sistem navigasi, perencanaan rute, robotika, dan berbagai aplikasi kecerdasan buatan.
Konsep Dasar Uniform Cost Search
Algoritma Uniform Cost Search bekerja dengan cara mempertimbangkan semua jalur yang mungkin dari titik awal ke titik tujuan. Untuk setiap langkah, algoritma ini memilih jalur dengan biaya terendah. Proses ini dilakukan secara berulang hingga mencapai titik tujuan atau tidak ada jalur lagi yang tersedia.
Implementasi Algoritma Uniform Cost Search
Implementasi algoritma Uniform Cost Search memerlukan struktur data yang tepat, seperti graf atau pohon dan fungsi evaluasi biaya. Setiap simpul dalam struktur data memiliki nilai biaya yang terkait. Algoritma ini menggunakan antrian prioritas untuk memilih jalur dengan biaya terendah pada setiap langkahnya.
Baca Juga: Algoritma Adalah: Jenis, Fungsi dan Contoh
Cara Kerja dan Contoh Algoritma Uniform Cost Search (UCS)
1. Cara Kerja Uniform Cost Search (UCS)
Berikut adalah langkah-langkah dalam algoritma Uniform Cost Search:
- Inisialisasi: Pertama, kita perlu menginisialisasi algoritma dengan memilih simpul awal dan menetapkan biaya 0 ke simpul awal. Biaya ini akan terus diperbarui saat kita menjelajahi graf.
- Buat sebuah antrian prioritas (priority queue) yang akan menyimpan simpul yang akan dieksplorasi. Antrian prioritas ini akan disusun berdasarkan biaya total dari simpul tersebut.
- Masukkan simpul awal ke dalam antrian prioritas dengan biaya 0.
- Selama antrian prioritas tidak kosong, lakukan langkah-langkah berikut:
- Ambil simpul dengan biaya terendah dari antrian prioritas.
- Periksa apakah simpul tersebut adalah simpul tujuan. Jika iya, maka kita telah menemukan jalur dengan biaya minimum dari simpul awal ke simpul tujuan dan algoritma berakhir.
- Jika simpul tersebut bukan simpul tujuan, kita perlu menjelajahi tetangga-tetangganya.
- Untuk setiap tetangga yang belum dieksplorasi, perbarui biaya total mereka dengan biaya total saat ini ditambah dengan biaya dari simpul saat ini ke tetangganya.
- Jika tetangga tersebut belum ada di antrian prioritas atau biaya totalnya lebih rendah dari biaya total yang ada, tambahkan tetangga tersebut ke antrian prioritas dengan biaya total yang diperbarui.
- Ulangi langkah-langkah di atas sampai kita menemukan simpul tujuan atau antrian prioritas kosong.
- Jika antrian prioritas kosong dan kita belum menemukan jalur ke simpul tujuan, maka jalur tersebut tidak ada.
Algoritma Uniform Cost Search memastikan bahwa simpul dengan biaya terendah dieksplorasi terlebih dahulu. Dengan menggunakan antrian prioritas, simpul dengan biaya terendah selalu dieksplorasi terlebih dahulu. Hal ini memastikan bahwa algoritma akan menemukan jalur dengan biaya minimum dari simpul awal ke simpul tujuan.
2. Contoh Uniform Cost Search (UCS)
Adapun rumus time complexity dalam algoritma uniform cost search sebagai berikut.
Keterangan:
b : branching factor
C : biaya optimal
ε : biaya setiap langkah
Agar lebih mudah dalam memahami operasi uniform cost search, berikut contoh algoritma tersebut berjalan.
Berikut terdapat graph berbobot yang dapat ditelusuri dengan biaya paling rendah menggunakan algoritma uniform cost search.
Langkah pertama, sebagai pengguna dapat menginput simpul root atau simpul sumber ke antrian queue.
Selanjutnya, tambahkan child simpul miliki simpil root ke dalam priority queue dengan jarak kumulatifnya sebagai prioritas, seperti gambar di bawah ini.
Simpul A mempunyai jarak minimum sehingga dapat diekstraksi dari daftar. Hal tersebut disebabkan karena A bukan merupakan simpul tujuan melainkan child simpul yang ditambahkan ke priority queue.
Baca Juga: Beam Search: Cara Kerja dan Contoh Penerapan
Kemudian, dalam B mempunyai prioritas maksimum sehingga child simpulnya ditambahkan ke queue.
Lalu, pada G dapat dihapus dan turunannya akan ditambahkan ke queue.
Berikutnya pada C dan I mempunyai jarak yang sama, sehingga pengguna dapat menghapus berdasarkan abjad. Adapun langkah-langkah dalam menghapus abjad.
Pengguna dapat menghapus I, namun I tidak mempunyai simpul child lagi sehingga tidak ada pembaruan dalam antrian.
Setelah itu, pengguna dapat menghapus simpul D. Simpul D hanya mempunyai satu child E dengan jarak kumulatif 10. Namun, E sudah ada dalam antrian dengan jarak yang lebih kecil sehingga pengguna tidak dapat menambahkannya kembali.
Selanjutnya, jarak minimum dimiliki oleh E, oleh karena itu simpul tersebut dapat dihilangkan.
Biaya minimum berikutnya adalah F, sehingga dapat dihilangkan dan turunannya yakni J dapat ditambahkan.
Lalu, biaya minimum selanjutnya adalah H, sehingga H dapat dihilangkan namun tidak mempunyai child simpul untuk ditambahkan.
Langkah terakhir, pengguna dapat menghilangkan simpul tujuan kemudian dilanjutkan melakukan pemeriksaan apakah simpul tersebut merupakan target atau bukan, serta pengguna juga dapat menghentikan algoritma pada langkah ini.
Kelebihan Uniform Cost Search (UCS)
- Optimalitas: UCS menjamin menemukan jalur dengan biaya minimum dari simpul awal ke simpul tujuan jika semua biaya lintasan positif. Ini membuatnya menjadi pilihan yang baik dalam situasi di mana kita perlu mencari jalur dengan biaya terendah.
- Kekeliruan yang lebih rendah: Karena algoritma ini menggunakan antrian prioritas, simpul dengan biaya terendah dieksplorasi terlebih dahulu. Ini mengurangi kemungkinan mengalami kesalahan atau kehilangan jalur dengan biaya lebih rendah.
- Eksplorasi sistematis: UCS secara sistematis menjelajahi simpul-simpul yang meminimalkan biaya total saat ini. Ini memastikan bahwa algoritma tidak melewatkan jalur yang mungkin memiliki biaya lebih rendah.
Kekurangan Uniform Cost Search (UCS)
- Waktu komputasi yang tinggi: Algoritma UCS dapat menjadi sangat lambat jika digunakan dalam graf yang besar atau memiliki biaya yang tidak seragam. Algoritma ini perlu menjelajahi semua simpul yang mungkin, termasuk simpul dengan biaya yang tinggi, sebelum menemukan jalur dengan biaya minimum.
- Ruang penyimpanan yang besar: Algoritma UCS memerlukan ruang penyimpanan yang signifikan untuk menyimpan antrian prioritas yang memuat semua simpul yang mungkin. Ini bisa menjadi masalah dalam graf yang sangat besar atau jika sumber daya penyimpanan terbatas.
- Tidak efisien dalam graf dengan biaya negatif: Jika terdapat biaya negatif dalam graf, algoritma UCS tidak akan berfungsi dengan benar. Hal ini dikarenakan algoritma UCS tidak memiliki mekanisme untuk mendeteksi atau menangani siklus negatif yang mungkin terjadi.
Dalam memilih algoritma pencarian, perlu mempertimbangkan karakteristik dan kebutuhan khusus dari masalah yang dihadapi. Meskipun UCS memiliki kelebihan tertentu, terdapat situasi di mana algoritma pencarian lain, seperti A* (A-star) atau algoritma pencarian heuristik, mungkin lebih sesuai tergantung pada tujuan pencarian dan struktur graf yang diberikan.
Baca Juga: Algoritma A Star (A*): Konsep, Cara Kerja, dan Kelebihan
Kesimpulan
Pada pembahasan di atas dapat disimpulkan bahwa Uniform Cost Search (UCS) adalah algoritma pencarian yang digunakan untuk menemukan jalur dengan biaya minimum pada graf berbobot. Algoritma ini bekerja dengan mengeksplorasi node berdasarkan biaya kumulatif terkecil menggunakan priority queue sehingga mampu menghasilkan solusi yang optimal. Karena karakteristik tersebut, UCS banyak diterapkan dalam bidang Artificial Intelligence, navigasi, robotika, dan optimasi jaringan.
Meskipun memiliki keunggulan dalam menemukan jalur terbaik, Uniform Cost Search membutuhkan memori dan waktu komputasi yang relatif besar pada graf yang kompleks. Oleh karena itu, pemilihan algoritma perlu disesuaikan dengan kebutuhan sistem. Jika prioritas utama adalah menemukan solusi dengan biaya terendah, maka Uniform Cost Search merupakan salah satu algoritma pencarian yang paling efektif untuk digunakan.
Artikel ini merupakan bagian dari seri Kecerdasan Buatan KantinIT.com. Jika artikel ini bermanfaat, jangan lupa bagikan ke media sosial atau ke teman kamu.
