People Innovation Excellence

Searching: Uniform Cost Search

Searching secara umum dapat dibagi menjadi Uninformed Search dan Informed Search. Uninformed Search sering disebut sebagai Blind Search. Istilah ini menggambarkan bahwa teknik pencarian ini tidak memiliki informasi atau pengetahuan tambahan mengenai kondisi di luar dari yang telah disediakan oleh definisi masalah.

Uninformed Search terdiri dari beberapa algoritma, di antaranya adalah:

  1. Breadth-First Search (BFS)
  2. Uniform-Cost Search(UCS)
  3. Depth-First Search
  4. Depth-Limited Search
  5. Iterative Deepening

Pada artikel ini, akan dibahas mengenai Uniform-Cost Search (UCS).

Jika seluruh edges pada graph pencarian tidak memiliki cost / biaya yang sama, maka BFS dapat digeneralisasikan menjadi uniform cost search

Bila pada BFS, pencarian dilakukan dengan melakukan ekspansi node berdasarkan urutan kedalaman dari root, maka pada uniform cost search, ekspansi dilakukan berdasarkan cost / biaya dari root.

Pada setiap langkah, ekspansi berikutnya ditentukan berdasarkan cost terendah atau disebut sebagai fungsi g(n) dimana g(n) merupakan jumlah biaya edge dari root menuju node n. Node-node tsb disimpan menggunakan priority queue.

Algoritma UCS dapat dilihat pada gambar berikut:

Perhatikan contoh pada gambar berikut ini. Nilai pada edge menandakan cost atau disebut juga g(n).

Penelusuran menggunakan UCS dari S ke G akan berjalan sebagai berikut.

  1. Frontier bernilai S
  2. Dari S, kita dapat menuju A, C, K dengan nilai 2,1,2. Untuk menyimpan pada frontier, perlu dilakukan sorting berdasarkan cost terendah. Sehingga dapat kita tuliskan f = C, A, K dengan cost 1,2,2
  3. Selanjutnya kita ekspansi C (yang paling rendah). Dari C kita bisa menuju D. cost dari C ke D adalah 1. namun, merujuk pada algoritma UCS, g(n) merupakan jumlah cost dari root menuju node n, maka g(n) untuk D dari C adalah 1 + cost sebelumnya menuju C yaitu 1 sehingga g(n) untuk D dari C adalah 2. Urutkan lagi berdasarkan cost.

References

  • Stuart Russell, Peter Norvig,. 2010. Artificial Intelligence : a modern approach. PE. New Jersey. ISBN:9780132071482

 


Published at : Updated
Written By
Rini Wongso, S.Kom., M.T.I
Subject Content Coordinator Intelligent Systems | School of Computer Science

Periksa Browser Anda

Check Your Browser

Situs ini tidak lagi mendukung penggunaan browser dengan teknologi tertinggal.

Apabila Anda melihat pesan ini, berarti Anda masih menggunakan browser Internet Explorer seri 8 / 7 / 6 / ...

Sebagai informasi, browser yang anda gunakan ini tidaklah aman dan tidak dapat menampilkan teknologi CSS terakhir yang dapat membuat sebuah situs tampil lebih baik. Bahkan Microsoft sebagai pembuatnya, telah merekomendasikan agar menggunakan browser yang lebih modern.

Untuk tampilan yang lebih baik, gunakan salah satu browser berikut. Download dan Install, seluruhnya gratis untuk digunakan.

We're Moving Forward.

This Site Is No Longer Supporting Out-of Date Browser.

If you are viewing this message, it means that you are currently using Internet Explorer 8 / 7 / 6 / below to access this site. FYI, it is unsafe and unable to render the latest CSS improvements. Even Microsoft, its creator, wants you to install more modern browser.

Best viewed with one of these browser instead. It is totally free.

  1. Google Chrome
  2. Mozilla Firefox
  3. Opera
  4. Internet Explorer 9
Close