Lompat ke konten Lompat ke sidebar Lompat ke footer

Apa itu Uniform-Cost Search? Pengertian dan Cara Kerjanya

Algoritma pencarian dapat dibedakan menjadi dua jenis, yakni uninformed search dan informed search. Perbedaan antara kedua jenis algoritma pencarian tersebut terletak pada ada tidaknya informasi atau pengetahuan tambahan mengenai kondisi selain dari yang telah disediakan oleh definisi masalah.

Uninformed search adalah teknik pencarian yang tidak memiliki informasi tambahan dan karenanya disebut juga dengan teknik pencarian buta (blind search). Salah satu algoritma uninformed search adalah Uniform-Cost Search.

Apa itu Algoritma Uniform-Cost Search? Pengertian dan Cara Kerjanya

Apa itu algoritma Uniform-Cost Search?

Kita akan membahasnya secara lebih lengkap di artikel berikut. Yuk, kita mulai!

Daftar Isi

Pengertian Algoritma Uniform-Cost Search

Uniform-Cost Search merupakan algoritma pencarian tanpa informasi (uninformed search) yang menggunakan biaya kumulatif terendah untuk menemukan jalur dari node sumber ke node tujuan.

Algoritma ini beroperasi di sekitar ruang pencarian berbobot terarah untuk berpindah dari node awal ke salah satu node akhir dengan biaya akumulasi minimum.

Algoritma Uniform-Cost Search masuk dalam algoritma pencarian uninformed search atau blind search karena bekerja dengan cara brute force, yaitu tidak mempertimbangkan keadaan node atau ruang pencarian.

Algoritma ini umumnya digunakan untuk menemukan jalur dengan biaya kumulatif terendah dalam graph berbobot di mana node diperluas sesuai dengan biaya traversalnya dari node root.

Biasanya algoritma Uniform-Cost Search diimplementasikan dengan menggunakan priority queue di mana prioritasnya adalah menurunkan biaya operasi.

Uniform-Cost Search juga dapat disebut sebagai varian dari algoritma Dijikstra. Hal ini karena pada uniform cost search, alih-alih memasukkan semua simpul ke dalam antrian prioritas (priority queue), kita hanya menyisipkan node sumber, lalu memasukkan satu per satu bila diperlukan.

Di setiap iterasi, kita memeriksa apakah item sudah dalam antrian prioritas (menggunakan array yang dikunjungi). Jika ya, kita melakukan kunci penurunan, jika tidak, kita memasukkan item tersebut ke dalam antrian.

Cara Kerja Algoritma Uniform-Cost Search

Berikut adalah cara kerja algoritma uniform-cost search:

  1. Masukkan node root ke dalam priority queue
  2. Ulangi langkah berikut saat antrian (queue) tidak kosong:
    • Hapus elemen dengan prioritas tertinggi
    • Jika node yang dihapus adalah node tujuan, cetak total biaya (cost) dan hentikan algoritma
    • Jika tidak, enqueue semua child dari node saat ini ke priority queue, dengan biaya kumulatifnya dari root sebagai prioritas

Di sini node root adalah node awal untuk jalur pencarian, dan priority queue tetap untuk mempertahankan jalur dengan biaya paling rendah untuk dipilih pada traversal berikutnya. Jika 2 jalur memiliki biaya traversal yang sama, node diurutkan berdasarkan abjad.

Time complexity pada algoritma uniform cost search dapat dirumuskan:

O(b(1 + C / ε))

Dimana:

  • b - branching factor
  • C - biaya optimal
  • ε - biaya setiap langkah

Berikut adalah contoh cara algoritma uniform cost search beroperasi:

Misalkan kita memiliki graph berbobot sebagai berikut. Kita ingin menelusuri destinasi dengan biaya terendah menggunakan algoritma UCS

Sumber: educative.io

Pertama, kita masukkan node root atau node sumber ke antrian (queue):

Sumber: educative.io
Kemudian, kita tambahkan child node milik node root ke dalam priority queue dengan jarak kumulatifnya sebagai prioritas:
Sumber: educative.io

A memiliki jarak minimum (prioritas maksimum), sehingga diekstraksi dari daftar. Karena A bukan node tujuan, child node ditambahkan ke priority queue.

Sumber: educative.io

Sekarang B memiliki prioritas maksimum, jadi child node ditambahkan ke queue:

Sumber: educative.io

Selanjutnya, G akan dihapus dan turunannya akan ditambahkan ke queue:

Sumber: educative.io

C dan I memiliki jarak yang sama, jadi kita akan menghapus menurut abjad:

Selanjutnya, kita menghapus I; namun, I tidak memiliki node child lagi, jadi tidak ada pembaruan pada antrean. Setelah itu, kita menghapus node D.

D hanya memiliki satu child, E, dengan jarak kumulatif 10. Namun, E sudah ada di antrian dengan jarak yang lebih kecil, jadi kita tidak akan menambahkannya lagi.

Jarak minimum berikutnya adalah jarak dari E, jadi node tersebut kita hilangkan:

Sumber: educative.io

Sekarang, biaya minimum adalah F, sehingga akan dihapus dan turunannya (J) akan ditambahkan:

Sumber: educative.io

Setelah itu, H memiliki biaya minimum sehingga akan dihapus, tetapi tidak memiliki child node untuk ditambahkan:

Sumber: educative.io

Terakhir, kita menghapus node tujuan, memeriksa apakah node tersebut adalah target kita, dan menghentikan algoritma di sini.

Jarak minimum antara node sumber dan tujuan telah ditemukan, yaitu 8.

Kelebihan dan Kekurangan Uniform Cost Search

Berikut adalah kelebihan dan kekurangan dari algoritma uniform cost search:

Kelebihan

  • Membantu untuk menemukan jalur dengan biaya kumulatif terendah di dalam graph berbobot dimana jalur memiliki biaya berbeda dari simpul root ke simpul tujuan.
  • Algoritma Uniform Cost Search dapat dianggap sebagai solusi optimal, karena pada setiap keadaan, jalur yang diikuti adalah jalur dengan rute terpendek.

Kekurangan

  • Daftar terbuka harus tetap diurutkan karena prioritas dalam priority queue perlu dipertahankan.
  • Dibutuhkan penyimpanan besar karena semakin banyak node maka ukuran penyimpanan meningkat secara eksponensial.
  • Algoritma dapat terjebak dalam kondisi infinite loop karena perlu mempertimbangkan setiap kemugkinan jalur dari node root ke node tujuan.

Penutup

Demikianlah penjelasan singkat mengenai algoritma Uniform-Cost Search. Semoga informasi yang disajikan dapat bermanfaat dan menambah wawasan pengetahuan kita.

Apabila Anda tertarik dengan artikel seperti ini, Anda dapat mengunjungi rubrik Data Structure atau membaca artikel lainnya mengenai algoritma Depth First Search

Referensi:

Trivusi
Trivusi Ikatlah ilmu dengan menulis. Menebar manfaat dengan berbagi :)

Posting Komentar untuk "Apa itu Uniform-Cost Search? Pengertian dan Cara Kerjanya"