Informed search Greedy Search A* Search IDA* Search RBFS Search SMA* Search
Repeated State and Cycle Do not return to the state you just came from. Have the
expand function (or the operator set) refuse to generate any successor that is the same state as the node's parent. Do not create paths with cycles in them. Have the expand function (or the operator set) refuse to generate any successor of a node that is the same as any of the node's ancestors. Do not generate any state that was ever generated before. This requires every state that is generated to be kept in memory, resulting in a space complexity of O(bd), potentially. It is better to think of this as O(s), where s is the number of states in the entire state space.
Spanning Search Tree state A A B B C C C D D E F
next B C D E C D F C E G G
cost 4 1 3 8 0 2 6 2 4 2 8
A C
B
D
E
G
E
D
F
G
Tujuan instruksional Mahasiswa dapat merancang dan mengkodekan algoritma pencarian serta mengenal kekuatan dan kelemahan masing masing algoritma:
Greedy search A* search IDA* search RBFS search SMA * search
Uniform Cost Search 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 g(SUCCESSOR(n)) > g(n) 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).
Uniform Cost Search
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)
It’s not easy being blind Algoritma Blind search bisa menemukan jawaban, namun Seringkali algoritma ini tidak efisien dalam pencariannya
Anybody see my key ??
Informed search Untuk mengefisienkan pencarian, dibutuhkan tambahan informasi yang spesifik terhadap permasalahan yang dihadapi Pencarian seperti inilah yang kita sebut Informed search
Heuristik Heuristik = “rule of thumb” Heuristic are criteria, methods , or principle for
deciding among several course of action promises to be the most effective in order to reach some goal Fungsi heuristik h(n) adalah “perkiraan” biaya termurah dari node n ke node tujuan
Contoh heuristik (straight line distance = hsld)
Contoh heuristik(2)
Heuristik ? ? ?
Jumlah nomor yang salah tempat
Contoh heuristik(3)
Heuristik ? ? ?
Manhattan distance
More on heuristic Heuristic berasal dari asal kata heuriskein yang artinya
menemukan. Buatlah heuristic sedemikian sehingga : h(n) pada kondisi goal adalah 0 Fungsi heuristic melambangkan cost yang akan
dikeluarkan agent jika memilih node tertentu Heuristic memperbaiki proses pencarian solusi walaupun tidak harus sampai mengatasi kasus terburuk (worst case scenario)
Best First Search
Greedy Best First Search Berusaha meminimalisasi perkiraan biaya untuk
mencapai goal dengan meng-expand node yang dinilai paling dekat dengan goal. Fungsi yang digunakan untuk menilai kedekatan node dengan goal adalah fungsi heuristic, biasanya dinotasikan dengan huruf h
h(n) = estimated cost of the cheapest path from the state at node n to a goal state
Greedy Search
Greedy search (construct the h(n))
S
Greedy Search A
h(S ): 1 1 B C
Fringe : S
D D
E
E
E
F
F
G
G
F
G
S
Greedy Search A
h(A ): 1 0.4 h(D) : 8.9 B C
Fringe : DA
D D
E
E
E
F
F
G
G
F
G
S
Greedy Search A
h(A ): 1 0.4 h(E) : 6.9 B C
Fringe : EA
D D
E
E
E
F
F
G
G
F
G
S
Greedy Search A
h(A ): 1 0.4 h(F) : 3.0 B C
Fringe : FA
D D
E
E
E
F
F
G
G
F
G
S
Greedy Search A
h(A ): 1 0.4 h(G) : 0 B
D D
E
Total cost : 13 C
Fringe : GA
E
E
F
F
G
G
F
G
Greedy search property Complete ?
No, can get stuck in loops Complete if repeated-state checking is performed Time ?
O(bm), but good heuristic can give dramatic improvement Space ?
O(bm) – save all nodes in memory Optimal ?
No, Why ?
Try This Greedy search: A-B-E-G-H = 99 Not Optimal Better solution: A-B-C-F-H = 39
A* Algorithm (Hart Nilsson & Rafael 1968)
Greedy Search minimalisir estimasi search cost Uniform cost Search minimalisir cost sampai saat
ini. Algoritma A* menggabungkan keduanya Dengan fungsi f(n)
f(n) = h(n) + g(n) g(n) = cost so far to reach n from start state h(n) = estimated cost to goal state from n f(n) = estimated total cost of path through n to goal
Try This
Try This
Back to: Romania
A* Search Example: Romania
A* Search Example: Romania
A* Search Example: Romania
A* Search Example: Romania
A* Search Example: Romania
A* Search Example: Romania
A* algorithm property Complete ?? Optimal ?? Time ?? Space ??
A* property (Optimality and Completeness) Algoritma A* bersifat admissible. Ini berarti apabila solusi ada, solusi yang ditemukan pertama adalah solusi yang optimal. A* bersifat admissible bila memenuhi syarat syarat berikut : Di dalam graph state space
Setiap node memiliki successor yang terbatas Setiap arc pada graph memiliki biaya yang > dari 0 Heuristik: untuk setiap node n, h(n) < h*(n)
A* property (Optimality) A* optimal untuk heuristik tertentu – dari semua algoritma
search yang optimal yang mencari dari root ke node tujuan, dapat dibuktikan bahwa tidak ada algoritma lain yang membuka simpul node yang paling sedikit dan menemukan solusi Namun, jumlah node yang disimpan masih bersifat exponential pada kasus terburuk Sayangnya perkiraan saja tidak cukup bagi algoritma A* untuk tidak membuka simpul secara exponential, sebagai tambahan A* harus menyimpan semua node pada memory A* jauh lebih efisien daripada pencarian tanpa informasi
Contours (Monotonicity)
More on heuristic (2) Heuristic yang baik adalah heuristic yang tidak
overestimate Suatu heuristik dikatakan konsisten bila : h(n) <= cost(n,n’) + h(n’)
More on heuristic (3)
More on heuristic (4) heuristik untuk kasus diatas tidak konsisten, karena
h(n)= 4 sedangkan h(n’) = cost(n,n’) + h(n’) = 1 + 2 = 3, sehingga h(n) > h(n’). hal ini membuat nilai f mengecil dari node n ke node
n’ Heuristik yang nilai f nya selalu membesar disebut
heuristik yang monoton
Bukti admissibility A* (Optimal) Bila G adalah Goal optimal G2 adalah Goal suboptimal C* adalah Biaya asli menuju G Bila G2 dipilih berarti f(n) >= f(G2)
Karena G2 adalah goal f(G2) = g(G2)
Maka terjadilah C* >= g(G2)
Kontradiksi !!
Bukti Completeness A* A * dikatakan complete dan optimal dengan
mengasumsikan sebuah heuristic yang admissible dan konsisten (atau menggunakan pathmax untuk mempertahankan konsistensi, i.e. Contours) Baca e-book
Analisis performansi A* |h(n)-h*(n)| <= O (log h*(n)) Queue besar Baca e-book
Dominansi h2 dikatakan memiliki dominansi atas h1 jika h2(n) > = h1(n)
untuk setiap n A * akan mengekspansi lebih sedikit node dengan h2 secara rata rata dibandingkan dengan h1 Bukti : Untuk setiap node dimana f(n) < C* akan diekspansi, maka n akan diekspansi apabila: h(n) < f* - g(n) karena h2(n) >= h1(n) setiap node yang diekspansi h2 akan diekspansi oleh h1. Bacalah di e-book bagaimana menggunakan heuristik lebih dari satu fungsi
Perbaikan algoritma A* Algoritma A* menggunakan banyak sekali memory
sehingga kerap kali habis tempat untuk pencarian Ada beberapa varian dari algoritma A* yang dapat digunakan untuk mensiasati kekurangan memory tersebut diantaranya adalah : IDA * RBFS
SMA *
Itterative Deepening A* search Idenya serupa dengan DFID search hanya saja
yang menjadi batas adalah nilai f per node. Mulailah dengan flimit = h(start) Potonglah (prune) semua node dimana f(node ) > f limit flimit berikutnya adalah nilai minimum node yang dipotong
IDA*
IDA*
IDA*
IDA* property Complete and optimal time complexity : DFS Space complexity : DFS (bm) Setiap iterasi pada IDA* adalah iterasi DFS sehingga
space yang dibutuhkan linear dan tidak membutuhkan priority queue
IDA* weakness Apabila nilai f sangat bervariasi, bahkan bila pada
kasus terburuk setiap node memiliki nilai f yang berbeda maka pada tiap iterasi IDA* hanya akan mengekspansi satu buah node. IDA* tidak cocok untuk graf dengan banyak siklus. NB: Semua algoritma berbasis DFS tidak cocok untuk graf dengan banyak siklus
IDA*
Recursive Breadth First Search RBFS menggunakan kebutuhan memory yang linear Cara kerjanya meniru algoritma best first search RBFS menyimpan nilai f terbaik dari jalur alternatif
yang tersedia dari pendahulu node yang sekarang Bila node yang sekarang melebihi limit nilai f maka jalur alternatif lainnya diperiksa. RBFS mengingat nilai f daun terbaik di sub pohon yang sudah dilalui
Simplified Memory bounded A* Algoritma ini menjalankan best first search selama
memory masih tersedia, apabila memory penuh maka node dengan nilai terburuk di buang, namun nilainya disimpan pada node atasnya. Kalau ada ruang memori yang mencukupi untuk semua node pada tree dalam jalur pencarian, maka pencarian akan menjadi optimal.
SMA* Illustrated
Local Search Algorithm • Kadang kadang kita tidak membutuhkan path pencarian, kita hanya perlu hasilnya saja. Bila demikian kita bisa menggunakan algoritma penyelesaian lain yaitu local search algorithm • Local search algorithm tidak menyimpan state dalam bentuk tree tapi hanya menyimpan satu state dan ‘memperbaiki’ state tersebut sampai mencapai sebuah goal.
Example problem
Local Search Algorithm (2) •
•
Beroperasi dengan menggunakan satu state aktif dan biasanya bergerak hanya kepada state yang bersebelahan dengan state tersebut Keuntungan local search algorithm 1. 2.
Menggunakan memory yang sangat sedikit (hanya 1 state) Kadang dapat menemukan jawaban yang baik di state space yang besar dan atau tak terbatas
Local Search State Space
Local Search algorithm (3) Beberapa local search algorithm: Hill Climbing / Gradient descent Simulated Annealing
Hill Climbing algorithm Layaknya seorang pendaki gunung yang mencari
tanah yang ketinggian lebih tinggi dari yang ditempatinya sekarang, hill climbing algorithm mencari state yang lebih baik dari state yang ada sekarang dan “membuang sisanya”
Hill Climbing algorithm
“Like climbing Everest in thick fog with amnesia” Steps in hill-climbing algorithm: 1. 2. 3. 4. 5.
Create initial state Generate successors Apply heuristic evaluation function to successors Choose the best alternative (forgetting all the rest) Repeat to step 2 until no more improvement could be made
Hill Climbing example ~ Good One
Hill Climbing example ~ Good One
Hill Climbing example ~ Bad One
Traveling Salesman Problem (TSP) Problem:
Seorang salesman ingin mengunjungi n kota. Jarak antar kota sudah diketahui. Kita ingin mengetahui rute terpendek yang dilalui dengan syarat tiap kota hanya boleh dikunjungi tepat 1 kali. Fungsi heuristik: Rute berikutnya harus lebih pendek dari rute saat ini
8
A
B
3
4
7
5 D
6
C
TSP - Hill Climbing
Operator: menukar urutan posisi 2 kota dalam satu lintasan Fungsi heuristik: panjang lintasan
Properties of Hill-Climbing • Complete ? No, may never find an answer • Time ? May be very slow • Space ? Constant
• Optimal ? No, may not find the best answer
Hill Climbing Weakness
Hill Climbing Improvement • Random Restart Hill-climbing Conduct a series of hill-climbing from randomly generated initial states • Stochastic Hill-Climbing Chooses at random from among the uphill moves • First-choice Hill-Climbing
Simulated Annealing
Idea: Escape local maxima by allowing some “bad” moves, but gradually decrease their size and frequency
Steps: 1. Pick a move at random 2. If move will improve things, take it 3. If it will make things worse, take it with some probability •
•
4.
Take it with probability e ∆E / T ∆E is value(current state) – value(move state) T is constant Keep going, making T smaller according to some schedule
If the schedule is slow enough, this algorithm is guaranteed to find the global optimum
Simulated Annealing
Origin: Annealing in Physics
•
The process of gradually cooling a liquid until it freezes If solid materials is heated past its melting point and then cooled back into a solid state, the structural properties of the cooled solid depend on the rate of cooling. E corresponds to the total energy of atoms in the material, and T corresponds to the temperature. The schedule determines the rate at which the temperature is lowered. Individual moves in the state space correspond to random fluctuations due to thermal noise
• • •
Latihan Heuristik Sebuah rubic cube adalah sebuah kubus 3x3 dengan 6 warna, kubus
ini awalnya memiliki warna yang sama untuk setiap sisinya. Untuk memainkannya seseorang dapat mengeser rubic perbaris atau kolom sehingga warna pada tiap sisi rubic tidak sama. Tujuan dari permainan adalah membuat rubic cube memiliki warna yang sama kembali pada tiap sisinya.
Latihan Heuristik Cobalah menganalisa permasalahan rubic cube : Berapa branching factor dari permasalahan ini ?
(tuliskan juga operator yang anda gunakan, jangan lupa tangani masalah repeated state bila ada). Carilah sebuah heuristik yang dapat dipakai untuk menyelesaikan permasalahan ini. Dari semua algoritma uninformed search yang sudah anda pelajari sebutkan algoritma apa yang paling tepat digunakan untuk permasalahan ini menurut anda, sertakan pula alasan mengapa anda memilih algoritma tersebut.
Latihan A* Buatlah graf pencarian sesuai tabel disamping. Lakukan strategi pencarian dengan algoritma uniform cost, greedy search, dan A* Gambarkan perjalanan pencarian.
Latihan Local Search Selesaikanlah 8 puzzle berikut dengan menggunakan
algoritma greedy search, A* dan Hill climbing
1 3 4 2 5 7 8 6 Initial state
1 2 3 4 5 6 7 8 Goal state
