Uniform Cost Search dan Iterative Depeending Search

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.