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).
Uniform Cost Search menggunakan priority queue (antrian prioritas). Algoritma menggunakan antrian prioritas ini adalah sebagai berikut:
Masukkan root ke dalam antrian
While antrian not empty
Pilih elemen dengan prioritas maksimum dari antrian (dalam hal ini cost terkecil)
If prioritas sama, jalur dipilih secara alphabetis terkecil
If jalur sampai ke goal state, print jalur and exit
Else
Masukkan semua children dari elemen yang dipilih, dengan cost kumulatif sebagai prioritas (cost terkecil memiliki prioritas terbesar)
Contoh penggunaan algoritma diatas pada pohon pencarian. Algoritma ditulis setiap iterai. Setiap elemen dari antrian prioritas ditulis [jalur, cost kumulatif].
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.
Iterative Deepening Search (IDS)
IDS merupakan metode yang menggabungkan kelebihan BFS (Complete dan Optimal) dengan kelebihan DFS (space complexity rendah atau membutuhkan sedikit memori). Tetapi konsekuensinya adalah time complexitynya menjadi tinggi.
IDS beroperasi seperti depth-first search, kecuali sedikit lebih dibatasi - ada kedalaman maksimum yang mendefinisikan berapa banyak level algoritma dapat mencari solusi. Sebuah node pada tingkat maksimum kedalaman diperlakukan sebagai terminal, meskipun biasanya akan memiliki node penggantinya. Jika pencarian "gagal," maka tingkat kedalaman maksimum bertambah satu dan proses mengulangi. Nilai untuk kedalaman maksimum pada awalnya ditetapkan sebesar 0 (yaitu, hanya node awal).
Visited Node
|
Current Node
|
|
 |
  |
||
Node awal dicek dengan goal state. Karena pencarian tidak dapat dilanjutkan, maka pencarian "gagal".
|
Tingkat kedalaman maksimum ditingkatkan menjadi 1. Kemudian pencarian dimulai dari awal. Kali ini, karena tingkat kedalaman maksimum adalah 1 maka pencarian dapat dilanjutkan.
|
Pencarian "gagal" karena goal state tidak ditemukan pada setiap node di tingkat kedalaman 1. Pencarian dimulai kembali dengan tingkat kedalaman maksimum 2.
|
Pencarian dilanjutkan hingga solusi (goal) ditemukan.
Satu hal yang menarik adalah node dalam pencarian ini pertama dicek dalam urutan yang sama dengan breadth-first-search. Tetapi, karena node dihapus seiring dengan berlanjutnya pencarian, maka memori yang digunakan lebih sedikit.
Kelemahan pencarian ini adalah redundansi, pengecekan kembali setiap node yang telah dicek dalam setiap iterasinya. Algoritma ini dapat ditingkatkan dengan mengingat node yang telah dicek, tetapi hal ini akan mengorbankan efisiensi memori yang membuat algoritma ini lebih dari BFS atau DFS.
Sumber :
http://web.stanford.edu/~msirota/soco/inter.html
https://algorithmicthoughts.wordpress.com/2012/12/15/artificial-intelligence-uniform-cost-searchucs/
Tidak ada komentar:
Posting Komentar