Kecerdasan Buatan Teknik Pencarian UCS (Uniform Cost Search)

Uniform Cost Search adalah salah satu algoritma terbaik untuk masalah pencarian, yang tidak melibatkan penggunaan heuristik. Algoritma ini dapat menyelesaikan masalah biaya optimal pada graf umum. Uniform cost search, melakukan pencarian di cabang-cabang yang memiliki harga seragam (hampir sama). Untuk mengukur performansi teknik pencarian, terdapat empat kriteria yang dapat digunakan, yaitu:

• Completeness: Apakah teknik tersebut menjamin penemuan solusi jika solusinya memang ada?
• Time complexity : Berapa lama waktu yang diperlukan?
• Space complexity : Berapa banyak ruang memori yang diperlukan?
• Optimality: Apakah teknik tersebut menjamin menemukan solusi yang terbaik jika terdapat beberapa solusi yang berbeda?

 

Perbedaan BFS dengan UCS

Konsepnya hampir sama dengan BFS, bedanya adalah bahwa BFS menggunakan urutan level dari yg paling rendah sampai yg paling tinggi. Sedangkan UCS berusaha menemukan solusi dengan total biaya terendah yang dihitung berdasarkan biaya dari simpul asal menuju ke simpul tujuan. Biaya dari simpul asal ke suatu simpul n dilambangkan sebagai g(n).

 

UCS menjamin ditemukannya solusi dan solusi yg ditemukannya selalu yg terbaik. Dgn kata lain, UCS adalah complete dan optimal. Syarat yg harus dipenuhi oleh pohon UCS adalah g(successor(n) >= g(n) untuk setiap simpul n. Jika syarat ini tidak dipenuhi maka UCS menjadi tidak complete dan tidak optimal. Uniform Cost Search menggunakan priority queue (antrian prioritas).

Pada contoh kasus gambar diatas, dapat dijabarkan iterasiny sebagai berikut:

Initialisasi : { [ S , 0 ] }
Iterasi 1 : { [ S->A , 1 ] , [ S->G , 12 ] }
Iterasi 2 : { [ S->A->C , 2 ] , [ S->A->B , 4 ] , [ S->G , 12] }
Iterasi 3 : { [ S->A->C->D , 3 ] , [ S->A->B , 4 ] , [ S->A->C->G , 4 ] , [ S->G , 12 ] }
Iterasi 4 : { [ S->A->B , 4 ] , [ S->A->C->G , 4 ] , [ S->A->C->D->G , 6 ] , [ S->G , 12 ] }
Iterasi 5 : { [ S->A->C->G , 4 ] , [ S->A->C->D->G , 6 ] , [ S->A->B->D , 7 ] , [ S->G , 12 ] }
Iterasi 6 mengeluarkan output final yaitu S->A->C->G

 

Di setiap iterasinya, algoritma ini tidak pernah melanjutkan node yang memiliki cost lebih besar dari cost kumulatif yang terkecil.  Elemen di antrian prioritas memiliki cost yang hampir sama dalam satu iterasi, karena itu disebut Uniform Cost Search. Di contoh diatas mungkin keseragaman cost tidak terlihat, tetapi jika digunakan pada graf yang lebih besar akan terlihat.