pemecahanmasalahdengan...
TRANSCRIPT
3/12/2018
1Pemecahan Masalah denganMetoda Pencarian (Searching)• Problem-Solving Agent (PSA)• Memutuskan tindakan yang harusdilakukan untuk mencapai hasil yangdiinginkan.• Dengan cara : mengidentifikasi tiap urutanaksi yang mendahuluinya.• Sasaran Problem-Solving Agent, adalahmencapai suatu Goal yang diinginkan (PSAmerupakan Tipe Goal-Based Agents).
3/12/2018
2
environment
agent
?
sensors
actuators
o Formulate Goal o Formulate Problem
� Intial States� Actions� Goal Test� Path Cost
o Find Solutiono Execution
Problem-Solving Agent (PSA)Mekanisme kerjaProblem-Solving Agent• Formulate Goal (Merumuskan Tujuan)Tentukan tujuan yang ingin dicapai.• Formulate Problem (Merumuskan Permasalahan)Tentukan tindakan (action) & keadaan (state) yang dipertimbangkan dalam mencapai tujuan.• Find Solution (Mencari Solusi Masalah)Tentukan rangkaian tindakan yang perlu diambil untukmencapai tujuan.• Execution (Pelaksanaan Solusi)Laksanakan rangkaian tindakan yang sudah ditentukan di tahap sebelumnya.
3/12/2018
3
Contoh : Turis di Romania• Liburan ke Romania, khususnya : Arad. Penerbangan dilakukan besok dari Bucharest.Contoh : Turis di Romania• Formulate GoalBerada di Bucharest• Formulate Problem– States : Kota-kota– Actions : Perjalanan antar kota-kota• Find Solution– Sederatan kota-kota yang menghasilkan jarakterpendek : Arad, Sibiu, Fagaras, Bucharest.• Execution
3/12/2018
4
Contoh : Turis di RomaniaGoal
Start
States
Actions
SolutionTipe Masalah (Problem)• Single State Problem Deterministic, Fully Observable• Multiple State Problem Deterministic, Partially Observable• Contingency Problem Stochastic, Partially Observable• Exploration Problem Unknown state space
3/12/2018
5
Single State Problem• Deterministic, Fully Observable–Agent mengetahui tentanglingkungannya (exact state)–Dapat memperhitungkan sederetanaction yang optimal untuk mencapaigoal state–Contoh : Bermain catur , setiap action akanmenghasilkan state yang pastiMultiple State Problem• Deterministic, Partially Observable– Agent tidak mengetahui exact state (bisa beberapa kemungkinan state)– Mendapatkan state ketika bekerjamencapai goal state.Contoh : Berjalan diruangan gelap :� Jika berada dipintu, berjalan terus akanmembawa kita kedapur.� Jika kita berada didapur, belok kiri akanmembawa kita ke kamar mandi,dll.
3/12/2018
6
Contingency Problem• Stochastic, Partially Observable– Harus menggunakan sensor selamaeksekusi– Solusi adalah sebuah tree atau kebijakan– Prediksi selanjutnya tidak dapat diketahuidengan pastiContoh : Pemain skate baru di suatu area�Sliding problem�Pemain skate lainnya yang disekitarnyaExploration Problem• Unknown state space–Agen harus menemukan & mempelajari“peta” dari lingkungan untuk digunakansebagai pemecah masalah.Contoh : Labirin
3/12/2018
7
Problem & Solution• Problem, adalah :kumpulan informasi yang digunakanagent untuk menentukan apa yang harus dilakukannya (bertindak)• Elemen dasar dari problem definition:–State (Keadaan)–Action (Tindakan)Formulate Problem• An Initial State : Kondisi awal• A Set of Actions Kumpulan dari kemungkinan-kemungkinan tindakan yang dapat dilakukan oleh agent– Operator : digunakan untuk menunjukkan suatutindakan, dengan kondisi keadaan yangan bagaimanatindakan akan tercapai, bila melakukan suatu tindakanpada suatu keadaan khusus• A Goal Test Apakah goal/tujuan akhir tercapai?• A Path CostJumlah dari biaya2 individual tiap tindakan selamaperjalanan menuju tercapainya tujuan akhir
3/12/2018
8
MengukurPerformance Problem-SolvingAda 3 cara mengukur performance problem solving :• Apakah ditemukan suatu solusi akhir ?• Apakah solusi yang diberikan adalah solusi yang terbaik (low path cost)?• Bagaimana hubungan search cost terhadapwaktu dan memory yang diperlukan untukmenemukan solusi ?Total Cost = Search Cost + Path CostContoh ProblemToy problems• Singkat dan deskripsi yang tepat.• Contoh : – 8-puzzle– 8-queens problem– Cryptarithmetic– Vacuum world– Missionaries & cannibals– Simple route finding– Towers of Hanoi– Water jug problem
3/12/2018
9
Contoh ProblemReal-world problems• Lebih sulit• Contoh : – Route finding– Touring & traveling salesperson problems– VLSI layout– Robot navigation– Process or assembly planningState Space Implisit & Eksplisit• State space dapat direpresentasikan secaraeksplisit dengan suatu grafik.(Tidak mudah untuk memodelkan state space dari suatu problem)s kaki ssska kakaki kiki
3/12/2018
10
State Space Implisit & Eksplisit• State space dapat direpresentasikan secaraImplisit dan dikembangkan ketika dibutuhkan. Sehingga Agent harus mengetahui :– Initial state– Operator kiri kanan2 8 31 6 47 52 8 31 6 47 5 2 8 31 6 47 5 2 8 31 6 47 52 8 31 6 47 5 2 8 316 47 5 2 8 31 6 47 5 2 8 31 6 47 5atasatas kiri atas bawah kananSearch Problem• S : Himpunan dari states • s0 : Initial state • A : Operator (S→S)• G : Goal states (G ⊆S )
3/12/2018
11
Contoh : Turis di Romania• Liburan ke Romania, khususnya : Arad. Penerbangan dilakukan besok dari Bucharest.FormulateProblem Turis di Romania• An Initial State : Dari Arad• Operator (atau succesor function):Contoh : Arad � Zerind, Arad � Sibiu, dll.• A Goal Test : Berada di Bucharest• A Path Cost : Penjumlahan jarak, jumlah operator yang dieksekusi
3/12/2018
12
Contoh : The vacuum world• The world hanya mempunyai 2 lokasi.• Setiap lokasi, dapat mengandung sampahatau tidak.• Agent bisa berada disuatu lokasi /dilokasiyang lain.• Ada 8 kemungkinan world states.• Ada 3 kemungkinan actions: kiri (ki) , kanan (ka), sedot (s).• Goal: membersihkan semua yang kotorContoh : The vacuum world• State? Satu dari 8 keadaan (state)• Operator? Ke kiri, kanan, sedot• Goal Test? Tidak ada sampah pada daerah kotak• Path Cost? 1 Path cost = jumlah langkah dalam paths kaki ssska kakaki kiki
3/12/2018
13
Contoh : 8-puzzle• State? Lokasi 8 buah angka dalam matriks 3x3.• Operator? Geser yang kosong ke kiri, kanan, atas, bawah.• Goal Test? Apakah state sesuai dengan goal state ?• Path Cost? 1 per move.Intial State Goal StateContoh: Criptharithmatic• State ? Criptharithmatic puzzle dg beberapa huruf digantidengan digit (angka).• Operator ? Ganti semua karakter (huruf) yang ada dengandigit (angka) yang belum muncul dlm puzzle.• Goal Test ? Puzzle hanya berisi angka-angka dan mewakilipenjumlahan yang benar.• Path Cost ? 0 (nol),seluruh solusi persamaan harusmemenuhi(valid).
3/12/2018
14
Contoh : Misionaris & Kanibal• Ada 3 misionaris dan 3 Kanibal, yang berharapakan menyebrangi suatu sungai.• Mereka hanya mempunyai sebuah perahu, yang hanya muat untuk dua orang saja.• Kondisi tidak akan aman jika jumlah kanibal lebihbanyak daripada jumlah misionaris.Contoh : Misionaris & Kanibal• State ? Konfigurasi misionaris, kanibal dan perahu (di satu sisi)• Operator ? Pindahkan perahu• Goal Test ? Apakah semua misionaris dan kanibal sudah berada disisi sebelah kanan?• Path Cost ? 1 pergerakan=1 costIntial State Goal State= Misionaris = Kanibal
3/12/2018
15
Mencari solusiMelalui Search Tree• Setelah merumuskan masalah � cari solusinya menggunakan sebuahsearch algorithm.• Search tree merepresentasikan state space.• Search tree terdiri dari kumpulan node : struktur data yang merepresentasikansuatu state pada suatu path, dan memilikiparent, children, depth, dan path cost.Mencari solusiMelalui Search Tree• Root node (Initial Node) dari search treemerepresentasikan initial state.• Children node adalahmerepresentasikan state pengganti dari suatu node (hasil ekspansi) .• Kumpulan semua node yang belum diekspansi disebutfringe (pinggir) dari suatusearch tree. …………InitialNodeChildrennodeAction
Goal node
3/12/2018
16
Mencari solusiMelalui Search Tree• Jalur dari suatu search tree merepresentasikanserangkaian tindakanyang merupakan solusiyang dimulai dari initial state dan berakhir di goal state. …………InitialNodeChildrennodeActionGoal nodeContohPenelusuran Search Tree• Mulai dari root node (Arad) sebagai currentnode.
3/12/2018
17
ContohPenelusuran Search Tree• Mulai dari root node (Arad) sebagai currentnode.• Lakukan node expansion terhadapnya.ContohPenelusuran Search Tree• Mulai dari root node (Arad) sebagai currentnode.• Lakukan node expansion terhadapnya.• Pilih salah satu node yang di-expand sebagaicurrent node yang baru. Ulangi langkahsebelumnya.
3/12/2018
18
Strategi pencarian(Search Strategy)• Terdapat berbagai jenis strategiuntuk melakukan search.• Semua strategi ini berbeda dalam satu hal : urutan dari node expansion.Kelompok Strategi Pencarian• Uninformed Search (Blind Search)–Hanya menggunakan informasi yang ada pada problem definition.–Tidak ada informasi tentang banyaknyalangkah atau path cost dari keadaansekarang (current state) sampai goal.• Informed Search (Heuristic Search)Mengeksploitasi informasi.
3/12/2018
19
Uninformed Search(Blind Search)Breadth-first searchUniform-cost searchDepth-first searchDepth-limited searchIterative deepening searchInformed Search(Heuristic Search)Best-first searchGreedy best-first searchA* search
3/12/2018
20
Breadth-First Search (BFS)• Strategi ini node utama diekspansi, selanjutnya node hasil ekspansi(node_eks) diekspansi lagi danseterusnya.• Implementasi: fringe adalah sebuahqueue, data struktur FIFO (First In First Out)Breadth-First Search (BFS)AB CD E F G
3/12/2018
21
Breadth-First Search (BFS)Breadth-First Search (BFS)• Turis di RomaniaAradZerind Sibiu TimisoaraArad Oradea Fagaras Rimnicu VilceaArad Oradea Arad Lugoj
3/12/2018
22Depth-First Search (DFS)• Depth-first search selalu melakukan ekspansisalah satu node pada level terdalam dalam pohonpencarian, jika gagal maka akan kembali ke atas, dan melakukan ekspansi pencarian pada/ melaluinode yang lain, dst.• Implementasi: fringe adalah sebuah stack, data struktur LIFO (Last In First Out)• Depth-first search sangat cocokdiimplementasikan secara rekursif.
3/12/2018
23
AB CD E F GH I J K L MDepth-First Search (DFS)Depth-First Search (DFS)• Turis di Romania AradZerind Sibiu TimisoaraArad OradeaZerind Sibiu Timisoara
3/12/2018
24
Uniform-Cost Search• (Dijkstra, 1959)• Merupakan modifikasi dari Breadth-First Search dengan tambahan melibatkanbiaya terendah dari node_eks• Implementasi: fringe adalah sebuah priority queue di mana node disortirberdasarkan path cost function g(n).Uniform-Cost Search• Contoh :S
0
1
A
5
B
15
CS G
A
B
C
5
1
15
10
5
5
G
11
G
10
3/12/2018
25
Uniform-Cost Search• Turis di RomaniaAradArad Oradea75 71 Arad Lugoj118 111140Zerind Sibiu Timisoara75 11875 140 118150 146 236 229Uniform-cost search75118140g=140 g=118 g=75g=0
3/12/2018
26
Uniform-cost search75118140g=140 g=118 g=757575 71g=150 g=146g=0
Depth-Limited Search• Merupakan modifikasi dari Depth-First Search untuk menghindari terjerusnya kelubang perangkap yang terlalu dalam, dengan cara memotong maksimum darikedalaman path.• Contoh :Maksimum path dalam peta ada 13, jikapencarian lebih dari 13, berarti salah danpencarian langsung dihentikan,dicarimelalui node lain.
3/12/2018
27
Iterative Deepening Search• Merupakan strategi pencariandengan memilih batas limit kedalaman melalui percobaanseluruh kemungkinan batas limit (dari kedalaman 0 sampai n).Limit = 1 Iterative Deepening Search(L= 0,1,2)Limit = 2 AB CAB CD E F GLimit = 0 A
3/12/2018
28
Iterative Deepening Search(L= 3)AB CD E F GH I J K L M N OLimit = 3
Iterative Deepening SearchDepth=0• Turis di RomaniaArad
3/12/2018
29
Iterative Deepening Search: depth=1• Turis di RomaniaAradZerind Sibiu TimisoaraIterative Deepening Search: depth=2• Turis di RomaniaAradZerind Sibiu TimisoaraArad Oradea Arad Oradea Fagaras RimnicuVilcea Arad Lugoj
3/12/2018
30
Bidirectional Search• Ide metoda ini adalah, pencarian secara simultanbersamaan dari initial state maju (forward), sementara dari goal mundur (backward), danberhenti pada saat keduanya bertemu.GoalStart GoalStartBidirectional SearchInitialState FinalState
3/12/2018
31
Bidirectional SearchStrategi Pencariandievaluasi berdasarkan• Completeness : Apakah strategi menjamin akan menemukan solusi(minimal satu) ? • Time complexity: Berapa lama waktu yang dibutuhkan untukmenemukan solusi ?• Space complexity:Berapa memory yang dibutuhkan untuk membentukpencarian (maksimal ukuran node list)?Time & space complexity diukur berdasarkan :
3/12/2018
32
Strategi pencariandievaluasi berdasarkanTime & space complexity diukur berdasarkan :– b - branching factor dari search tree– d - depth (kedalaman) dari solusi optimal– m - kedalaman maksimum dari search tree (bisa infinite!)• Optimality:Apakah strategi menghasilkan kualitas solusitertinggi (minimum cost), jika dibandingkandengan solusi-solusi lain? Breadth-first search• Complete: Ya (jika b terbatas)• Optimal : Ya (jika cost = 1 per langkah)• Time : 1 + b + b2 + b3 + b4 + … + bd = bd• Space : bd (Setiap node disimpan di memory)b : Branching factord : Kedalaman dari solusim: Kedalaman Maximum
3/12/2018
33
b d Simpul Waktu Memory10 6 106 1 detik 100 MB10 8 108 100 detik 10 GB10 12 1012 11,57 hari 100 TB10 14 1014 3,17 tahun 10.000 TBKompleksitas BFS• Asumsi : 1 simpul = 100 bytes dankecepatan komputer = 106 simpul/detik.Depth-first search• Complete: Tidak , gagal jika state-space takterbatas (kondisi berulang), tanpabatasan kedalaman.• Optimal : Tidak• Time : bm (Masalah jika m > d)• Space : b.m (kedalaman yang linier)b : Branching factorm: Kedalaman Maximum
3/12/2018
34
Uniform Cost Search• Complete: Ya (jika b terbatas)• Optimal : Ya• Time : bd• Space : bdb : Branching factorm: Kedalaman MaximumDepth Limited Search• Complete: Ya (Jika l>d)• Optimal : Tidak• Time : bl• Space : b.lb : Branching factorm: Kedalaman Maximuml : Kedalaman cut-off
3/12/2018
35
Iterative Deepening Search• Complete: Ya• Optimal : Ya• Time : bd• Space : b.d• Maximum space sama dengan DFS.• Time complexity hampir sama dengan BFS.Bidirectional Search• Complete: Ya• Optimal : Ya• Time : bd/2• Space : bd/2b : Branching factord : Kedalaman dari solusi
3/12/2018
36
Perbandingan Strategi PencarianCriterion Breadth- Uniform Depth- Depth- Iterative Bidirectionalfirst cost first limited deepening (if applicable)Time bd bd bm bl bd b(d/2)Space bd bd bm bl bd b(d/2)Optimal? Ya Ya Tidak Tidak Ya YaComplete? Ya Ya Tidak Ya Ya Yajika l≥db : Branching factord : Kedalaman dari solusim: Kedalaman Maximuml : Kedalaman cut-offMenghindari Keadaan yang berulang• Masalah dalam proses Uninformed-Search :– Kemungkinan ada waktu terbuang karena“pengembangan” cabang.– Kemungkinan proses yang berulang
3/12/2018
37
3 Cara Menghindari Keadaan Berulang• Jangan kembali ke keadaan yang baru dilewati (dengan membuat fungsi/operator pengembang yang dapat menolak pada saat terbentuknya keadaan yang sama dengan keadaan parent).• Jangan membuat cabang dengan lingkaran didalamnya (dengan membuat fungsi/operator pengembang yang dapat menolak pada saat terbentuknya keadaan yang sama dengan ancestor).• Jangan membentuk keadaan yang pernah dibentuk sebelumnya (diperlukan memory yang dapat menyimpan setiap keadaan yang pernah dihasilkan).Constraint Satisfaction Search• Constaint Satisfaction Problem (CSP) :Suatu masalah khusus yang adanya beberapatambahan struktur diluar kebutuhan dasar darimasalah umum.• Keadaan dalam CSP didefinisikan oleh :sederetan nilai variabel dan goal test ditetapkandengan suatu batasan (constraint) yang harusdipatuhi oleh nilai variabel tersebut.
3/12/2018
38
Constraint Satisfaction Search• Jenis Batasan :– UNARY CONSTRAINT (Menyangkut 1 variabel)– BINARY CONSTRAINT (Menghubungkan 2 variabel)– HIGHER ORDER CONSTRAINT (Meliputi >=3 variabel)• Setiap variabel Vi dalam CSP mempunyai “Domain” Di, yang merupakan sekumpulan nilai yang dapat dipergunakan oleh variabel tersebut. • “Domain” dapat berupa DISKRIT atau KONTINYU.• Contoh : – Domain Kontinyu : Mendesain mobil berat– Domain Diskrit : Perakitan komponenBacktracking Search & Forward Checking• Backtracking SearchSuatu algoritma (perbaikan)yang menambahkansuatu test, sebelum melaksanakan langkahselanjutnya, yaitu test apakah ada batasan yang telah dilanggar oleh variabel yang telah disetujuisampai titik tersebut.• Forward CheckingSuatu algoritma yang melihat kedepan untukmenghindari kemungkinan tidak terpecahkan/ terselesaikannya masalah.
3/12/2018
39
Best-first Search• Best-First Search :suatu metoda dalam strategi pemecahanmasalah dengan menggunakan fungsievaluasi (evaluation function), dimananode diurutkan, sehingga hasil evaluasiterbaik (minimum cost nodes) akandikembangkan lebih dahulu.• Strategi untuk meminimumkan estimasibiaya untuk mencapai goal. Best-first Search• Kunci keberhasilan best-first search terletak di heuristic function.• Heuristic function h(n) adalah :fungsi yang menyatakan estimasi/ perkiraan cost dari n ke goal state.
3/12/2018
40
Turis di Romania• Sebuah heuristic function untuk agent turis Rumania :hSLD(n) = jarak straight-line distance dari n ke Bucharest.Turis di Romania
374
329
253
3/12/2018
41
Greedy Search• Adalah strategi BFS yang menggunakan f(n)=h(n) untukmenentukan node berikutnya yang akan dikembangkan (expand)• Greedy best-first search selalumemilih node yang kelihatannyapaling dekat ke goal (yang memilikih(n) paling kecil)Greedy SearchArad366Zerind374 Sibiu253 Timisoara329Arad366 Oradea380 Fagaras178 Rimnicu Vilcea193Sibiu253 Bucharest0
3/12/2018
42
ContohGreedy Best-First SearchSolusi yang diberikan tidak optimalSolusi yang OptimalGreedy Search• Tidak Complete• Tidak Optimal 2 21 2Ih=5Ah=3Ch=3 Bh=4Dh=1GgoalGgoalEh=21 13Greedy search akan mendapatkangoal disebelah kiri (solution cost : 7).Solusi optimal solution adalahjalur dengan goal yang disebelahkanan (solution cost : 5).Greedy search memilih yang terbaik, yang bisa saja yang terbaik secara lokal saja.
3/12/2018
43
A* Search• Metode search yang efisien dan optimal.• Idenya : menghindari node yang berada di path yang “mahal”• Kombinasi antara greedy search dan uniform-cost search.• Fungsi evaluasi : f(n) = g(n) + h(n)– g(n) = biaya perjalanan (path cost ) ke node n. – h(n) = biaya estimasi (estimated path cost) dari node n ke goal. – f(n) = Solusi biaya estimasi termurah (estimated total cost of path) node n ke goalA* Search Arad366=366+0Rimnicu Vilcea607=414+193 Craiova615=455+160 Bucharest418=418+097 138 101Sibiu591=338+253 Bucharest450=450+099 211 Craiova526=366+160 Pitesti415=317+98 Sibiu553=300+2538097146Arad646=280+366 Oradea671=291+380 Fagaras417=239+178 Rimnicu Vilcea413=220+193140 151 99 80Zerind449=75+374 Sibiu393=140+253 Timisoara447=118+32975 140 118
3/12/2018
44
A* search example3/12/2018RMJ VeCoS ITU 87A* search example3/12/2018RMJ VeCoS ITU 88
3/12/2018
45
A* search example3/12/2018RMJ VeCoS ITU 89A* search example3/12/2018RMJ VeCoS ITU 90
3/12/2018
46
A* search example3/12/2018RMJ VeCoS ITU 91A* search example3/12/2018RMJ VeCoS ITU 92
3/12/2018
47
Sifat A*• Peta Romania memperlihatkan contour padaf=380, f=400, dan f=420 (Kondisi awal Arad)IDA* (Iterative Deepening A*) Search• Kombinasi A* dan iterative deepening• Digunakan untuk mengurangi jumlahmemory yang dipakai.• Iterasi yang digunakan dengan Depth First Search yang dimodifikasi denganmenggunakan f-cost limit. • Kelemahan IDA* :Setiap contour naik satu state, waktuproses akan lebih lama
3/12/2018
48
SMA*(Simplified Memory Bounded A*)Search• IDA* memiliki jumlah memory yang kecil, tetapi tidak dapat menyimpan“sejarah” pencarian, sehingga adakemungkinan proses pencarian yang terulang. • SMA* menggunakan semua memory yang tersedia untuk menanganipencarian. Sifat SMA*• Tidak tergantung pada memory yang tersedia.• SMA* menghindari pengulangan bagian sejauhmemory mampu menampung.• SMA* akan selesai jika memory yang tersedia cukupuntuk menyimpan jalan solusi yang terdangkal.• SMA* akan optimal, jika memory yang tersedia cukupuntuk jalan solusi optimal yang terdangkal, jika tidakmaka akan dikembalikan solusi yang terbaik yang dapat dicapai dengan memory yang tersedia.• Bila memory cukup, memungkinkan untuk seluruhpencarian tree, maka pencarian tersebut optimal danefesien.