UCS dan IDS

Uniform Cost Search (UCS)

               Uniform Cost Search adalah algoritma Seach Tree (graph) yang digunakan untuk menyelesaikan beberapa persoalan . Algoritma ini memulai pencarian dari root node, kemudian dilanjutkan ke node-node selanjutnya. Dimana node tersebut dipilih yang memilki harga (cost) terkecil dari root node. Algoritma ini merupakan modifikasi dari Bread First Search (BFS).

Dalam implementasi algoritma ini , melibatkan semua node yang berhubungan dengan root node, dan meletakannya dalam priority queue untuk mencapai node tujuan. Dimana node – node yang dipilih merupakan node yang berharga terkecil.

Ilustrasi jalannya algoritma Uniform Cost Search dapat digambarkan sebagai berikut :

Seperti tampak pada gambar, initial state terletak pada node start, kemudian untuk mencapai node berikutnya, algoritma ini memilih jalur yang memilki harga terkecil diantara dua node di depannya. Begitu seterusnya, dilakukan pengecekan node yang memilki harga terkecil hingga sampai pada goal state.

Contoh lebih detil tentang jalannya Algoritma Uniform Cost Serch adalah sebagai berikut :

Contoh kedua :

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.

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

Iterative Deepening Search (IDS)

                Iterative deepening search atau  iterative deepening depth-first search adalah strategi umum, sering digunakan dalam kombinasi dengan pencarian mendalam pertama, yang menemukan batas kedalaman terbaik. Hal ini secara bertahap meningkatkan batas-pertama 0, maka 1, kemudian 2, dan seterusnya sampai tujuan ditemukan.

Hal ini akan terjadi ketika batas kedalaman mencapai d, kedalaman node tujuan yang dangkal. Pendalaman berulang menggabungkan manfaat dari kedalaman pertama dan luasnya pertama pencarian. Seperti pencarian depth-first, persyaratan memori yang sangat sederhana: O(bd) harus tepat. Seperti pencarian breadth-first, itu selesai ketika faktor percabangan adalah terbatas dan optimal ketika biaya jalan adalah fungsi dari kedalaman node. Gambar 3.15 menunjukkan empat iterasi pada IDS pada pencarian pohon biner, di mana solusinya ditemukan pada iterasi keempat.

IDS mungkin tampak boros, karena iterasi yang dihasilkan beberapa kali. Ternyata ini tidak terlalu bagus. Alasannya adalah bahwa dalam sebuah pohon pencarian dengan sama (atau hampir sama) bercabang faktor pada setiap tingkat, sebagian besar node berada di tingkat bawah, sehingga tidak peduli banyak yang tingkat atas yang dihasilkan beberapa kali. Dalam sebuah berulang memperdalam pencarian, node pada tingkat bawah (kedalaman d) dihasilkan sekali, orang-orang di sebelah tingkat bawah yang dihasilkan dua kali, dan seterusnya, sampai anak-anak dari akar, yang dihasilkan d kali. Jadi jumlah total node yang dihasilkan

N(1DS) = (d) b + (d - l)b2 + . . . + (1) bd ,

yang memberikan kompleksitas waktu O (bd). Kita dapat membandingkan ini dengan node yang dihasilkan oleh breadth-first pencarian:

N(BFS) = b + b2 + . . . + bd + (bdtl - b) .

Perhatikan bahwa pencarian breadth first menghasilkan beberapa node pada kedalaman d + 1, sedangkan pendalaman berulang tidak. Hasilnya adalah bahwa pendalaman berulang sebenarnya lebih cepat daripada pencarian breadth-first, meskipun generasi berulang. Sebagai contoh, jika b = 10 dan d = 5, jumlahnya

N(IDS) = 50+400+3.000+20.000+100.000 = 123.450

N(BFS) = 10+100+1.000+10.000+100.000+999.990 = 1.111.100

Jadi IDS merupakan metode yang menggabungkan kelebihan BFS (Complete dan Optimal) dengan kelebihan DFS (space complexity rendah atau membutuhkan sedikit memori).

Tetapi konsekwensinya adalah time complexitynya menjadi tinggi.

Referensi:

Russel and Norvig, Artificial Intelligence: a Modern Approach, Prentice Hall, 1995

https://tomatcoklat.wordpress.com/2012/02/19/artificial-intelligence-_/

http://adijinadiboy.blogspot.co.id/2013/04/metode-pencarian-artificial-intelejence_589.html

http://kuliahkusayang.blogspot.co.id/2010/04/teknik-searching.html
http://zakki.dosen.narotama.ac.id/files/2012/02/KECERDASAN-BUATAN-ARTIFICIAL-INTELLIGENCE.ppt