Sekilas Tentang Uniform Cost Search & Iterative Deepening Search

Uniform Cost Search

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).

BFS

Penelusuran Ekspansi Node pada Breadth First Search. Sumber gambar: http://socs.binus.ac.id/files/2013/04/BFS.jpg

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 :


Iterative Deepening Search

Metode Iterative Deepening A* Iterative-Deepening A* (IDA*) search algorithm adalah pengembangan dari A*search algorithm yang dikombinasikan dengan iterative deepening search. IDA* search algorithm merupakan best-first searches yang optimal dalam hal solution cost, time, dan space. Prinsip algoritma iterative deepening search adalah melakukan depth-limited search secara bertahap dengan nilai l yang incremental . Contoh cara kerja iterative deepening search dapat dilihat pada gambar di bawah ini:

Untitled

Contoh Iterative Deepening Search. Sumber: Russel, Stuart J; Norvig, Peter. (2003). Artificial Intelligence : A Modern Approach 2nd Edition

Pada metode IDA* search algorithm digunakan fungsi evaluasi yang sama seperti metode A* yaitu sebagai berikut:

f(n) = g(n) + h(n) (6)

Dimana: f(n) = estimasi total cost suatu path dari node awal ke node tujuan melalui node n g(n) = cost dari suatu path untuk mencapai node n dari node awal h(n) = estimasi cost suatu path

Cara kerja IDA* adalah sebagai berikut :

  • (1) nilai threshold ditentukan;
  • (2) f(n) = g(n) + h(n) dihitung pada tiap iterasi;
  • (3) jika f(n) threshold maka node di-prune;
  • (5) jika goal node tercapai dengan price lebih kecil maka nilai threshold dikembalikan;
  • (6) jika seluruh iterasi telah berakhir tanpa mencapai goal node maka dimulai iterasi lain dengan nilai threshold yang lebih besar;
  • (7) nilai threshold yang baru adalah nilai minimum dari node yang di- prune pada iterasi sebelumnya;
  • (8) nilai threshold untuk iterasi pertama diatur ke nilai pada keadaan awal.
Sumber:

Russel, Stuart J; Norvig, Peter. (2003). Artificial Intelligence : A Modern Approach 2nd Edition

http://socs.binus.ac.id/2013/04/23/uninformed-search-dan-informed-search/

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

https://radityokuncoro.wordpress.com/2014/10/13/iterative-deepening-a/

Iklan

Tinggalkan Balasan

Isikan data di bawah atau klik salah satu ikon untuk log in:

Logo WordPress.com

You are commenting using your WordPress.com account. Logout / Ubah )

Gambar Twitter

You are commenting using your Twitter account. Logout / Ubah )

Foto Facebook

You are commenting using your Facebook account. Logout / Ubah )

Foto Google+

You are commenting using your Google+ account. Logout / Ubah )

Connecting to %s