BAB IV
TEKNIK PELACAKAN
A. Teknik Pelacakan Pelacakan adalah teknik untuk pencarian :sesuatu”. Didalam pencarian ada dua kemungkinan hasil yang didapat yaitu menemukan dan tidak menemukan. Sehingga pencarian merupakan teknik yang penting dalam AI. Hal penting dalam menentukan keberhasilan sistem berdasar kecerdasan adalah kesuksesan dalam pencarian dan pencocokan. Keberhasilan dan kualitas pencarian diukur adari empat cara yaitu: 1. Kelengkapan Apakah algoritma pencarian menjamin untuk mendapatkan sebuah penyelesaian jika ada penyelesaian ? 2. Optimal Apakah algoritma pencarian akan mendapatkan penyeleaian optimal (Misal: penyelesaian dengan biaya lintasan minimum) 3. Kekompleksan waktu Berapa lama waktu yang digunakan untuk menyelesaian permasalahan ? 4. Kekompleksan Ruang Berapa banyak memori yang dibutuhkan untuk melakukan pencarian
Ada beberapa teknik pelacakan: Depth-first Hill-climbing Some path
Breadth-first Beam Best-first
British museum SEARCH
Optimal path
Branch and bound
20
Dynamic Programming A*
Minimax Alpha-beta pruning Games
Progressive deepening Heuristic Pruning Heuristik continuation
Mis. mencari lintasan(path) dari satu kota ke kota lain, dalam suatu jaringan kota Gb.1
A
B
C
S G D
E
F
Lintasan dimulai dari S (starting point) ke G (tujuan akhir) Pencarian lintasan: 1. mencari beberapa lintasan (some path) atau lintasan terpendek 2. berapa banyak traversing lintasan
Sering pergi dari S ke G, akan beruntung jika mencari lintasan yang paling pendek. Jika hanya sekali, lebih baik mencari some path (sembarang lintasan) dan lintasan optimal bisa dicari kemudian.
Cara termudah merubah peta lintasan ke dalam bentuk pohon (tree), dengan membuat beberapa kemungkinan lintasan dari S ke G, dan menghindari lintasan yang siklik (S – A – D – S – A – D)
21
S
A
D
B
D
A
E
B
E
C
E B
F
D
F
B
G
C
11
C 14
F
C
17
F 15
E
A
G G
19 19 17
15 13
G 25
Istilah - Simpul (node) , link : hubungan antar node,
induk dan anak
- Akar (root) : node pada puncak (top) of tree - Terminal node : node yang tidak mempunyai anak - Suatu node adalah ancestor node yang lain (descendant)
jika jumlah anak untuk setiap node sama, maka jumlah anak tersebut disebut branching factor ekspansi simpul (expanding node): proses pembentukan simpul anak dari suatu simpul n node selalu open sampai dia expanded (selesai diperiksa) / closed
B. Pencarian Buta Melebar Pertama (Breadth First Search)
Pada metode ini semua node pada level n akan dikunjungi terlebih dahulu sebelum mengunjungi node-node pada level n+1. Pencarian dimulai dari node akar terus
22
ke level ke-1 dari kiri ke kanan, kemudian berpindah ke level berikutnya demikian pula dari kiri ke kanan hingga ditemukan solusi. (gambar 4.1) A
B
E
C
F
G
H
D
I
J
K
L
M
Algoritma Breadth First: 1. Buat suatu variable Node_list dan tetapkan sebagai keadaan awal. 2. Kerjakan langkag-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, maka Keluar. b. Pada setiap langkah yang aturannya cocok dengan E, kerjakan: -
Aplikasikan aturan tersebut untuk membentuk sustu keadaan baru.
-
Jika keadaan awal adalah tujuan yang diharapkan, sukses, dan keluar
-
Jika tidak demikian, tambahkan keadaan awal yang baru tersebut pada akhir Node_list
¾ Keuntungan: 1. Tidak akan menemui jalan buntu. 2. Jika ada satu solusi, maka breadth first search akan menemukan. Jika ada lebih dari satu solusi, maka solusi minimum akan ditemukan. ¾ Kelemahan: 1. Membutuhkan memori yang besar, karena menyimpan semua node dalam satu pohon. 2. Membutuhkan waktu yang lama, karena akan menguji n level untuk mendapatkan solusi pada level yang ke- (n+1).
23
¾ Analisis Ruang dan Waktu 1. Diasumsikan:
Ada satu solusi (I tujuan ditemukan) pada pohon.
Pohon pelacakan memiliki cabang yang selalu sama, yaitu sebanyak b.
Tujuan dicapai pada level ke-d.
Tujuan dicapai pada pertengahan pohon ( kondisi rata-rata)
2. Analisis Ruang - Antrian pertama memiliki 1 keadaan. - Setelah mencapai langkah pertama, antrian akan berisi b keadaan. - Pemrosesan setiap b keadaan pada level ke-0 akan menambahkan b keadaan lagi pada antrian. - Sehingga setelah dilakukan pemrosesan semua keadaan pada level ke-d, maka antrian akan menyimpan keadaan sebanyak b d −1 . - Karena diasumsikan bahwa tujuan terletak di tengah, maka antrian akan menyimpan b d −1 /2 keadaan (Gambar 4.2)
d
d-1
3. Analisis Waktu
Ukuran waktu diambil dari banyaknya keadaan yang dikunjungi. Jika tujuan diasumsikan bahwa setiap node membutuhkan waktu yang sama dalam pemrosesan maka: Waktu = waktu untuk memproses node-node di level 1 + Waktu untuk memproses node-node di level 2 +…+ Waktu untuk memproses node-node di level ke-(d-1) + Waktu untuk memproses node-node di level ke-(d)/2 = 1 + b + b 2 + b 3 +…….+ b d −1 + b d /2 = 0 (b d )
24
C. Pencarian Mendalam Pertama ( Depth First Search) Pada Depth First Search, Proses pencarian akan dilakukan pada semua anak sebelum dilakukan pencarian ke node-node yang selevel. Pencarian dimulai dari dari node akarke level yang lebih tinggi. Proses ini diulangi terus hingga ditemukan solusi. (gambar 4.3) •
termasuk teknik pelacakan sistematis
•
ruang keadaan direpresentasikan dg. diagram pohon mapun grafik
•
asumsi one path is as good as any other
•
ambil salah satu cabang ( left-to-right order)
•
simpul-simpul paling dalam diperiksa lebih dahulu
•
lebih efektif digunakan jika simpul sasaran (Goal) terletak pada lokasi yang lebih dalam.
contoh simpul S → A → B → C, belum mendapatkan G, kembali ke ancestor terdekat (B), mencari alternatif lain, go to the right B → E → D, belum mencapai G, kembali ke ancestor terdekat (E), mencari alternatif lain, go to the right E→F→G
S A
D •
B C
•
E D
F G
• •
25
Langkah-langkah depth-first-search : •
bentuk queue satu elemen Q (one-elemen-queue) yang berisi simpul akar
•
sampai queue kosong atau Goal bisa dicapai, tentukan bahwa elemen pertama dari Q adalah simpul Goal 1. bila elemen pertama Q adalah simpul Goal do nothing 2. bila elemen pertama Q, BUKAN simpul Goal, ambil elemen pertama dari Q dan tambahkan elemen pertama dari anak-anaknya (first element’s children), from the left to the right, ke elemen depan Q •
jika Goal telah dicapai, nyatakan SUKSES, otherwise nyatakan GAGAL
Urutan pelacakan dengan depth-first-search
S, A , B, C, E, D, F, G Efficiensi dari pelacakan ini dapat ditingkatkan dengan memperhitungkan pemilihan urutan dari cabang pohon yang dipilih (tidak selalu from left-to-theright). Pilihlah cabang yang menjanjikan terlebih dahulu (shortest distance) ¾ Keuntungan
Membutuhkan memori yang relative kecil, karena hanya node-node pada lintasan yang aktif saja yang disimpan.
Secara kebetulan, metode ini akan menemukan solusi tanpa harus menguji lebih banyak lagi yang lain.
¾ Kelemahan:
Memungkinkan tidak ditemukannya tujuan yang diharapkan.
Hanya akan mendapatkan 1 solusi pada setiap pencarian
¾ Analisis Ruang dan Waktu 1. Analisis Ruang
Setelah berjalan 1 langkah, stack akan berisi b node.
Setelah berjalan 2 langkah, stack akan berisi (b-1)+b node
Setelah berjalan 3 langkah, stack akan berisi (b-1)+(b-1)+b node
Setelah berjalan d langkah, stack akan berisi (b-1)x d+1, mencapai maksimum
2. Analisis Waktu
26
Pada kasus terbaik, depth-first-search akan mencapai tujuan pada kedalaman d pertama, sehingga dibutuhkan pencarian sebanyak d+1 node.
Pada kasus terburuk , depth-first-search akan mencapai tujuan pada kedalaman d pada node terakhir, sehingga dibutuhkan pencarian sebanyak : 1+b+b 2 +b 3 +….+b d = (b d +1 -1)/(b-1)
D. Pembangkitan & Pengujian (Generate And Test)
Pada prinsipnya metode ini merupakan penggabungan antara depth-first search dengan pelacakan mundur (backtracking), yaitu bergerak ke belakang menuju pada suatu keadaan awal. Nilai pengujian berupa jawaban ‘ya’ atau ‘tidak’. Algoritma: 1. Bangkitkan suatu kemungkinan solusi (membangkitkan suatu titik tertentu atau lintasan tertentu dari keadaan awal). 2. Uji untuk melihat apakah node tersebut benar-benar merupakan solusinya dengan cara membandingkan node tersebut atau node akhir dari suatu lintasan yang dipilih dengan kumpulan tujuan yang diharapkan. 3. Jika solusi ditemukan, keluar. Jika tidak, ulangi kembali langkah yang pertama.
Contoh 2.3: Traveling Salesman Problem (TSP). Seorang salesman ingin mengunjungi n kota. Jarak antara tiap-tiap kota sudah diketahui. Kita ingin mengetahui rute terpendek dimana setiap kota hanya boleh dikunjungi tepat 1 kali. Misalkan ada 4 kota dengan jarak antara tiap-tiap kota seperti terlihat pada Gambar A 7 D
B
8 3
4 6
5 C
Gambar 4.1 Contoh kasus TSP.
27
Disini, penyelesaian dengan menggunakan generate & test dilakukan dengan membangkitkan solusi-solusi yang mungkin dengan menyusun kota-kota dalam urutan abjad, yaitu: •
A–B–C–D
•
A–B–D–C
•
A–C–B–D
•
A–C–D–B
•
Dan seterusnya (Gambar 2.21).
A
B
C
D
B
C
C
D
B
D C
B
D
C
D
B
C
B
D
Gambar 4.2 Metode Generate dan Test
Misalkan pertama-tama kita mulai dari node A. Kita pilih sebagai keadaan awal adalah lintasan ABCD dengan panjang lintasan (=19). Kemudian kita lakukan backtracking untuk mendapatkan lintasan ABDC (=18). Lintasan ini kita bandingkan dengan lintasan ABCD, ternyata ABDC < ABCD, sehingga lintasan terpilih adalah ABDC. Kita lakukan backtracking lagi untuk mendapatkan lintasan ACBD (=12), ternyata ACBD < ABDC, maka lintasan terpilih sekarang adalah ACBD. Demikian seterusnya hingga kita temukan solusi yang sebenarnya. Tabel 4.3 menunjukkan proses pencarian tersebut. Dari Tabel 4.3 dapat dilihat bahwa pada akhir pencarian, kita peroleh lintasan terpendek adalah A-C-B-D atau D-B-A-C dengan panjang lintasan sebesar 12. Salah satu kelemahan dari metode generate & test ini adalah perlu membangkitkan semua kemungkinan sebelum dilakukan pengujian, sehingga membutuhkan waktu yang cukup besar dalam pencariannya.
28
Tabel 4.3 Alur pencarian dengan generate & test pada TSP. Pencarian ke-
Lintasan
Panjang Lintasan
Lintasan terpilih
Panjang Lintasan terpilih
1.
ABCD
19
ABCD
19
2.
ABDC
18
ABDC
18
3.
ACBD
12
ACBD
12
4.
ACDB
13
ACBD
12
5.
ADBC
16
ACBD
12
6.
ADCB
18
ACBD
12
7.
BACD
17
ACBD
12
8.
BADC
21
ACBD
12
9.
BCAD
15
ACBD
12
10.
BCDA
18
ACBD
12
11.
BDAC
14
ACBD
12
12.
BDCA
13
ACBD
12
13.
CABD
15
ACBD
12
14.
CADB
14
ACBD
12
15.
CBAD
20
ACBD
12
16.
CBDA
16
ACBD
12
17.
CDAB
21
ACBD
12
18.
CDBA
18
ACBD
12
19.
DABC
20
ACBD
12
20.
DACB
15
ACBD
12
21.
DBAC
15
ACBD
12
22.
DBCA
12
ACBD atau DBCA
12
23.
DCAB
17
ACBD atau DBCA
12
24.
DCBA
19
ACBD atau DBCA
12
29
E. Pendakian Bukit (Hill Climbing)
Metode ini hampir sama dengan metode pembangkitan & pengujian, hanya saja proses pengujian dilakukan dengan menggunakan fungsi heuristik. Pembangkitan keadaan berikutnya sangat tergantung pada feedback dari prosedur pengetesan. Tes yang berupa fungsi heuristic ini akan menunjukkan seberapa baiknya nilai terkaan yang diambil terhadap keadaan-keadaan lainnya yang mungkin. •
Mencari solusi pada persoalan-persoalan dimana fungsi harga suatu simpul ke sasaran bisa ditaksir, walaupun tidak selalu benar (heuristik)
•
Pencarian lintasan menuju ke Goal dilakukan dengan cara yang sama dengan depth-first Search, tetapi
•
Pemilihan urutan cabang pohon yang ditelusuri berdasarkan pengukuran jarak tempuh yang terpendek
•
Lebih bagus dari depth-first search
langkah-langkah Hill-Climbing Search •
Bentuk queue satu elemen Q (one-elemen-queue) yang berisi simpul akar
•
Sampai queue kosong atau Goal bisa dicapai, tentukan bahwa elemen pertama dari Q adalah simpul Goal ¾ bila elemen pertama Q adalah simpul Goal do nothing ¾ bila elemen pertama Q, BUKAN simpul Goal, ambil elemen pertama dari Q dan pilihlah elemen pertama dari anak-anaknya yang memiliki jarak tempuh terpendek ke Goal, jika ada, tambahkan ke elemen depan Q •
Jika Goal telah dicapai, nyatakan SUKSES, otherwise nyatakan GAGAL
30
1. Simple Hill Climbing Algoritma: 1. Mulai dari keadaan awal, lakukan pengujian: jika merupakan tujuan, maka berhenti; dan jika tidak, lanjutkan dengan keadaan sekarang sebagai keadaan awal. 2. Kerjakan langkah-langkah berikut sampai solusinya ditemukan, atau sampai tidak ada operator baru yang akan diaplikasikan pada keadaan sekarang: (a.) Cari operator yang belum pernah digunakan; gunakan operator ini untuk mendapatkan keadaan yang baru. (b.) Evaluasi keadaan baru tersebut. i. Jika keadaan baru merupakan tujuan, keluar. ii. Jika bukan tujuan, namun nilainya lebih baik daripada keadaan sekarang, maka jadikan keadaan baru tersebut menjadi keadaan sekarang. iii. Jika keadaan baru tidak lebih baik daripada keadaan sekarang, maka lanjutkan iterasi.
Pada simple hill climbing ini, ada 3 masalah yang mungkin, yaitu: •
Algoritma akan berhenti kalau mencapai nilai optimum local.
•
Urutan penggunaan operator akan sangat berprngaruh pada penemuan solusi.
•
Tidak diijinkan untuk melihat satupun langkah sebelumnya.
Contoh 2.4: Traveling Salesman Problem dengan simple hill climbing. Disini 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. 31
ABC
(19) Tk 1,2
Tk 1,3 Tk 3,4
Tk 2,3
BAC
(17)
ACB
Tk 4,1
ABD
Tk 2,4
DBC
ADC
CBA
Tk 1,2 (15) Tk 2,3
BCA Tk 1,2
Tk 4,1
Tk 3,4
BAD
Tk 2,3
Tk 2,4
DAC
Tk 3,4
Tk 4,1
(20)
BDC
BAC
Tk 1,2
DBC Tk 2,3
Tk 3,4 (19)
BDC
BDC
Tk 2,3
BCD
DCB
BDA
ACB
Tk 2,3 Tk 3,4 Tk 4,1 (13)
BAD
(12)
(14)
DCA
Tk 1,2 (21)
DBA
Tk 1,2
(17)
BCD
(15)
CAB
Tk 1,3
Tk 2,4 (18)
CBA
Tk 1,3
CDA
Tk 3,4 Tk 4,1
BDA Tk 4,1
Tk 2,4 (15)
DBA
Tk 2,4
Tk 2,4
ADC
Tk 1,3
BCA
ADB
Tk 1,3
BAC
CDB
(15)
(16)
Tk 1,3 (19)
ABC
DAC
CBD
Gambar 4.4 Metode Simple Hill Climbing dengan 6 operator.
Operator yang akan kita gunakan, adalah menukar urutan posisi 2 kota dalam suatu lintasan. Apabila ada n kota, dan kita ingin mencari kombinasi lintasan dengan menukar posisi urutan 2 kota, maka kita akan mendapatkan sebanyak: Sehingga kalau ada 4 kota, kita bisa memperoleh:
n! 2!(n − 2)!
4! =6 2!(4 − 2)!
kombinasi.
Keenam kombinasi ini akan kita pakai semuanya sebagai operator, yaitu: Ò Tukar1,2 (menukar urutan posisi kota ke-1 dengan kota ke-2).
32
Ò Tukar2,3 (menukar urutan posisi kota ke-2 dengan kota ke-3). Ò Tukar3,4 (menukar urutan posisi kota ke-3 dengan kota ke-4). Ò Tukar4,1 (menukar urutan posisi kota ke-4 dengan kota ke-1). Ò Tukar2,4 (menukar urutan posisi kota ke-2 dengan kota ke-4). Ò Tukar1,3 (menukar urutan posisi kota ke-1 dengan kota ke-3). Pada Gambar 4.4 terlihat bahwa, pada keadaan awal, lintasan terpilih adalah ABCD (=19). Pada level pertama, hill climbing akan mengunjungi BACD (=17) yang ternyata memiliki nilai heuristik lebih kecil dibandingkan dengan ABCD (17<19), sehingga BACD menjadi pilihan selanjutnya dengan operator terpakai Tukar1,2. Pada level kedua, hill climbing akan mengunjungi ABCD. Karena operator Tukar1,2 sudah digunakan oleh BACD, maka dipilih node yang lain yaitu BCAD (=15). Karena nilai heuristik BCAD lebih kecil dibanding dengan BACD (15<17), maka node BCAD akan menjadi pilihan selanjutnya dengan operator Tukar2,3. Kemudian hill climbing akan mengunjungi CBAD (=20). Karena nilai heuristik CBAD lebih besar jika dibanding dengan BCAD (20>17), maka dipilih node lain. Pencarian menuju ke node BACD, karena operator Tukar2,3 sudah pernah digunakan oleh BCAD, maka dipilih node lain. Kunjungan berikutnya ke node BCDA (=18). Nilai inipun masih lebih besar dari nilai heuristic BCAD, sehingga dipilih node lain. Node yang dikunjungi berikutnya adalah DCAB (=19). Nilai heuristik DCAB ternyata juga lebih besar dibanding dengan BCAD, sehingga pencarian dilanjutkan di node lainnya lagi, yaitu BDAC (=14). Nilai heuristik ini sudah lebih kecil daripada nilai heuristik node BCAD (14<15), maka sekarang node ini yang akan diekplorasi. Pencarian pertama ditemukan node DBAC (=21), yang lebih besar daripada nilai BDAC. Nilai heuristik yang lebih kecil diperoleh pada node BDCA (=13). Sehingga node BDCA ini akan diekplorasi. Pencarian pertama sudah mendapatkan node dengan nilai heuristik yang kebih kecil, yaitu DBCA (=12). Sehingga node ini diekplorasi juga. 33
Dari hasil ekplorasi dengan pemakaian semua operator, ternyata sudah tidak ada node yang memiliki nilai heuristik yang lebih kecil dibanding dengan nilai heuristik DBCA, sehingga sebenarnya node DBCA (=12) inilah lintasan terpendek yang kita cari Misalkan kita tidak menggunakan semua operator, melainkan kita hanya menggunakan 4 operator pertama saja, 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). maka pencarian dengan simple hill climbing ini dapat dilihat pada Gambar 2.23. Lintasan terpendek yang diperoleh adalah B-C-A-D yaitu sepanjang 15. Disini kita akan terjebak pada nilai minimum lokal yang disebabkan oleh kurangnya operator yang kita gunakan. Kita tidak dapat memperoleh nilai minimum globalnya yaitu sebesar 12.
(19)
ABC
Tukar 1,2 Tukar 2,3 (17)
BAC
ACB
Tukar 3,4 Tukar 2,3 Tukar 1,2 (15)
ABC
BCA
CBA
BAC
BCD
ABD
Tukar 4,1
DBC
Tukar 4,1
BAD
Tukar 3,4 Tukar 2,3 Tukar 1,2 (17) (18) (20)
Tukar 3,4
Tukar 4,1
DAC
(17)
DCA
Gambar 4.5. Metode Simple Hill Climbing dengan 4 operator.
34
2. Steepest-Ascent Hill Climbing Steepest-ascent hill climbing sebenarnya hampir sama dengan simple hill climbing, hanya saja gerakan pencarian tidak dimulai dari posisi paling kiri. Gerakan selanjutnya dicari berdasarkan nilai heuristik terbaik. Dalam hal ini urutan penggunaan operator tidak menentukan penemuan solusi. Algoritma: 1. Mulai dari keadaan awal, lakukan pengujian: jika merupakan tujuan, maka berhenti; dan jika tidak, lanjutkan dengan keadaan sekarang sebagai keadaan awal. 2. Kerjakan hingga tujuan tercapai atau hingga iterasi tidak memberikan perubahan pada keadaan sekarang. a. Tentukan SUCC sebagai nilai heuristik terbaik dari successor-successor. b. Kerjakan untuk tiap operator yang digunakan oleh keadaan sekarang: i. Gunakan operator tersebut dan bentuk keadaan baru. ii. Evaluasi keadaan baru tersebut. Jika merupakan tujuan, keluar. Jika bukan, bandingkan nilai heuristiknya dengan SUCC. Jika lebih baik, jadikan nilai heuristic keadaan baru tersebut sebagai SUCC. Namun jika tidak lebih baik, nilai SUCC tidak berubah. c. Jika SUCC lebih baik daripada nilai heuristik keadaan sekarang, ubah node SUCC menjadi keadaan sekarang.
Pada steepest-ascent hill climbing ini, ada 3 masalah yang mungkin, yaitu: • Local optimum: keadaan semua tetangga lebih buruk atau sama dengan keadaan dirinya. • Plateau: keadaan semua tetangga sama dengan keadaan dirinya.
35
• Ridge: local optimum yang lebih disebabkan karena ketidakmampuan untuk menggunakan 2 operator sekaligus.
Contoh 2.5: Traveling Salesman Problem dengan steepest ascent hill climbing. ABC
(19) Tk 1,2 (17)
(12)
BAC (15)
CAB
ACB
Tk 1,2 Tk 3,4 Tk 2,3 (13) (19)
ABC
Tk 1,3 Tk 3,4 Tk 4,1 Tk 2,4 Tk 2,3 (12) (18) (18)
ACD
ABD
Tk 4,1 Tk 2,4 (19)
DCB
DBC Tk 1,3 (16)
ADB
ADC
(20)
CBA
(15)
BCA
Gambar 4.6 Metode Steepest Ascent Hill Climbing.
Pada Gambar 4.6, terlihat bahwa, keadaan awal, lintasan terpilih adalah ABCD (19). Pada level pertama, hill climbing akan memilih nilai heuristik terbaik dari keenam succesor yang ada, yaitu: BACD(17), ACBD(12), ABDC(18), DBCA(12), ADCB (18) atau CBAD(20). Tentu saja yang terpilih adalah ACBD, karena memiliki nilai heuristik paling kecil (=12). Dari ACBD ini akan dipilih nilai heuristik terbaik dari succesornya yaitu: CABD(15), ABCD(19), ACDB(13), DCBA(19), ADBC(16) atau BCAD(15). Ternyata dari keenam successor tersebut memiliki nilai heuristik yang lebih besar disbanding dengan ACDB. Sehingga tidak akan ada perubahan nilai keadaan (tetap ACDB). Hasil yang diperoleh, lintasannya adalah ACDB (12).
36
F. Pencarian Terbaik Pertama (Best First Search)
Metode Best First Search merupakan kombinasi dari metode Depth First Search dan Breadth First Search dengan mengambil kelebihan dari kedua metode tersebut. Apabila metode Hill Climbing tidak diperbolehkan untuk kembali ke node pada level yang lebih rendah meskipun node pada level yang lebih rendah tersebut memiliki nilai heuristic yang lebih baik, lain halnya dengan metode Best First Search. Pada Best First Search, pencarian diperbolehkan mengunjungi node yang ada di level yang lebih rendah, jika ternyata node pada yang lebih tinggi ternyata memiliki nilai heuristic yang lebih buruk. •
gabungan dari metode depth-first dan bread-first search
•
setiap step search, pilih node yang paling menjanjikan (mis. jarak paling pendek), dengan mengaplikasikan fungsi heuristik
•
expansikan node tersebut → successors
•
jika salah satu successors adalah Goal, maka SUKSES
•
jika tidak ulangi proses di atas
Algoritma: 1. Tempatkan node awal A pada antrian OPEN. 2. Kerjakan langkah-langkah berikut hingga tujuan ditemukan atau antrian OPEN sudah kosong: a. Ambil node terbaik dari OPEN; b. Bangkitkan semua successornya; c. Untuk tiap-tiap successor kerjakan:
37
i. Jika node tersebut belum pernah dibangkitkan sebelumnya, evaluasi node tersebut dan masukkan ke OPEN; ii. Jika node tersebut sudah pernah dibangkitkan sebelumnya, ubah parent jika lintasan baru lebih menjanjikan. Hapus node tersebut dari antrian OPEN. Gambar 4.7 menunjukkan metode pencarian terbaik pertama. Diasumsikan bahwa node dengan nilai yang lebih besar, memiliki nilai evaluasi yang lebih baik. Pada saat keadaan awal, antrian berisi A. Pengujian dilakukan pada level pertama, node D memiliki nilai terbaik, sehingga menempati antrian pertama, disusul dengan C dan B. Node D memiliki cabang E dan F yang masing-masing bernilai 2 dan 4. Dengan demikian C merupakan pilihan terbaik dengan menempati antrian pertama. Demikian seterusnya
Antrian OPEN
A
[A]
A
[D,C,B]
C 5
B 3
D 7 [C,F,B,E]
A D
C 5
B 3
C 2
D 4 [G,F,B,E,H]
A C
B 3 C 5
D D 1
C 2
D 4
Gambar 4.7 Metode Best-First Search
38
39
40
