Sky_Heaven: Tugas Kecerdasan Buatan

Nama : Aji Sutrisna
NIM : 1305453

Uniform Cost Search dan Iterative Deepening Search

Dalam Algoritma pencarian ada 4 hal yang perlu diperhatikan saat membuat suatu algoritma yaitu

Completeness atau teknik tersebut menjamin penemuan solusi jika solusinya memang ada.
Time Complexity yaitu berapa lama waktu yang diperlukan.
Space Complexity yaitu berapa banyak ruang memori yang diperlukan.
Optimality yaitu apakah teknik tersebut menjamin menemukan solusi yang terbaik jika terdapat beberapa solusi yang berbeda

Maka dari itu algoritma yang baik adalah yang memenuhi semua hal yang diatas.

Uniform Cost Search

Uniform Cost Search merupakan salah satu teknik pencarian yang termasuk pada Uninformed Search (Blind Search). Pada Uninformed Search Algoritm informasi yang disediakan akan menjadi informasi kunci saat pencarian berlangsung, karena pada algoritma ini tidak ada informasi tambahan yang digunakan.

Dalam UCS (Uniform Search Search) memiliki konsep yang hampir mirip dengan BFS (Breadth First Search) karena UCS merupakan gabungan dari konsep BFS dengan konsep DFS (Depth First Search), bedanya BFS menggunakan urutan level dari yang paling rendah hingga tertinggi, sedangkan dalam UCS berusaha menemukan solusi dengan biaya terendah yang dihitung berdasarkan biaya dari node asal ke node tujuan.

Dalam menggunakan UCS memiliki syarat yang harus dipenuhi agar bisa optimal dan complete, yaitu g(SUCCESSOR(n)) >= g(n) untuk setiap node N. Karena bila syarat ini tidak bisa dipenuhi maka UCS tidak bisa digunakan.

catatan :

g(n) = biaya simpal dari simpul asal ke simpul n.

Kelebihan dan kekurangan UCS.

Dalam algoritma UCS memiliki kelebihan sebagai berikut.

Karena memiliki konsep seperti BFS maka UCS menjamin ditemukannya solusi dan solusi yang ditemukannya selalu solusi yang terbaik dalam kata lain UCS merupakan pencarian yang complete dan optimal.
Sangat cocok digunakan bila tidak menggunakan heuristik. karena butuh completeness dalam menemukan setiap solusi.

Kekurangan algoritma UCS sebagai berikut.

Memiliki syarat yang harus dipenuhi agar bisa complete dan optimal.
Memiliki kompleksitas waktu dan ruang yang banyak karena memakai konsep BFS. Komplesitas nya yaitu O(b^d).

Ilustrasi UCS bisa diskemakan sebagai berikut.

https://tomatcoklat.files.wordpress.com/2012/02/1.png

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

Algoritma ini dimplementasikan dalam vaccum problem dimana ruangan yang asalnya kotor harus menjadi bersih dengan menggunakan vaccum otomatis.

Iterative Deepening Search

IDS (Iterative Deepening Search) merupakan algoritma pencarian yang mengkombinasikan antara keunggulan dari BFS (complete dan optimal) dengan keunggulan dari DFS (space complexity), tapi memiliki kekurangan yaitu dari segi time complexity (Ob^d).

Dalam IDS pencarian dilakukan secara iteratif (menggunakan penelusuran DFS) dimulai dari batasan level 1. Jika belum ditemukan solusi maka dilakukan iterasi lagi hingga solusi ditemukan. Jika solusi ditemukan tidak perlu melakukan proses backtracking (penelusuran balik untuk mendapatkan jalur yang diinginkan).

Keunggulan dari IDS sebagai berikut

merupakan algoritma yang complete, optimal.
memiliki space complexity yang kecil karena merupakan gabungan dari BFS dan DFS.

Kelemahan dari IDS hanya satu yang fatal yaitu time complexity yang tinggi. Karena time complexity yang tinggi maka kita bisa melakukan percepatan dengan melakukan teknik parralel processing (menggunakan lebih dari satu proccesor)