Section Artikel
Apa itu Uniform Cost Search ?
Uniform cost search merupakan algoritma search tree yang digunakan untuk menyelesaikan beberapa permasalahan. Algoritma ini melakukan pencarian dari akar sampai kemudian dilanjut menuju ke simpul-simpul lainnya.
Uniform cost search juga dapat dipahami sebagai algoritma pencarian tanpa informasi yang menggunakan anggaran kumulatif paling rendah dalam melakukan pencarian jalur dari simpul sumber ke simpul tujuan.
Uniform cost search bekerja dengan metode brute force dengan tidak menghitungkan keadaan simpul atau ruang pencarian. Biasanya algoritma ini dapat diterapkan dengan menggunakan priority queue, yang mana fokus utamanya adalah menurunkan anggaran operasi.
Uniform cost search juga dapat disebut sebagai varian dari algoritma dijkstra. Bukannya menginput semua simpul ke dalam antrian prioritas namun hanya menyisipkan simpul sumber, kemudian menginputnya secara satu per satu apabila diperlukan.
Fungsi Uniform Cost Search
Dalam penerapannya algoritma uniform cost search melibatkan seluruh simpul yang berhubungan dengan root node, dan memposisikannya dalam priority queue untuk mencapai simpul tujuan. Simpul-simpul yang terpilih merupakan simpul yang berharga paling kecil.
Uniform cost search dapat digunakan untuk menyelesaikan beberapa permasalahan. Algoritma uniform cost search dapat menentukan simpul mana yang akan diekspansi dan urutan node selanjutnya yang akan diekspansi melalui sebuah fungsi g(n).
Fungsi g(n) merupakan fungsi yang menyatakan cost dari sumpul-E atau simpul ekspan dan simpul-simpul lainnya. Selain mengoperasikan fungsi algoritma BFS, uniform cost search juga dapat melakukan ekspansi simpul dengan nilai path yang terkecil.
Hal tersebut dapat dilakukan dengan membuat antrian pada successor yang ada berdasar kepada nilai path-nya atau simpul disimpan dalam bentuk priority queue.
kelebihan dan kekurangan
Algoritma uniform cost search memiliki kelebihan dan kekurangan, berikut diantaranya.
Kelebihan Uniform Cost Search
Berikut ini kelebihan yang ada dalam uniform cost search.
- Membantu dalam menentukan rute dengan biaya kumulatif paling rendah dalam suatu graph berbobot yang mana jalur tersebut mempunyai biaya berbeda dari simpul root ke simpul tujuan.
- Algoritma uniform cost search dianggap sebagai penyelesaian permasalahan secara optimal sebab dalam setiap keadaan, jalur yang diikuti merupakan jalur dengan rute paling pendek.
Kekurangan Uniform Cost Search
Selain kelebihan, uniform cost search juga memiliki kekurangan. Berikut diantaranya.
- Memerlukan ruang penyimpanan yang cukup besar sebab semakin banyak simpul maka ukuran penyimpanan semakin meningkat secara eksponensial.
- Algoritma dapat terjebak dalam keadaan infinite loop sebab perlu mempertimbangkan setiap kemungkinan jalur dari node root mengarah ke node tujuan.
- Fokus utama dalam priority queue perlu dipertahankan sehingga daftar terbuka harus tetap berada dalam keadaan urut.
Cara Kerja Uniform Cost Search
Selanjutnya cara kerja algoritma uniform cost search. Pertama input simpul root ke dalam priority queue. Kedua, ulangi langkah berikut saat antrian queue sedang tidak terisi.
- Hapus elemen dengan prioritas paling tinggi.
- Apabila terdapat simpul yang terhapus maka itu adalah simpul tujuan, selanjutnya cetak biaya dan hentikan algoritmanya.
- Apabila tidak maka enqueue dari semua simpul saat ini ke priority queue dengan biaya totalnya dari root sebagai prioritas.
Node atau simpul root merupakan simpul awal untuk jalur pencarian, dan priority queue dipertahankan untuk tetap berada di jalur dengan anggaran paling rendah agar dapat dipilih pada traversal berikutnya. Apabila terdapat dua jalur yang mempunyai biaya traversal yang sama maka simpul diurutkan berdasarkan abjad.
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.
