Search Strategy
Search Strategy Salah satu hal penting dalam menentukan keberhasilan sistem cerdas adalah kesuksesan dalam pencarian (search) Pada dasarnya ada 2 Teknik pencarian : 1. Metode Buta (Uninformed Search) Breadth-first search Depth-first search 2. Metode Terbimbing (Informed Search) Greedy best-first search Heuristic search o Generate & Test o Hill-climbing search : Simple, Steepest-Ascent o Best-first search : OR Graph, Algoritma A* o Simulated annealing search
1
Breadth-First Search
•
•
Disebut juga pencarian melebar Semua node pada level n akan dilacak terlebih dahulu sebelum melacak node-node pada level n+1 Pencarian dimulai dari node level 0, menuju level 1 dari kiri ke kanan, lalu menuju level 2 dari kiri ke kanan dst-nya, hingga ditemukan solusi/tujuan. Keuntungan : o Tidak akan menemui jalan buntu o Jika terdapat lebih dari satu solusi maka solusi dengan lintasan minimum akan dipilih sebagai solusi terbaik. Kelemahan : o Membutuhkan memori yang cukup banyak, karena harus menyimpan semua node dalam satu pohon. o Membutuhkan waktu yang cukup lama karena akan menguji n level untuk mendapatkan solusi pada level n+1
Breadth-First Search S D
A B C
E D
D
A
E
B
F
B
F
G
C
G
C
E B E
A
F C
G
F G
Move downwards, level by level, until goal is reached.
2
Breadth-First Search Algoritma Breadth-First Search 1. Buat variabel NODE_LIST dan tetapkan sebagai keadaan awal. 2. Kerjakan langakh-langkah berikut ini, sampai tujuan tercapai atau NODE_LIST dalam keadaan kosong : a.Hapus elemen pertama dari NODE_LIST, sebut dengan nama E. Jika NODE_LIST kosong, keluar. b.Pada setiap langkah yang aturannya cocok dengan E, kerjakan : i. Aplikasikan aturan tersebut untuk membentuk keadaan baru. ii. Jika keadaan awal adalah tujuan yang diharapkan, sukses dan keluar. iii. Jika tidak demikian, tambahkan keadaan awal yang baru tsb pada akhir NODE_LIST.
Pseudocode for BFS Initialize: Let Q = {S} While Q is not empty pull Q1, the first element in Q if Q1 is a goal report(success) and quit else child_nodes = expand(Q1) eliminate child_nodes which represent loops put remaining child_nodes at the back of Q end Continue 6
3
Breadth-First Search 0,0 0,3 4,0
4,0
0,0
3,0
0,0
0,3
3,3
0,3
3,0
4,2
0,2
4,0
4,2
2,0
4,3
0,0
1,3
Dst-nya
0,0
3,3
Depth-First Search
•
•
Pencarian dimulai dari node level 0, dilanjutkan ke node-node anaknya sampai selesai, baru berpindah ke node-node yang selevel hingga ditemukan solusi/tujuan. Jika proses pencarian tidak menemukan solusi pada satu lintasan maka akan dilakukan backtracking (pencarian mundur) ke node sebelumnya untuk kemudian baru berpindah ke level berikutnya (khususnya untuk node-node yang bercabang) Keuntungan : o Membutuhkan memori yang relatif kecil (bila dibanding BFS). o Hanya node yg aktif saja yang disimpan. o Pencarian solusi mungkin tidak harus memeriksa semua lintasan. o Begitu pencarian menemukan satu solusi maka pencarian selesai. Kelemahan : o Hanya akan mendapatkan 1 solusi setiap kali pencarian. o Solusi alternatif tidak menjadi perhatian
4
Depth-First Search S D
A B C
E D
D
A
E
B
F
B
F
G
C
G
C
E B E
A
F C
G
F G
Breadth-First Search
What about time complexity and space complexity ?
Misal diasumsikan ada 1 solusi pada pohon. Misal pohon pelacakan memiliki cabang yg selalu sama yaitu b dan tujuan dicapai pada level ke-d. Antrian pertama memiliki 1 state dan pada level 1 akan diekspansi sebanyak b. Pada level 2 diekspansi sebanyak b2. Pada level 3 diekspansi sebanyak b3. Untuk kedalaman hingga level d maka diperoleh deret ekspansi :
1+ b + b2 + b3 + . . . . + bd O(bd) Karena setiap lintasan tersimpan di memori maka kompleksitas ruangnya akan setara dengan kompleksitas waktu yaitu O(bd).
5
Breadth-First Search Analisis Kompleksitas Waktu If a goal node is found on depth d of the tree, all nodes up till that depth are created.
d b
G
m
Thus: O(bd)
Breadth-First Search Analisis Kompleksitas Ruang •
Largest number of nodes in QUEUE is reached on the level d of the goal node.
d b
QUEUE contains all In General: bd
G
m
and G nodes. (Thus : 4) .
6
Breadth-First Search
Secara umum, BFS cocok untuk pencarian dengan lintasan kecil.
Depth-First Search 0,0 0,3
4,0
4,0 0,0 3,0
4,3 0,0 1,3
Dst-nya
0,0 0,3 3,3 0,3 3,0 4,2 0,2 4,0 3,3 0,0 4,2 2,0
7
Depth-First Search Pseudocode for DFS Initialize: Let Q = {S} While Q is not empty pull Q1, the first element in Q if Q1 is a goal report(success) and quit else child_nodes = expand(Q1) eliminate child_nodes which represent loops put remaining child_nodes at the front of Q end Continue
Depth-First Search Analisis Kompleksitas Waktu •
In the worst case: •
the (only) goal node may be on the right-most branch,
m
b G
Time complexity = bm + bm-1 + … + 1 = bm+1 -1 b-1 Thus: O(bm)
8
Depth-First Search Analisis Kompleksitas Ruang Largest number of nodes in QUEUE is reached in bottom leftmost node. Example: m = 3, b = 3 :
•
•
... QUEUE contains all nodes. Thus: 7. In General: ((b-1) * m) + 1 Order: O(m*b)
Depth-First Search Evaluation of DFS by four criteria : -
-
Good : Since we don’t expand all nodes at a level, space complexity is modest. For branching factor b and depth m, we require bm number of nodes to be stored in memory. This is much better than bd. In some cases, DFS can be faster than BFS. However, the worse case is still O(bm).
Bad : - If you have deep search trees (or infinite – which is quite possible), DFS may end up running off to infinity and may not be able to recover.
-
Thus DFS is neither optimal or complete.
18
9
Perbandingan BFS dan DFS Criterion Time Space Optimal ? Complete ?
Breadth-first O(bd) O(bd) Yes, jika bobot tiap langkah identik Yes, jika tree berhingga
Depth-first O(bm) O(bm) No No
b – maks jumlah cabang d – level kedalaman m – kedalaman maksimum
19
Search Strategy: Informed Search
Disebut juga metode Heuristic (‘rule of thumb’, ‘hints’)
Merupakan pendekatan metode pelacakan dalam AI (Greedy) Best-first Search A* search Hill climbing
10
Search Strategy: Informed Search
Metode yang didesain untuk mempersempit area pelacakan. Berkaitan dengan pohon pelacakan (search tree), metode heuristik akan memangkas ukuran lintasan-lintasan yang tidak vital berdasarkan pengalaman atau informasi/keadaan awal. Analogi : Ketika seorang penjaga pantai mencari seseorang yang hilang di lautan, ia tidak perlu memeriksa seluruh isi lautan. Kondisi sekitar pantai, arah dan kecepatan angin dsb dapat diguna kan untuk membatasi area pelacakan.
Metode ini diharapkan akan menghemat sumber daya pelacakan.
(Greedy) Best-First Search
Menelusuri node yang terdekat dengan tujuan. Fungsi evaluasi heuristik : f(n) = h(n) f(n) : fungsi evaluasi heuristik h(n) : estimasi nilai dari node n ke node tujuan. Pada search tree, dibutuhkan 2 antrian : o OPEN, yang berisi node-node yang sudah dibangkitkan, dan sudah memiliki heuristik tetapi belum diuji. Umumnya merupakan antrian yang berisi elemen-elemen dengan nilai heuristik tinggi. o CLOSED, yang berisi node-node yang sudah diuji
11
(Greedy) Best-First Search Romania with step costs in km Problem : Posisi Anda di Arad. Tentukan lintasan untuk mencapai Bukharest menggunakan heuristik hSLD(n)=‘Straight-line Distance from n to Bukharest’
374
253 329
12
Node 1 yang diekspansi adalah Sibiu, karena terdekat dengan tujuan daripada Zerind dan Timisoara
Ekspansi node berikutnya adalah Faragas, karena terdekat dengan tujuan
13
•
Faragas menghubungkan langsung ke tujuan.
(Greedy) Best-First Search
Pada contoh tersebut, greedy best first search menggunakan heuristik hSLD(n) menemukan solusi dengan melakukan ekspansi hanya pada node yang dianggap terdekat dengan tujuan, sehingga estimasi biayanya minimum. Akan tetapi solusi tsb tidak optimum, karena menuju Bukharest via Sibiu dan Faragas ternyata 32 km lebih jauh dibanding via Rimnicu Vilcea dan Pitesti. Arad – Sibiu – Faragas – Bukharest : 450 km Arad – Sibiu – Rimnicu Vilcea – Pitesti – Bukharest : 418 km Lintasan tsb tidak dilalui karena nilai heuristik untuk Rimnicu Vilcea lebih tinggi dibanfing Faragas.
14
A* Search
Perbaikan dari metode (Greedy) best first search. Fungsi evaluasi untuk node n : f(n) = g(n) + h(n) g(n) : estimasi biaya/nilai dari node awal ke node n h(n) : estimasi biaya/nilai dari node n ke node tujuan A* search meminimalkan total biaya/nilai
5-
30
15
5-
31
5-
32
16
5-
33
5-
34
17
5-
35
Hill Climbing Search
Membangkitkan semua kemungkinan solusi dari keadaan awal. Proses pengujian berdasarkan fungsi heuristik untuk menunjukkan seberapa baik nilai estimasi yang diambil terhadap keadaan-keadaan lain yang mungkin. a) Mulai dari keadaan awal, lakukan pengujian. Jika merupakan tujuan, STOP. Jika tidak, lanjutkan dengan keadaan sekarang sebagai keadaan awal. b) Kerjakan iterasi berikut hingga ditemukan solusi atau sampai tidak ada operator baru yang bisa diaplikasikan pada keadaan sekarang : Cari operator yang belum pernah digunakan untuk mendapat operator baru Evaluasi keadaan baru tersebut : o Jika keadaan baru merupakan tujuan, keluar. o Jika bukan tujuan, tapi nilainya lebih baik dari keadaan sekarang, maka jadikan sebagai keadaan baru tsb menjadi keadaan sekarang. o Jika keadaan baru tidak lebih baik dari keadaan sekarang, lanjutkan iterasi Note : - Algoritma berhenti jika sudah mencapai nilai optimum - Tidak diijinkan melihat satupun langkah sebelumnya
18
Hill Climbing Search 8
A 3 7 D
B 4 5
6
C
Seorang salesman akan mengunjungi 4 kota. Jarak antar Kota sudah diketahui. Kita ingin mengetahui rute terpendek Dimana setiap kota hanya boleh dikunjungi tepat 1 kali. Misal jarak antar kota diketahui seperti pada gambar tsb.
Solusi – solusi yang mungkin dengan menyusun kotakota, misalnya : A – B – C – D : dengan panjang lintasan (=19) A – B – D – C : (=18) A – C – B – D : (=12) A – C – D – B : (=13) dst
38
19
Ruang keadaan berisi semua kemungkinan lintasan yang mungkin. Operator digunakan untuk menukar posisi kota-kota yang bersebelahan. Fungsi heuristik yang digunakan adalah panjang lintasan yang terjadi. Operator yang akan digunakan adalah menukar urutan posisi 2 kota dalam 1 lintasan. Bila ada n kota, dan ingin mencari kombinasi lintasan dengan menukar posisi urutan 2 kota, maka akan didapat sebanyak :
Keenam kombinasi ini akan dipakai semuanya sebagai operator, yaitu
Tukar 1,2 = menukar urutan posisi kota ke – 1 dengan kota ke – 2 Tukar 2,3 = menukar urutan posisi kota ke – 2 dengan kota ke – 3 Tukar 3,4 = menukar urutan posisi kota ke – 3 dengan kota ke – 4 Tukar 4,1 = menukar urutan posisi kota ke – 4 dengan kota ke – 1 Tukar 2,4 = menukar urutan posisi kota ke – 2 dengan kota ke – 4 Tukar 1,3 = menukar urutan posisi kota ke – 1 dengan kota ke – 3
20
Hill Climbing Search Kemungkinan solusi yang mungkin (ruang keadaan) :
A B
C
B
C
D dst
A
C D B D C B D C D B B C
Fungsi heuristik : panjang lintasan yang terjadi Operator digunakan untuk menukar posisi kota yang bersebelahan. Misal : T1,2 : Tukar posisi kota ke 1 dengan kota ke 2
42
21
Keadaan awal, lintasan ABCD (=19)
Level pertama, hill climbing mengunjungi BACD (=17), BACD (=17) < ABCD (=19), sehingga BACD menjadi pilihan selanjutnya dengan operator Tukar 1,2 Level kedua, mengunjungi ABCD, karena operator Tukar 1,2 sudah dipakai BACD, maka pilih node lain yaitu BCAD (=15), BCAD (=15) < BACD (=17) Level ketiga, mengunjungi CBAD (=20), CBAD (=20) > BCAD (=15), maka pilih node lain yaitu BCDA (=18), pilih node lain yaitu DCAB (=17), pilih node lain yaitu BDAC (=14), BDAC (=14) < BCAD (=15) Level keempat, mengunjungi DBAC (=15), DBAC(=15) > BDAC (=14), maka pilih node lain yaitu BADC (=21), pilih node lain yaitu BDCA (=13), BDCA (=13) < BDAC (=14) Level kelima, mengunjungi DBCA (=12), DBCA (=12) < BDCA (=13) Level keenam, mengunjungi BDCA, karena operator Tukar 1,2 sudah dipakai DBCA, maka pilih node lain yaitu DCBA, pilih DBAC, pilih ABCD, pilih DACB, pilih CBDA Karena sudah tidak ada node yang memiliki nilai heuristik yang lebih kecil dibanding nilai heuristik DBCA, maka node DBCA (=12) adalah lintasan terpendek (SOLUSI)
THE MOTIVATION Bill gates, salah satu orang terkaya di dunia, mempunyai motto:
Jika Anda terlahir miskin itu bukan kesalahan Anda, tapi jika Anda mati miskin itu adalah kesalahan Anda".
"
Menurut Bill Gates ada 3 kunci sukses dalam usaha baru. 1. Berada di tempat yang tepat pada waktu yang tepat. 2. Memiliki visi di mana industri / bisnis Anda akan bekerja 3. Mengambil Aksi besar-besaran dan Segera. (Ini adalah waktu untuk bertindak).
44
22
Referensi Aris Marjuni, Materi Ajar: Artificial Intelligence, 2005
45
23
