Dalam dunia kecerdasan buatan dan ilmu komputer, pencarian solusi dalam suatu ruang masalah adalah tugas fundamental. Berbagai algoritma telah dikembangkan untuk tujuan ini, masing-masing dengan kelebihan dan kekurangannya. Salah satu algoritma pencarian yang penting dan banyak digunakan adalah Uniform Cost Search (UCS). UCS adalah algoritma pencarian berbasis grafik yang bertujuan untuk menemukan jalur terpendek dari satu node (titik awal) ke node lain (titik tujuan) dalam sebuah grafik berbobot. Berbeda dengan algoritma pencarian lain seperti Breadth-First Search (BFS) yang mengeksplorasi secara merata, UCS memprioritaskan jalur dengan biaya kumulatif terendah.
Bagaimana Cara Kerja UCS?
Prinsip dasar UCS adalah mengeksplorasi node yang paling "murah" terlebih dahulu. Algoritma ini menggunakan struktur data prioritas antrian (priority queue) untuk menyimpan node-node yang akan dikunjungi. Setiap elemen dalam prioritas antrian adalah sebuah node, bersama dengan biaya kumulatif untuk mencapai node tersebut dari titik awal.
Berikut adalah langkah-langkah umum cara kerja UCS:
Inisialisasi:
Buat sebuah prioritas antrian yang diurutkan berdasarkan biaya kumulatif (terendah ke tertinggi).
Masukkan node awal ke dalam prioritas antrian dengan biaya 0.
Buat sebuah set untuk melacak node yang sudah dikunjungi agar tidak mengunjungi kembali node yang sama berkali-kali dengan biaya yang lebih mahal.
Proses Perulangan: Selama prioritas antrian tidak kosong:
Keluarkan node dengan biaya terendah dari prioritas antrian. Node ini disebut node saat ini (current node).
Jika node saat ini adalah node tujuan, maka jalur yang ditemukan adalah jalur terpendek, dan algoritma berhenti.
Jika node saat ini belum dikunjungi:
Tandai node saat ini sebagai sudah dikunjungi.
Untuk setiap tetangga (neighbor) dari node saat ini:
Hitung biaya kumulatif untuk mencapai tetangga tersebut (biaya ke node saat ini + biaya dari node saat ini ke tetangga).
Jika tetangga belum pernah dimasukkan ke dalam prioritas antrian, atau jika biaya baru yang ditemukan lebih rendah dari biaya sebelumnya untuk mencapai tetangga tersebut, masukkan tetangga ke dalam prioritas antrian dengan biaya kumulatif yang baru.
Solusi Tidak Ditemukan: Jika prioritas antrian menjadi kosong sebelum node tujuan ditemukan, berarti tidak ada jalur dari node awal ke node tujuan, atau ada masalah dalam grafik.
Karakteristik dan Kelebihan UCS
UCS memiliki beberapa karakteristik penting yang membuatnya efektif dalam skenario tertentu:
Optimalitas: Jika ada jalur menuju tujuan, UCS dijamin akan menemukan jalur dengan biaya terendah (optimal). Ini karena ia selalu mengembangkan jalur yang paling murah terlebih dahulu.
Kelengkapan: UCS juga dijamin akan menemukan solusi jika ada.
Eksplorasi Berbasis Biaya: Berbeda dengan pencarian yang hanya mempertimbangkan kedalaman (seperti Depth-First Search) atau lebar (seperti Breadth-First Search), UCS secara eksplisit memperhitungkan "biaya" atau "harga" dari setiap langkah atau transisi antar node. Biaya ini bisa merepresentasikan jarak, waktu, atau sumber daya lain yang dibutuhkan.
Perbedaan dengan Algoritma Lain
Penting untuk membedakan UCS dari algoritma pencarian terkait:
UCS vs. BFS: BFS akan menemukan jalur terpendek dalam hal jumlah langkah jika semua biaya tepi (edge cost) sama. Namun, jika biaya tepi bervariasi, BFS tidak menjamin jalur terpendek secara biaya. UCS menangani variasi biaya tepi ini dengan baik.
UCS vs. Dijkstra's Algorithm: UCS sebenarnya adalah varian dari algoritma Dijkstra. Perbedaan utama terletak pada bagaimana mereka menangani node yang sudah dikunjungi. UCS biasanya hanya menambahkan node ke antrian jika biaya baru lebih rendah. Dijkstra lebih ketat dan memproses ulang jika menemukan jalur yang lebih murah. Dalam banyak implementasi praktis, keduanya seringkali merujuk pada konsep yang sama untuk pencarian jalur terpendek di grafik berbobot tak negatif.
UCS vs. A* Search: A* Search adalah pengembangan dari UCS yang menambahkan fungsi heuristik. Heuristik ini memperkirakan biaya dari node saat ini ke tujuan, membantu mengarahkan pencarian ke arah yang lebih menjanjikan. Jika heuristiknya nol, A* Search akan berperilaku sama seperti UCS.
Kapan Menggunakan UCS?
UCS sangat cocok digunakan dalam situasi di mana:
Anda membutuhkan solusi jalur terpendek yang optimal.
Biaya transisi antar node bervariasi dan penting untuk diperhitungkan.
Tidak ada informasi heuristik yang tersedia atau tidak dapat diandalkan untuk memandu pencarian.
Contoh aplikasi UCS meliputi perencanaan rute di peta, penugasan sumber daya dengan biaya berbeda, atau pemecahan teka-teki di mana setiap gerakan memiliki biaya tertentu.
Kesimpulan
Algoritma Uniform Cost Search adalah alat yang ampuh untuk menemukan jalur terpendek dalam grafik berbobot. Dengan memprioritaskan eksplorasi berdasarkan biaya kumulatif terendah, UCS memastikan optimalitas dan kelengkapan solusinya, menjadikannya pilihan yang solid ketika biaya merupakan faktor krusial dalam penentuan jalur.