METODE PENCARIAN (ARTIFICIAL INTELEJENCE) Uniform cost search (UCS)

Konsepnya hampir sama dengan BFS, bedanya adalah bahwa BFS menggunakan urutan level yang paling rendah sampai yang paling tinggi, sedangkan UCS menggunakan urutan biaya dari yang paling kecil sampai yang terbesar.

UCS berusaha menemukan solusi dengan total biaya terendah yang dihitung berdasarkan biaya dari simpul asal menuju ke simpul tujuan.

UCS adalah algoritma terbaik untuk masalah pencarian, yang tidak melibatkan penggunaan heuristik. Hal ini dapat memecahkan grafik umum untuk biaya yang optimal. UCS kedengarannya pencarian di cabang yang kurang lebih sama dalam biaya.

UCS lagi menuntut penggunaan antrian prioritas. Ingat bahwa Cari Pertama Kedalaman menggunakan antrian prioritas dengan kedalaman upto node tertentu menjadi prioritas dan jalur dari akar ke simpul menjadi elemen yang tersimpan. Antrian prioritas yang digunakan di sini adalah sama dengan prioritas menjadi biaya kumulatif upto node. Berbeda Cari Pertama Kedalaman dimana kedalaman maksimum memiliki prioritas maksimum, UCS memberikan biaya kumulatif minimum prioritas maksimal. Algoritma ini menggunakan antrian prioritas adalah sebagai berikut:

Insert the root into the queue
While the queue is not empty
      Dequeue the maximum priority element from the queue
      (If priorities are same, alphabetically smaller path is chosen)
      If the path is ending in the goal state, print the path and exit
      Else
            Insert all the children of the dequeued element, with the cumulative costs as priority

Sekarang mari kita menerapkan algoritma pada pohon pencarian di atas dan melihat apa yang memberi kita. Kami akan pergi melalui setiap iterasi dan melihat hasil akhir. Setiap elemen dari antrian prioritas ditulis sebagai

Inisialisasi: {[S, 0]}

Iteration1: {[S-> A, 1], [S-> G, 12]}

Iteration2: {[S-> A-> C, 2], [S-> A-> B, 4], [S-> G, 12]}

Iteration3: {[S-> A-> C-> D, 3], [S-> A-> B, 4], [S-> A-> C-> G, 4], [S-> G , 12]}

Iteration4: {[S-> A-> B, 4], [S-> A-> C-> G, 4], [S-> A-> C-> D-> G, 6], [S -> G, 12]}

Iteration5: {[S-> A-> C-> G, 4], [S-> A-> C-> D-> G, 6], [S-> A-> B-> D, 7] , [S-> G, 12]}

Iteration6 memberikan hasil akhir sebagai S-> A-> C-> G.

Hal yang perlu disebutkan:

-> Penciptaan pohon bukan merupakan bagian dari algoritma. Hal ini hanya untuk visualisasi.

-> Algoritma mengembalikan jalur pertama kali bertemu. Ia tidak mencari semua jalan.

-> Algoritma mengembalikan jalur yang optimal dari segi biaya.

Pada suatu titik tertentu dalam eksekusi, algoritma pernah memperluas node yang memiliki biaya yang lebih besar daripada biaya jalur terpendek dalam grafik. Unsur-unsur dalam antrian prioritas hampir biaya yang sama pada waktu tertentu, dan dengan demikian Uniform Cari nama Biaya. Ini mungkin tampak seolah-olah unsur tidak memiliki hampir biaya yang sama, dari contoh di atas. Tetapi ketika diterapkan pada grafik yang jauh lebih besar tentu begitu.

UCS juga dapat digunakan sebagai Pencarian Breadth Pertama jika semua ujung-ujungnya diberi biaya 1. Saya sebutkan sebelumnya bahwa UCS adalah algoritma terbaik yang tidak menggunakan heuristik. Kita akan melihat apa yang heuristik dan bagaimana mereka diterapkan dalam algoritma pencarian dalam posting mendatang.