KECERDASAN BUATAN (ARTIFICIAL INTELLIGENCE)
PERTEMUAN 3 SEARCHING
1
Metode Pencarian
Terdapat banyak metode yang telah diusulkan. Semua metode yang ada dapat dibedakan ke dalam 2 jenis : 1. Pencarian buta / tanpa informasi (blind (blind / unun-informed search)) search 2. Pencarian heuristik / dengan informasi (heuristic (heuristic atau informed search) search)
setiap metode mempunyai karakteristik yang berbedaberbeda-beda dengan kelebihan dan kekurangan masingmasing-masing. 2
4 Kriteria mengukur performansi 1. Completeness : Apakah metode tersebut menjamin penemuan solusi jika solusinya memang ada? 2. Time complexity : Berapa lama waktu yang diperlukan ? 3. Space complexity : Berapa banyak memori yang diperlukan ? 4. Optimality : Apakah metode tersebut menjamin menemukan solusi yang terbaik jika terdapat beberapa solusi yang berbeda ? 3
Heuristic Searching Sebagai Dasar dari Kecerdasan Buatan
Para peneliti awal kecerdasan buatan menitik beratkan pada penyelesaian masalah yang tidak menggunakan metoda komputasi konvensional konvensional..
Hal ini disebabkan metoda pemecahan masalah konvensional tidak dapat lagi digunakan digunakan..
Permasalahan pada sistem AI tidak memiliki algoritma tertentu.. Kalaupun ada tentulah sangat kompleks tertentu kompleks..
Karena itu haruslah ditemukan sebuah teknik baru yang mirip dengan cara yang digunakan oleh manusia untuk menyelesaikan masalah dan dapat diimplementasikan pada komputer.. komputer 4
Salah satu metoda yang cukup terkenal adalah metoda searching searching..
Searching dalam sebuah struktur data telah menjadi dasar bagi algoritma komputer komputer,, tetapi proses searching pada AI memiliki perbedaan perbedaan..
Metoda searching pada AI merupakan searching terhadap problem space bukan searching data (e.g., angka angka,, karakter karakter,, string) tertentu tertentu..
5
Proses searching ini berupa jalur yang menggambarkan keadaan awal sebuah masalah menuju kepada penyelesaian masalah yang diinginkan (i.e., the solved problem).
Jalur-jalur ini mengambarkan langkahJalurlangkah-langkah penyelesaian masalah.
Melalui proses searching menuju sebuah penyelesaian akan terbentuk sebuah solution space.. space
6
Perhatikan contoh penyelesaian masalah komputer pada Gambar 1.4. Langkah pertama untuk mengetahui apakah komputer dapat digunakan atau tidak adalah menmenswitch ON. Selanjutnya dengan melakukan inspeksi terhadap kondisi lampu indikator kita dapat menentukan langkah berikutnya. Misalnya kondisi lampu OFF. Dengan melakukan searching terhadap problem space kita akan tiba pada sebuah penyelesaian masalah agar komputer dapat diaktifkan kembali. 7
8
BLIND / UNUN-INFORMED SEARCH Istilah blind atau buta digunakan karena memang tidak ada informasi awal yang digunakan dalam proses pencarian. Berikut ini, sekilas 6 metode yang tergolong blind search a. Breadth--First Search (BFS) Breadth b. Depth--First Search (DFS) Depth c. Depth--Limited Search (DLS) Depth d. Uniform Cost Search (UCS) e. Iterative--Deepening Search (IDS) Iterative f. Bi--Directional Search (BDS) Bi
9
1. BreadthBreadth-first Search
Breadth-first search (BFS) melakukan Breadthproses searching pada semua node yang berada pada level atau hirarki yang sama terlebih dahulu sebelum melanjutkan proses searching pada node di level berikutnya. Urutan proses searching BFS ditunjukkan dalam Gambar 1.6 adalah: A,B,C,D,E,F,
10
11
Pada metode BreadthBreadth-First Search, semua node pada level n akan dikunjungi terlebih dahulu sebelum mengunjungi nodenode-node pada level n+1
Pencarian dimulai dari node akar terus ke level keke-1 dari kiri ke kanan, kemudian berpindah ke level berikutnya demikian pula dari kiri ke kanan hingga ditemukannya solusi 12
13
S A
D
B C
D E
E
F G
E
B G
C
A
F
B
B
G
C
C
E
G
14
15
16
17
18
Tidak akan menemui jalan buntu (solusi lebih optimal)
Jika ada satu solusi, maka breadthbreadth-first search akan menemukannya. Dan jika ada lebih dari satu solusi, maka solusi minimum akan ditemukan.
19
Membutuhkan memori yang cukup banyak, karena menyimpan semua node dalam satu pohon (membutuhkan simpul yang umumnya relatif banyak banyak))
Membutuhkan waktu yang cukup lama, karena akan menguji n level untuk mendapatkan solusi pada level yang keke-(n+1) 20
2. DepthDepth-first Search
Depth-first search (DFS) adalah proses searching sistematis Depthbuta yang melakukan ekpansi sebuah path (jalur) menuju penyelesaian masalah sebelum melakukan ekplorasi terhadap path yang lain. Proses searching mengikuti sebuah path tunggal sampai menemukan goal atau dead end. Apabila proses searching menemukan deaddead-end, DFS akan melakukan penelusuran balik ke node terakhir untuk melihat apakah node tersebut memiliki path cabang yang belum dieksplorasi.
21
Apabila cabang ditemukan ditemukan,, DFS akan melakukan pencarian pada cabang tersebut tersebut.. Apabila sudah tidak ada lagi cabang yang dapat dieksplorasi dieksplorasi,, DFS akan kembali ke node parent dan melakukan proses searching terhadap cabang yang belum dieksplorasi dari node parent sampai menemukan penyelesaian masalah masalah.. Urutan proses searching DFS ditunjukkan dalam Gambar 1.5 adalah:: A, B, E, F, G, C, ... adalah
22
23
S A
D
B C
D E
E
F G
E
B G
C
A
F
B
B
G
C
C
E
G
24
Kelebihan DFS adalah:
Pemakaian memori hanya sedikit, berbeda jauh dengan BFS yang harus menyimpan semua node yang pernah dibangkitkan. Jika solusi yang dicari berada pada level yang dalam dan paling kiri, maka DFS akan menemukannya secara cepat.
25
Kelemahan DFS adalah:
Jika pohon yang dibangkitkan mempunyai level yang dalam (tak terhingga), maka tidak ada jaminan untuk menemukan solusi (Tidak Complete Complete). ). Jika terdapat lebih dari satu solusi yang sama tetapi berada pada level yang berbeda, maka pada DFS tidak ada jaminan untuk menemukan solusi yang paling baik (Tidak (Tidak Optimal). Optimal ).
26
3. DepthDepth-Limited Search (DLS)
Metode ini berusaha mengatasi kelemahan DFS (tidak complete) dengan membatasi kelemahan maksimum dari suatu jalur solusi.
Tetapi, sebelum menggunakan DLS, kita harus tahu berapa level maksimum dari suatu solusi.
27
Definisi
Algoritma Depth Depth--Limited Search (DLS), adalah salah satu jenis algoritma pencarian solusi solusi.. Algoritma ini dijalankan dengan cara membangkitkan pohon pencarian secara dinamis.. Pencarian solusi dilakukan secara mendalam dinamis mendalam..
Pada dasarnya, algoritma DLS sama dengan algoritma DFS, hanya saja dalam permasalahan penelusuran graf, sebelumnya ditentukan terlebih dahulu batas maksimum level yang dikunjungi.
28 www.themegallery.com
Algoritma
Misalkan terdapat graf/pohon dengan n buah simpul dan v merupakan simpul awal penelusuran maka algoritma DFS adalah sebagai berikut:
1.
Tentukan batas kedalaman pohon yang akan dikunjungi.
Kunjungi simpul v.
2.
3.
Kunjungi simpul w yang bertetangga dengan simpul v, yang berada di kedalaman pohon <= batas. 29 www.themegallery.com
Ulangi DLS mulai dari simpul w.
4.
5.
6.
Ketika mencapai simpul u sedemikian sehingga semua simpul yang bertetangga dengannya telah dikunjungi, pencarian dirunut-balik (backtrack) ke simpul terakhir yang dikunjungi sebelumnya dan mempunyai simpul w yang belum dikunjungi.
Pencarian berakhir bila tidak ada lagi simpul yang belum dikunjungi yang dapat dicapai dari simpul yang telah dikunjungi dalam kedalaman pohon <= batas. 30 www.themegallery.com
Kelebihan dan Kekurangan
DLS lahir untuk mengatasi kelemahan DFS(tidak complete) dengan membatasi kedalaman maksimum dari suatu jalur solusi solusi.. Tetapi harus diketahui atau ada batasan dari sistem tentang level maksimum maksimum.. Jika batasan kedalaman terlalu kecil, DLS tidak complete complete..
31 www.themegallery.com
S A B C
D D
E
E
E F
A B
B
Jarak dan E
Jml Langkah 1. 2. 3.
SE SB SG 32
Contoh 1
Bila simpul awal adalah 1 dan batas kedalaman adalah 3 maka urutan dikunjunginya adalah 1, 2, 4, 5, 3, 6,7. 33 www.themegallery.com
Contoh 2
Bila simpul awal juga 1 dan batas kedalaman adalah 3 maka urutan dikunjunginya adalah 1, 2, 5, 6, 3, 7, 4 34 www.themegallery.com
4. Uniform Cost Search (UCS)
Konsepnya hampir sama dengan BFS, 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. 35
5. IterativeIterative-Deepening Search (IDS) IDS merupakan metode yang menggabungkan kelebihan BFS (Complete dan Optimal) dengan kelebihan DFS (space complexity rendah atau membutuhkan sedikit memori) Tetapi konsekwensinya adalah time complexitynya menjadi tinggi.
36
n=0
n=1
n=2
S
n=3 A B
C
D D
E
E
E F
A B
B
E 37
n=4 S A B C
D D
E F
E
E B
A
F
B
G
C
B
E
C 38
n=5 S A
D
B C
D E
E
F G
E
B G
C
A
F
B
B
G
C
C
E
G
39
The example node set Initial state
A B
C
D
E
F
Goal state
G H
I
J
K
L
M N
O
P
Q
S
T
U V
W X
Y
Z
R
Press space to see a IDS of the example node set
40
A
We Node begin A iswith thenour expanded initial state: and removed the node labeled from the A. queue. This node Press is added space. to the queue. Press space to continue
As this is the 0th iteration of the search, we cannot search past any level greater than zero. This iteration now ends, and we begin the 1st iteration.
Press space to begin the search Size of Queue: 01
Queue: A Empty
Nodes expanded: 10
Current Action: Expanding
Current level: 0n/a
ITERATIVE DEEPENING SEARCH PATTERN (0th ITERATION)
41
We Node The now B search isback expanded now track moves to and expand removed to level node one from C, of and the queue. the theprocess node Press set. continues. space. Press space Presstospace. continue
B
C
A D
Node We again A is expanded, begin withthen our removed initial state: from the the node queue, labeled andA.the Note revealed that the nodes 1st iteration are added carriestoon thefrom front the . Press 0th, and space. therefore the ‘nodes expanded’ value is already set to 1. Press space to continue
E
F
As this is the 1st iteration of the search, we cannot search past any level greater than level one. This iteration now ends, and we begin a 2nd iteration.
Press space to continue begin thethe search search Size of Queue: 012345
Queue: A B, F C, D, E, F Empty C, D, F E, D, E, F E, F
Nodes expanded: 7654321
Current Action: Expanding Backtracking
Current level: 10n/a
ITERATIVE DEEPENING SEARCH PATTERN (1st ITERATION)
42
Node The search Bexpanding ismove expanded then and tothe level of We After now to moves level node two G we ofrevealed backtrack theone node the nodes node added set. Press to the space front of to the continue queue. set. to expand Press space node to H.continue. The process then Press spaceuntil to continue. continues goal state. Press space
B
A
C
G H
I
D
J
K
Node We Again, again Awe is begin removed expand with node from ourAthe initial to reveal queue state: the and the node level each revealed one labeled nodes. node Press A. is Note added space. thattothe the2nd front of iteration the queue.carries Press on space. from the 1st, and therefore the ‘nodes expanded’ value is already set to 7 (1+6). Press space to E F continue the search
L
Node L is located on the second level and the search returns a solution on its second iteration. Press space to end.
Press space to continue the search Size of Queue: 034561
Queue: A B,J, G, H, C, I, J, D, K, L, Empty D, C, E, D, H,D, C, L, E, F D, E, D, C,E, FF E, E, D,FFF E, F
Nodes expanded: 16 987 10 11 12 13 14 15
CurrentSEARCH Action: Backtracking Expanding FINISHED
Current level: 210n/a
ITERATIVE DEEPENING SEARCH PATTERN (2nd ITERATION)
43
6. Bi Bi--Directional Search (BDS)
Pencarian dilakukan dari dua arah : pencarian maju (dari start ke goal) dan pencarian mundur (dari goal ke start). Ketika dua arah pencarian telah membangkitkan simpul yang sama, maka solusi telah ditemukan, yaitu dengan cara menggabungkan kedua jalur yang bertemu.
44
