KATA PENGANTAR
Puji syukur penulis panjatkan kehadirat Allah SWT yang telah memberikan rahmat serta karunia-Nya kepada kami sehingga kami berhasil menyelesaikan Makalah ini yang alhamdulillah tepat pada waktunya yang berjudul Artificial Intelligence metode Uniform Cost Search (UCS).
Tujuan penulisan makalah ini adalah untuk memenuhi salah satu tugas mata kulia Artificial Intellegence.
Makalah ini berisikan tentang informasi Pengertian, metode dan cara kerja UCS untuk mengambil sebuah solusi yang di inginkan. Diharapkan Makalah ini dapat memberikan informasi kepada kita semua.
Penulis menyadari bahwa Makalah ini masih jauh dari sempurna, oleh karena itu kritik dan saran dari semua pihak yang bersifat membangun selalu kami harapkan demi kesempurnaan Makalah ini.
Akhir kata, kami sampaikan terima kasih kepada semua pihak yang telah berperan serta dalam penyusunan Makalah ini dari awal sampai akhir. Semoga Allah SWT senantiasa meridhai segala usaha kita. Amiin.
Gresik, 02 April 2015
Penyusun
DAFTAR ISI
KATA PENGANTAR………………………………...…………………………………………
DAFTAR ISI…..……………………………………..………………………………………….
BAB 1 :…………………………………………………………………………………………..
PENDAHULUAN…………………………..………………..…………………………………..
1.1 LATAR BELAKANG………………………...……………………………………...….
1.2 RUMUSAN MASALAH………………………………………………………………...
1.3 TUJUAN PENULISAN……...…………………………………………………………..
BAB 11:………………………………………………………………………………………….
PEMBAHASAN…………………………………………………………………………………
2.1 Pengertian Uniform Cost Serch ………………………………………………………....
2.2 Konsep dan Cara Kerja Algoritma UCS………………………………………………….
2.3 Penerapan UCS dalam Algoritma………………………………………………………...
2.4 Keuntungan dan Kelemahan UCS………………………………………………………..
BAB III:……………………………………………………………………………………...…..
PENUTUP……………………………………………………………………………………..…
3.1 Kesimpulan…………………………………………………………………………........
DAFTAR PUSTAKA……………………………………………………………………………………..
BAB I
PENDAHULUAN
1.1 Latar Belakang
System AI, hal penting dalam menentukan keberhasilan system dalam kecerdasan adalah keberhasilan dalam pencarian dan kecocokan. Pada dasarnya ada dua teknik pencarian dan pelacakan yang digunakan, yaitu pencarian buta / tanpa informasi (blind / un-informed search) dan pencarian heuristik / dengan informasi (heuristic atau informed search) dimana setiap metode mempunyai karakteristik yang berbeda-beda dengan kelebihan dan kekurangan masing-masing. Apakah metode tersebut menjamin penemuan solusi jika solusinya memang ada, Berapa lama waktu yang diperlukan, Berapa banyak memori yang diperlukan, dan Apakah metode tersebut menjamin menemukan solusi yang terbaik jika terdapat beberapa solusi yang berbeda. Semua itu ditentukan sesuai metode apa yang akan kita pilih nanti. Adapun metode untuk searching itu sendiri diantaranya yaitu : Breadth-first search (BFS), Uniform cost search, Depth-first search (DFS), Depth-limited search, Iterative deepening search (IDS), Bidirectional search.
1.2 Rumusan Masalah
1. Apa pengertian UCS ?
2. Bagaimana metode atau algoritma UCS ?
3. Bagaimana cara kerja UCS ?
1.3 Tujuan
Tujuan dari Pembuatan Makalah ini, antara lain agar :
1. Mahasiswa mampu memahami apa itu pengertian UCS
2. Mahasiswa mampu mengetahui metode atau algoritma UCS.
3. Mahasiswa dapat mengetahui cara kerja UCS.
BAB II
PEMBAHASAN
2.1 pengertian Uniform Cost SerchSebelum menganalisis lebih dalam tentang persoalan ini , terlebih dahulu kami mencari referensi-referensi mengenai hal ini. Dari referensi-referensi yang kami dapatkan , maka kami memahami beberapa hal tentang apa itu Uniform Cost Search.
2.2 Konsep dan cara kerja Uniform Cost Serch
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). Teknik pencariannya memperhatikan cost/jarak antara 1 node ke node lain.
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.
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.
Contoh lebih detil tentang jalannya Algoritma Uniform Cost Serch adalah sebagai berikut :
Expansion showing the explored set and the frontier (priority queue):
Start Node: A
Goal Node: G
Step 1
Frontier:
Explored: –
Step 2:
Expand A
Frontier:
Explored: A
Step 3:
Expand D
Frontier:
Explored: AD
Step 4:
Expand A
Frontier:
Explored: ADB
Step 5:
Expand E
Frontier:
Explored: ADBE
Note: B was not added to the priority queue because it was already explored
Step 6:
Expand F
Frontier:
Explored: ADBEF
Step 7:
Expand C
Frontier:
Explored: ADBEFC
Step 8:
Expand G
Found the path: A ke D ke F ke G
Pseudocode :
procedure UniformCostSearch(Graph, root, goal)
node := root, cost = 0
frontier := empty priority queue containing node
explored := empty set
do
if frontier is empty
return failure
node := frontier.pop()
if node is goal
return solution
explored.add(node)
for each of node’s neighbors n
if n is not in explored
if n is not in frontier
frontier.add(n)
if n is in frontier with higher cost
replace existing node with n
2.3 Penerapan USC dalam Algoritma
Modifikasi BFS untuk mendapatkan biaya terendah sepanjang jalur pencarian, bukan hanya dilihat dari solusi yang didapat saja. (lowest cost vs. lowest depth)
Urutan biaya selalu menaik
o g(SUCCESSOR(n)) > g(n)
o g(n) = biaya jalur pencarian dari titik awal sampai node n.
Properti dari algoritma pencarian ini adalah: komplit, optimal / admissible, dan exponensial dalam kompleksitas waktu dan ruang, O(bd ).
Pada graf di atas, proses pencarian berlangsung sebagai berikut:
1. OPEN S (start)
2. OPEN A, B, C (cost = 1, 5, 15)
3. OPEN B, G, C (cost = 5, 11, 15)
4. OPEN G, G, C (cost = 10, 11, 15)
5. SOLUTION G (path S-B-G)
2.4 kelebihan dan keuntungan
Karena mengikuti konsep BFS, maka UCS menjamin ditemukannya solusi dan solusi yg ditemukannya selalu yg terbaik. Dgn kata lain, UCS adalahcomplete dan optimal.
Syarat yg harus dipenuhi oleh pohon UCS adalah g(successor(n) >= g(n) untuk setiap simpul n. Jika syarat ini tidak dipenuhi maka UCS menjadi tidak complete dan tidak optimal.
BAB III
PENUTUP
KESIMPULAN Uniform Cost search adalah suatu algoritma untuk menyelesaikan persoalan dimana dimulai dari node awal untuk mencari harga (cost) terkecil dari node selanjutnya.
Uniform Cost Serch hampir sama dengan BFS(Breadth-First Search) atau tepatnya sebagai penyempurna dari BFS.
DAFTAR PUSTAKA
https://tomatcoklat.wordpress.com/2012/02/19/artificial-intelligence-_/ / diakses pada 30 maret 2015 pukul 07.30
http://www.academia.edu/4924317/Seminar_Nasional_Informatika_SNIf_-_2013 / diakses pada 1 April 2015 pukul 07.30
https://muhlisthahir033.files.wordpress.com/2011/12/ai-05-dan-06.pdf /diakses pada 2 April 2015 pukul 15.23
Tidak ada komentar:
Posting Komentar