Pencarian merupakan salah satu aspek penting dalam dunia komputasi. Algoritma pencarian adalah metode yang digunakan untuk menemukan solusi dari masalah tertentu. Salah satu algoritma pencarian yang umum digunakan adalah Uniform Cost Search.
Artikel ini kita akan belajar tentang algoritma Uniform Cost Search, termasuk konsep dasarnya, implementasinya, keuntungan, kekurangan dan contoh penggunaannya.
Apa itu Uniform Cost Search (UCS)?
Uniform Cost Search adalah salah satu algoritma pencarian yang digunakan untuk mencari jalur terpendek dalam sebuah graf dengan bobot pada setiap lintasannya. Algoritma ini sering digunakan dalam masalah optimisasi dan perutean. Tujuan utama dari Uniform Cost Search adalah mencari jalur dengan biaya terendah dari titik awal ke titik tujuan.
A. 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.
B. 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.
Cara Kerja dan Contoh Algoritma Uniform Cost Search (UCS)
1. Cara Kerja
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
Adapun rumus time complexity dalam algoritma uniform cost search sebagai berikut.
O(b(1 + C / ε))
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.
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 dan Kekurangan Uniform Cost Search (UCS)
Berikut adalah kelebihan dan kekurangan dari algoritma Uniform Cost Search (UCS):
Kelebihan
- 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
- 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.
Kesimpulan
Pada pembelajaran kita di atas dapat kita simpulkan bahwa Uniform Cost Search adalah salah satu algoritma pencarian yang digunakan untuk mencari jalur terpendek dalam sebuah graf dengan bobot pada setiap lintasannya. Algoritma ini sering digunakan dalam masalah optimisasi dan perutean yang bertuuan untuk mencari jalur dengan biaya terendah dari titik awal ke titik tujuan.
Dalam memilih algoritma pencarian, penting untuk mempertimbangkan karakteristik dan kebutuhan masalah yang dihadapi. UCS bisa menjadi pilihan yang baik dalam situasi di mana mencari jalur dengan biaya terendah sangat penting, tetapi perlu diperhatikan keterbatasan dan kekurangan algoritma ini.
Artikel ini merupakan bagian dari seri artikel belajar Algoritma dan jika ada ide topik yang mau kita bahas silahkan komen di bawah ya..
