Penyelesaian Masalah dengan Pencarian
Model Problem & Pencarian Solusi
Mengkonversi situasi yang diberikan ke dalam situasi lain menggunakan sekumpulan operasi tertentu. Searching : merepresentasikan masalah ke dalam ruang keadaan. Untuk melakukan hal ini, diperlukan sedikit kemampuan rekayasa.
Masalah Jurigen Air • Terdapat dua jurigen tanpa skala ukuran. • Sebuah kran air yang bisa mengeluarkan air tanpa batas. • Bagaimana mendapatkan tepat 2 galon air di dalam jurigen 3-galon? Kran air
4-galon 3-galon
Ruang Keadaan
Keadaan bisa berupa jumlah air yang berada dalam jurigen 4-galon dan jurigen 3-galon. Keadaan = (x, y)
x = 0, 1, 2, 3, 4 y = 0, 1, 2, 3
Keadaan Awal = (0, 0) Keadaan Tujuan = (n, 2) untuk setiap nilai n berupa bilangan bulat [0, 4].
Himpunan Operator
Operator (aturan produksi) adalah langkah untuk mengubah suatu keadaan menjadi keadaan yang lain. Himpunan operator harus lengkap. Solusi mungkin tidak ditemukan jika himpunan operatornya tidak lengkap. Bagaimana mengetahui kelengkapan himpunan operator?
1
(x,y)
(4,y)
Isi penuh jurigen 4 galon
(x,3)
Isi penuh jurigen 3 galon
(x-d,y)
Buang sebagian air dari jurigen 4 galon
(x,y-d)
Buang sebagian air dari jurigen 3 galon
(0,y)
Kosongkan jurigen 4 galon
(x,0)
Kosongkan jurigen 3 galon
If x < 4 2
(x,y) If y < 3
3
(x,y) If x > 0
4
(x,y) If y > 0
5
(x,y) If x > 0
6
(x,y) If y > 0
7
(x,y)
(4,y-(4-x)) Tuangkan air dari jurigen 3 galon ke
If x+y 4 and y > 0
jurigen 4 galon sampai jurigen 4 galon penuh
8
(x,y)
(x-(3-y),3) Tuangkan air dari jurigen 4 galon ke
If x+y 3 and x > 0
jurigen 3 galon sampai jurigen 3 galon penuh
9
(x,y)
(x+y,0)
If x+y 4 and y > 0
10 (x,y)
ke jurigen 4 galon
(0,x+y)
If x+y 3 and x > 0 11 (0,2)
Tuangkan seluruh air dari jurigen 3 galon
Tuangkan seluruh air dari jurigen 4 galon ke jurigen 3 galon
(2,0)
Tuangkan 2 galon air dari jurigen 3 galon
ke jurigen 4 galon 12 (2,y)
(0,y)
Buang 2 galon air dalam jurigen 4 galon sampai habis.
Model
State : sebuah keadaan yang unik di dalam problem Aksi : operasi untuk mengubah keadaan dari satu state ke state lain Ruang Pencarian : kumpulan state-state berbeda Problem : Perbedaan antara state awal dengan state goal Solusi : menerapkan strategi searching untuk menemukan rangkaian state yang mengantarkan dari state awal ke state tujuan 8
Contoh: Romania
Liburan di Romania; tepatnya di Arad. Perjalanan menuju Bucharest Formulasikan tujuan:
Formulasikan masalah:
di Bucharest states: kota-kota actions: mengemudi antar 2 kota
Temukan solusi:
Urutan kota, contohnya: Arad, Sibiu, Fagaras, Bucharest
Contoh: Romania
Formulasi problem Sebuah masalah didefinisikan dalam 4 komponen: 1. 2.
status awal, contoh: “di Arad” atau”in (Arad)" aksi atau fungsi suksesor
S(x) = state space, himpunan dari aksi dan status yang mungkin dari status awal ke status akhir. Membentuk graf.
3.
goal test:
eksplisit, contoh x = “Bucharest“atau”in (Arad)" implisit, contoh Biaya/path cost (tambahan) contoh jumlah jarak, jumlah aksi yang dieksekusi, dll. c(x,a,y) adalah biaya per aksi, diasumsikan besarnya ≥ 0. Sebuah solusi adalah urutan aksi mulai dari status awal sampai dengan status akhir
Menentukan state space
State space merupakan abstraksi dari
penyelesaian masalah Status (abstrak) = kumpulan dari statusstatus riil Aksi (abstrak) = kombinasi komplex dari aksi-aksi riil
Contoh: "Arad Zerind" merepresentasikan sebuah himpunan kompleks dari rute, detours, tempat istirahat, dll.
Contoh: 8-puzzle
status? Lokasi dari ubin (tile) aksi? move blank left, right, up, down goal test? = is state match (given) biaya? 1 per aksi
[Note: optimal solution of n-Puzzle family is NP-hard]
Tree Search
Ide dasar:
Mensimulasikan eksplorasi state space dengan membangkitkan semua status suksesor dari status yang baru saja dieksplor
Contoh tree search
Implementasi: general tree search
Implementasi: status vs. node
Status adalah representasi dari konfigurasi fisik Simpul (node) adalah struktur data yang merupakan bagian dari pohon pencarian yang terdiri dari status, node induk (parent), aksi, biaya (path cost: g(x)), dan kedalaman (depth)
Fungsi Expand membangkitkan seluruh node suksesor, berdasarkan status-status yang diberikan oleh fungsi SuccessorFn
Strategi-strategi Pencarian
Strategi pencarian didefinisikan berdasarkan penentuan urutan pemrosesan node Strategi dievaluasi menurut dimensi-dimensi berikut:
completeness: apakah pasti menemukan solusi jika memang ada? Kompleksitas waktu: jumlah nodes yang dibangkitkan Kompleksitas memori: jumlah maksimum nodes di memori optimal: apakah selalu menemukan solusi dengan biaya terendah?
Kompleksitas waktu dan memori diukur dalam terminologi berikut:
b: faktor pencabangan maksimal dari pohon pencarian d: kedalaman dari solusi berbiaya terendah m: kedalaman maksimum dari ruang pencarian (mungkin ∞)
Strategi2 Pencarian BLIND SEARCH/Uninformed
Strategi pencarian Uninformed hanya menggunakan informasi yang tersedia pada definisi masalah Breadth-first search Uniform-cost search Depth-first search Depth-limited search Iterative deepening search
Breadth-first search (BFS)
Memprioritaskan node se-level Implementasi:
fringe berupa antrian (queue): suksesor2 baru ditempatkan di belakang
(a)
Breadth-first search
(b)
(c)
(d)
Properti BFS
Complete Ya (jika b terbatas) Waktu? 1+b+b2+b3+… +bd + b(bd-1) = O(bd+1) memori? O(bd+1) (menyimpan semua node di memory) Optimal? Ya (jika biaya=1 per langkah)
Perbaikan: Uniform Cost Search (UCS)
Prioritas node yang dieksplorasi adalah node yang memberikan path cost terendah Implementasi:
fringe = antrian berdasar biaya
Ekivalen dengan BFS jika biaya per langkah sama
Depth-first search
Mengeksplor node yang levelnya lebih bawah Implementasi:
fringe = stack, menempatkan suksesor di depan
Depth-first search
Properties of depth-first search
Complete? Tidak: gagal pada ruang pencarian dengan kedalaman yang tinggi Waktu? O(bm) : sangat jelek jika m jauh lebih besar dari d Memori? O(bm) Optimal? Tidak, Jika ada lebih dari 1 solusi pada level yang beda, solusi mungkin
Pencarian Heuristik
INFORMED SEARCH/HEURISTIC SEARCH
Ide:
-
menggunakan fungsi evaluasi f(n) untuk membangkitkan node suksesor mengurutkan node suksesor berdasarkan harga, hasil dari f(n)
Kasus khusus: greedy BFS * A search 27
Greedy BFS
Mempertimbangkan harga perkiraan, bukan harga sebenarnya Fungsi Evaluasi f(n) = h(n) = estimasi biaya dari node n ke tujuan contoh hSLD(n) = straight-line distance dari node n ke ke kota B Greedy BFS memprioritaskan node yang terlihat lebih dekat ke tujuan 28
Fungsi Heuristik
Fungsi h(N), memperkirakan biaya dari jalur termurah dari node n ke node tujuan. contoh: 8-puzzle 5 8 4 2 1 7 3 6 N
1 2 3 4 5 6 7 8 goal
h(N) = jumlah ubin salah alamat =6 h(N) = jumlah jarak setiap posisi ubin ke posisi akhirnya =2+3+0+1+3+0+3+1 = 13 29
Romania (step cost dalam km) Jarak langsung ke B A (366) B (0) C (160) D (242) E (161) F (176) G (77) H (151) I (226) L (244) M (241) N (234) O (380) P (100) R (193) S (253) T (329) U (80) V (199) Z (374)
30
Greedy BFS (contoh)
31
Properti Greedy BFS
Complete? Tidak – mungkin terjadi loop contoh: I N I N Waktu? O(bm) Memori? O(bm) – menyimpan semua nodes di memori Optimal? Tidak (krn yg dgunakan hanya harga perkiraan)
32
A* search
Menggabungkan uniform cost search dengan
greedy search
Ide: menghindari jalur dengan biaya yang tinggi Fungsi evaluasi f(n) = g(n) + h(n) g(n) = biaya sesungguhnya dari node awal ke node n h(n) = perkiraan biaya dari node n ke tujuan f(n) = perkiraan biaya total dari node asal ke node tujuan dengan melewati n 33
A* search (contoh)
34
Properti A*
Complete? Ya (kecuali jika terdapat node dengan f ≤ f(G) ) Waktu? Exponential memori? Menyimpan semua node di memori Optimal? ya
35
Kasus Khusus Searching
Tempatkan n ratu pada papan n x n kotak, setiap ratu menempati sebuah kotak, tidak ada 2 atau lebih ratu pada kolom, baris, dan diagonal yang sama
36
Hill-climbing search
37
Hill-climbing search
Problem: tergantung dari status awal, bisa terjebak pada maksimum lokal maxima
38
Hill-climbing search: Persoalan 8Ratu
h = jumlah pasangan ratu yang berada pada baris /kolom/ diagonal yang sama h = 17 utnuk status di atas
39
Hill-climbing search: 6-Ratu
Sebuah minimum lokal dengan h = 1
40
Simulated annealing (SA) search
Idea: menghindari maksimum lokal dengan membolehkan status yang lebih jelek dari status sebelumnya, tetapi secara gradual mengurangi frekuensinya
41
Constraint Satisfaction Problems
Constraint satisfaction problems (CSP)
Pencarian standar:
state adalah sebuah "black box“ – struktur data mendukung fungsi suksesor, fungsi heuristik, dan goal test
CSP:
state didefinisikan dalam bentuk variabel Xi dengan nilai dari domain Di goal test adalah himpunan konstrain yang menspesikasikan kombinasi nilai variabel yang dibolehkan
Contoh: Map-Coloring
Variabel WA, NT, Q, NSW, V, SA, T Domain Di = {merah, hijau, biru} Konstrain: daerah-daerah yang bertetangga harus mempunyai warna yang berbeda Contoh: WA ≠ NT atau (WA,NT) in {(merah,hijau),(merah,biru),(hijau,merah), (hijau,biru),(biru,merah),(biru,hijau)}
Constraint graph
Binary CSP: setiap konstrain berhubungan dengan 2 variabel Constraint graph: simpul adalah variabel dan busur adalah konstrain
Solusi berupa pernyataan lengkap dan konsisten, contohnya: WA = merah, NT = hijau,Q = merah,NSW = hijau,V = merah,SA = biru,T = hijau
Jenis Konstrain
Unary constraints hanya melibatkan sebuah variabel,
Binary constraints melibatkan pasangan variabel
contoh SA ≠ hijau
contoh SA ≠ WA
Higher-order constraints melibatkan 3 atau lebih variabel
contoh cryptarithmetic
Contoh: Cryptarithmetic
Variabel: F T U W
R O X1 X2 X3 Domain: {0,1,2,3,4,5,6,7,8,9} Konstrain: Alldiff (F,T,U,W,R,O)
O + O = R + 10 · X1 X1 + W + W = U + 10 · X2 X2 + T + T = O + 10 · X3 X3 = F, T ≠ 0, F ≠ 0
CSP pada dunia nyata
Persoalan penugasan
Timetabling
Contoh: siapa (dosen) mengajar kelas apa Contoh: jadwal perkuliahan
Penjadwalan transportasi Penjadwalan produksi
Formulasi Pencarian standar
Menggunakan DFS Solusi akan ditemukan pada kedalaman n untuk variabel berjumlah n Jalur/path tidak dipentingkan Pernyataan bersifat komutatif, contoh: [WA=merah maka NT=hijau] sama dengan [NT=hijau maka WA=merah] Status awal: himpunan kosong { } Fungsi suksesor: menyatakan sebuah nilai ke sebuah variabel yang tidak konflik dengan pernyataan-pernyataan yang sudah ada Gagal jika terdapat pernyataan tidak legal Goal test: Pernyataan lengkap
Backtracking search
Contoh backtracking
Game Playing Search
Games vs. search problems
"Unpredictable" opponent specifying a move for every possible opponent reply
Time limits unlikely to find goal, must approximate
Game tree (2-player, deterministic, turns)
Minimax
Perfect play for deterministic games
Idea: choose move to position with highest minimax value = best achievable payoff against best play
E.g., 2-ply game:
Minimax algorithm
Properties of minimax
Complete? Yes (if tree is finite)
Optimal? Yes (against an optimal opponent)
Time complexity? O(bm)
Space complexity? O(bm) (depth-first exploration)
For chess, b ≈ 35, m ≈100 for "reasonable" games exact solution completely infeasible
