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