Kamis, 15 Oktober 2020
Software Development Life Cycle (SDLC) - RAD MODEL
Selasa, 13 Oktober 2020
Uniform Cost Search
Uniform Cost Search
Searching secara umum dapat dibagi menjadi Uninformed Search dan Informed Search. Uninformed Search sering disebut sebagai Blind Search. Istilah ini menggambarkan bahwa teknik pencarian ini tidak memiliki informasi atau pengetahuan tambahan mengenai kondisi di luar dari yang telah disediakan oleh definisi masalah.
Uninformed Search terdiri dari beberapa algoritma, di antaranya adalah:
Breadth-First Search (BFS)
Uniform-Cost Search(UCS)
Depth-First Search
Depth-Limited Search
Iterative Deepening
Pada artikel ini, akan dibahas mengenai Uniform-Cost Search (UCS).
Jika seluruh edges pada graph pencarian tidak memiliki cost / biaya yang sama, maka BFS dapat digeneralisasikan menjadi uniform cost search
Bila pada BFS, pencarian dilakukan dengan melakukan ekspansi node berdasarkan urutan kedalaman dari root, maka pada uniform cost search, ekspansi dilakukan berdasarkan cost / biaya dari root.
Pada setiap langkah, ekspansi berikutnya ditentukan berdasarkan cost terendah atau disebut sebagai fungsi g(n) dimana g(n) merupakan jumlah biaya edge dari root menuju node n. Node-node tsb disimpan menggunakan priority queue.
Algoritma UCS dapat d hargailihat pada gambar berikut:
Perhatikan contoh pada gambar berikut ini. Nilai pada edge menandakan cost atau disebut juga g(n).
Penelusuran menggunakan UCS dari S ke G akan berjalan sebagai berikut.
Frontier bernilai S
Dari S, kita dapat menuju A, C, K dengan nilai 2,1,2. Untuk menyimpan pada frontier, perlu dilakukan sorting berdasarkan cost terendah. Sehingga dapat kita tuliskan f = C, A, K dengan cost 1,2,2
Selanjutnya kita ekspansi C (yang paling rendah). Dari C kita bisa menuju D. cost dari C ke D adalah 1. namun, merujuk pada algoritma UCS, g(n) merupakan jumlah cost dari root menuju node n, maka g(n) untuk D dari C adalah 1 + cost sebelumnya menuju C yaitu 1 sehingga g(n) untuk D dari C adalah 2. Urutkan lagi berdasarkan cost.
References
Stuart Russell, Peter Norvig,. 2010. Artificial Intelligence : a modern approach. PE. New Jersey. ISBN:9780132071482
KECERDASAN BUATAN
Dalam bahasan kecerdasan buatan sebuah software/ hardware disebut cerdas jika memiliki kemampuan untuk searching, reasoning, planning dan le...
-
Pada saat ini perkembangan teknologi telah masuk pada berbagai bidang kehidupan manusia, diantaranya pada proses jual beli, pemesanan, pe...
-
Hallo semuanya selamat datang di blog saya perkenalkan nama saya Hilmi saya seorang mahasiswa di Universitas Muhammadiyah Sukabumi pro...