METODE PENCARIAN
ì
Irvanizam Zamanhuri, M.Sc Dr. Taufiq A. Gani, M.EngSc Jurusan Informatika Universitas Syiah Kuala http://informatika.unsyiah.ac.id/irvanizam
Teknik-‐Teknik Search (1/3) ì Hal-‐hal yang muncul dalam teknik pencarian : ì Arah Search ì Topologi proses search ì Penggunaan fungsi heuris
tersebut ì ARAH SEARCH ì Dapat dilakukan : ì Maju à bermula dari keadaan awal (start state) ì Mundur à diawali dari keadaan tujuan (goal state)
Teknik-‐Teknik Search (2/3) ì TOPOLOGI SEARCH ì Ada 2 macam penggambaran problem, yaitu dalam bentuk : ì TREE (Tree) ì Graph
ì TREE ì Merupakan graf dimana 2 simbol memiliki paling
banyak satu lintasan yang menghubungkannya. ì Tidak ada loop dalam TREE. ì Contoh : problem ember air.
Teknik-‐Teknik Search (3/3) ì GRAPH ì Graph dibedakan menjadi 2 (dua): ì Graph berarah ì Graph Tidak berarah ì Teknik searching dalam Kecerdasan Buatan (AI)
digunakan untuk mencari solusi dari suatu permasalahan.
ì Langkahnya adalah dengan mendefinisikan terlebih
dahulu Ruang Masalah (State)
Ruang Masalah Keadaan Awal (Ini
Studi Kasus : Masalah Galon Air Kran air
4 liter
3 liter
A
B
ì Bagaimana caranya bisa didapatkan air dengan
ukuran tepat 2 liter di Galon B?
Studi Kasus : Masalah Galon Air §
Keadaan Awal à Galon A dan B masih kosong No Kejadian yang mungkin untuk masalah galon air
§
1
Isi penuh galon A
2
Isi penuh galon B
3
Buang sebagian air dari galon A
4
Buang sebagian air dari galon B
5
Kosongkan isi galon A
6
Kosongkan isi galon B
7
Tuang air dari galon A ke galon B sampai galon B penuh
8
Tuang air dari galon B ke galon A sampai galon A penuh
9
Tuang semua air dari galon A ke galon B
10 Tuang semua air dari galon B ke galon A
Tujuan (Goal) à Galon B berisi 2 liter air, Galon A berisi n liter air
Studi Kasus : Masalah Galon Air ì Solusi Galon A
Galon B
No. Kejadian
0 liter
0 liter
Ini
0 liter
3 liter
2
3 liter
0 liter
10
3 liter
3 liter
2
4 liter
2 liter
8 à Goal
Performance Searching (1/3) ì Evaluasi sebuah pencarian akan sangat kompleks ì Dasar pengukuran dari evaluasi : ì Seberapa cepat search menemukan penyelesaian ì Seberapa cepat search menemukan penyelesaian
yang baik
ì Kecepatan search ditentukan : ì Panjang Lintasnya. ì Jumlah sesungguhnya penulusuran node.
Performance Searching (2/3) §
Untuk mengukur performansi metode pencarian, terdapat 4 kriteria yang dapat digunakan : §
Completeness § Apakah solusi pas< ditemukan?
§
Time Complexity § Berapa lama waktu yang diperlukan
§
Space Complexity § Berapa banyak memori yang dibutuhkan
§
Op<mally § Apakah solusi yang ditemukan adalah solusi yang
terbaik?
Performance Searching (3/3) ì Time & Space complexity diukur berdasarkan : ì b à faktor percabangan dari search tree ì d à depth (kedalaman) dari solusi op<mal ì m à kedalaman maksimum dari search tree (bisa infinite)
Jenis Teknik Pencarian ¨ Ada beberapa teknik untuk mencari kemungkinan
penyelesaian, yaitu :
¨ Blind Search (Uninformed Search) ¤ Depth First Search (DFS) ¤ Breadth First Search (BFS) ¤ Uniform Cost Search (UCS) ¤ Depth Limited Search (DLS) ¤ Itera=ve Deepening Search (IDS)
¤ Heuris=k Search (Informed Search) ¤ Hill-‐Climbing Search ¤ Least-‐Cost Search ¤ Best First Search
BLIND SEARCH (Breadth First Search) ì Pada metode ini diperiksa se
yang sama sebelum mengolah ke level berikutnya yang lebih dalam.
ì Pencarian dilakukan pada semua simpul dalam
se
ì Jika pada satu level belum ditemukan solusinya,
maka pencarian dilanjutkan pada level berikutnya.
BLIND SEARCH (Breadth First Search)
BLIND SEARCH (Breadth First Search) ì Keuntungan Breadth First Search : ì Tidak akan menemui jalan buntu ì Jika ada solusi, maka Breadth First Search akan
menemukannya, jika lebih dari satu maka solusi akan ditemukan
ì Kelemahan Breadth First Search ì Membutuhkan memori yang cukup banyak, karena
menyimpan semua node dalam satu pohon ì Membutuhkan waktu yang cukup lama, karena menguji n level untuk mendapatkan solusi pada level yang ke(n+1)
BLIND SEARCH (Breadth First Search) ì Sifat Breadth First Search : ì Complete ì Ya, jika b terbatas
ì Time Complexity b + b 2 + b3 +... + b d = b(b d !1) / (b !1) = O b d+1 = O b d
( )
( )
ì Space Complexity
O (bd )
ì Op<mal ì Ya, jika semua step cost sama, tapi pada umumnya
Peta Aceh ì Contoh Kasus : ì ì ì ì ì ì ì ì ì ì ì ì ì ì ì ì
B.Aceh–Sabang Sabang–Calang Calang–Jantho Jantho–Sigli Sigli–Meulaboh Meulaboh–Bireuen Bireuen–Bl.Pidie Bl.Pidie–Simeulu
: 1000 KM : 1000KM : 800 KM : 1900 KM : 1500 KM : 1800 KM : 500 KM : 1000 KM
Simeulue–Takengon : 1500 KM Takengon–Lhokseumawe: 1500 KM Lhokseumawe–Tapaktua : 1000KM Tapaktuan-‐Singkil : 800KM Singkil-‐Bl.Kejren : 900KM Bl.Kejren-‐Kutacane : 700KM Kutacane-‐Langsa Langsa-‐Perlak
: 900KM :1000KM
Tree : Kasus Peta Aceh
BLIND SEARCH (Depth First Search) ì Pencarian dilakukan pada suatu simpul dalam se
level dari yang paling kiri.
ì Jika pada level yang terdalam, solusi belum
ditemukan, maka pencarian dilanjutkan pada simpul sebelah kanan dan simpul yang kiri dapat dihapus dari memori
ì Jika pada level yang paling dalam
solusi, maka pencarian dilanjutkan pada level sebelumnya.
ì Demikian seterusnya sampai ditemukan solusi
BLIND SEARCH (Depth First Search) ì Metode pencarian dapat dilihat seper< gambar :
BLIND SEARCH (Depth First Search) ì Keuntungan : ì Membutuhkan memori rela
BLIND SEARCH (Depth First Search) § Sifat Depth First Search §
Complete
§ Tidak Commplete, jika pohon yang dibangkitkan
mempunyai level yang sangat dalam (
§
Time Complexity
§
Space Complexity
§
Op<mal
( )
Ob
m
O(bm)
§ Tidak op<mal, karena jika terdapat lebih dari satu solusi
yang sama tetapi berada pada level yang berbeda, maka DFS
Peta Aceh ì Contoh Kasus : ì ì ì ì ì ì ì ì ì ì ì ì ì ì ì ì
B.Aceh–Sabang B.Aceh–Calang Calang–Meulaboh Meulaboh–Bl.Pidie Bl.Pidie–Tapaktuan Bl.Pidie–Singkil Meulaboh–Simulue B.Aceh–Jantho
: 1000 KM : 1000KM : 800 KM : 1900 KM : 1500 KM : 1800 KM : 500 KM : 1000 KM
B.Aceh–Sigli Sigli–Bireuen Bireuen–Takengon Mtakengon-‐Bl.Kejren Takengon-‐Kutacane Bireuen-‐Lhokseumawe
: 1500 KM : 1500 KM : 1000KM : 800KM : 900KM : 700KM
Lhokseumawe-‐Langsa Lhokseumawe-‐Perlak
: 900KM :1000KM
Tree : Kasus Peta Aceh
BLIND SEARCH (Uniform Cost Search) ì Konsepnya hampir sama dengan BFS ì Pada UCS, menggunakan urutan biaya dari yang
paling kecil sampai terbesar
ì UCS berusaha untuk menemukan solusi dengan
total biaya terendah.
A
5
S
8
B
12
7 2 10
C
G
Latihan: (Problem Solving Agent) ì 8-‐Puzzle Problem : ì Contoh 8-‐puzzle, puzzle ukuran 3x3 dengan 8 angka dan
satu buah spasi kosong.
ì Goal : letakkan angka tersebut berurutan seper< gambar
berikut:
Referensi ì Sebagian besar materi(slide) disiapkan oleh
(Sekolah Tinggi Ilmu Komputer Indonesia (STIKI) Malang.
ì George F. Luger, Ar<ficial Intelligence, Addison
Wesley, Fourth Edi
ì Stuart Russell & Peter Norvig, Ar<ficial Intelligence:
A Modern Approach, Third Edi
