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).
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:
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 : banyurachman.wordpress.com
