Uniform
Cost Search
Metode ini
adalah perpaduan antara BFS dan DFS
pada UCS, pencarian nya mempehatikan cost/jarak
antara 1 node ke node lain.
Contoh nya.
pada permasalahan diatas telah ditentukan jarak antara node. maka pada ucs akan membuka node yang memiliki nilai/cost antar node yang terendah.
pada gambar diatas jika kita buka
c = 10
b = 20
a = 10
karena nilai c dan a sama maka teserah mau buka yang mana lebih dahulu.
seandainya kita mebuka c maka kita teruskan pencariannya, jika kita buka
d = 10+5 =15
e = 10+40 = 50 (mencapai goal, namun nilai cost nya dirasa masih terlalu besar)
maka kita buka node d, lalu akan didapat
e = 10+5+30 = 45 (nilai pada pencarian ini pun terasa masih terlau besar) maka dari itu kita buka node yang kecil di awal tadi yaitu node a
setelah kita buka node a akan di dapat
e = 10 + 20 = 30 (di dapatkan goal dengan solusi terbaik)
dari kasus diatas dapat kita lihat, ada banyak cara unuk mendapatkan solusi. namun dari berbagai macam penyelesaian kasus, kita dapat mencari solusi yang paling optimal dan ini lah ke unggulan dari UCS
Pencarian dengan Breadth First Search akan menjadi optimal ketika nilai pada semua path adalah sama. Dengan sedikit perluasan, dapat ditemukan sebuah algoritma yang optimal dengan melihat kepada nilai tiap path di antara node-node yang ada.
Selain menjalankan fungsi algoritma BFS, Uniform Cost
Search melakukan ekspansi node dengan nilai path yang paling kecil. Hal ini
bisa dilakukan dengan membuat antrian pada successor yang ada berdasar kepada
nilai path-nya (node disimpan dalam bentuk priority queue).
Iterative Depeending Search
Iterative
deepening search merupakan sebuah strategi umum yang biasanya dikombinasikan
dengan depth first tree search, yang akan menemukan berapa depth limit terbaik
untuk digunakan. Hal ini dilakukan dengan secara menambah limit secara
bertahap, mulai dari 0,1, 2, dan seterusnya sampai goal sudah ditemukan.
Metode
ini adalah sebuah metode yang menggabungkan
kelebihan yang ada pada BFS dan DFS namun memiliki konsekuensi yaitu adanya
kompleksitas waktu yang tinggi karena IDS adalah sebuah algoritma search yang
menggunakan batasan level pada setiap iterasi pencarian yang berupa f limit
nilai gabungan antara nilai sebenarnya dengan nilai perkiraan , pada IDS
memungkinkan setiap simpul simpul berulang ulang di gunakan inilah yang
menyebabkan memungkinkan adanya kompleksitas waktu yang tinggi.
