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.
- 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.
 |
| https://chessprogramming.wikispaces.com/file/view/ideep.jpg/397640688/ideep.jpg |
Sumber :
http://socs.binus.ac.id/2013/04/23/uninformed-search-dan-informed-search/
https://tomatcoklat.wordpress.com/2012/02/19/artificial-intelligence-_/
https://en.wikipedia.org/wiki/Iterative_deepening_depth-first_search
http://adijinadiboy.blogspot.co.id/2013/04/metode-pencarian-artificial-intelejence_589.html
