Halaman

Minggu, 20 September 2015

Uniform Cost Search (UCS) dan Iterative-Deepening Search (IDS)

Uniform Cost Search (UCS)

Uniform Coast Search merupakan algoritma berupa Search Tree atau bisa disebut juga sebagai algoritma graph. Algoritma ini digunakan untuk menyelesaikan beberapa persoalan. Algoritma ini memulai pencariannya dari root node, kemudian dilanjutkan ke node-node selanjutnya. Dimana node tersebut dipilih sesuai dengan yang memiliki harga (cost) terkecil dari root node. Algoritma ini juga merupakan modifikasi dari Bread First Search (BFS).

Dalam implrmrntasi algoritma ini melibatkan semua node yang berhubungan dengan root node dan meletaknnya dalam priority queue untuk mencapai node tujuan. dimana node-node yang dipilih merupakan node yang memiliki harga paling kecil.

Ilustrasi dari jalannya algoritma Uniform Cost Search dapat digambarkan sebagai berikut :


Dapat dilihat pada gambar diatas, initial state pada node start, kemudain untuk mencapai node berikutnya, algoritma ini memilih jalur yang memiliki harga terkecil diantar dua node berikutnya. begitu seterusnya, dilakukan pengecekan node yang memiliki harga terkecil hingga sampai pada goal state.

Konsep dasar Uniform Cost Serch hampir sama dengan BFS(Breadth-First Search), bedanya adalah bahwa BFS menggunakan urutan level yang paling rendah sampai yang paling tinggi, sedangkan UCS menggunakan urutan biaya dari yang paling kecil sampai yang terbesar. 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 (IDS) merupakan metode yang menggabungkan kelebihan BFS (Complete dan Optimal) dengan kelebihan DFS (space complexity rendah atau membutuhkan sedikit memori).

IDS menggabungkan depth-first pencarian ruang-efisiensi dan kelengakapan luas-pertama pencarian ini (ketika faktor percabangan terbatas). Ini adalah optimal ketika biaya jalan adalah fungsi penurunan kedalaman node.

Kompleksitas ruang IDS adalah, dimana merupakan faktor percabangan dan kedalaman dangkal gawang karena berulang memperdalam kunjungan menyatakan beberapa kali. hal itu mungkin tampak sia-sia, tapi ternyata menjadi tidak begitu mahal, karena dipohon sebagian besar node berada di tingkat bawah, sehingga tidak terlalu menjadi masalah jika tingkat atas yang dikunjungi beberapa kali.


Diposting oleh di Tidak ada komentar:
Langganan: Postingan (Atom)