ALGORITMA PENCARIAN (HEURISTIC)

Universitas Dian Nuswantoro

ALGORITMA PENCARIAN (HEURISTIC) Farah Zakiyah Rahmanti, M.T Diperbarui 2016

Overview    



Pengertian Pencarian Heuristik Generate and Test Hill Climbing Best First Searching Latihan


Pencarian Heuristik 

Merupakan teknik yang digunakan untuk meningkatkan efisiensi dari proses pencarian.



Dalam pencarian ruang keadaan, heuristik adalah aturan untuk memilih cabang-cabang yang paling mungkin menyebabkan penyelesaian permasalahan dapat diterima.


Metode Pencarian Heuristik 

 

Generate and Test (Pembangkitan dan Pengujian) Hill Climbing Best First Search


Generate and Test 

Pembangkitan dan pengujian.



Metode yang paling sederhana dalam pencarian heuristic.



Metode gabungan dari DFS dan pelacakan mundur (backtracking) karena solusi harus dibangkitkan secara lengkap sebelum dilakukan test.



Jika ruang masalahnya sangat luas, mungkin memerlukan waktu yang sangat lama.


Algoritma Generate and Test 

Pada gambar di bawah ini, terdapat 12 kota

A, B, C, D, E, F, G, H, I, J, K, Z. 

Pak pos ingin mengirimkan barang dari kota A ke kota Z.



Problem : lintasan dengan jarak terpendek?



Keadaan awal : A



Goal : Z



Algoritma :

1. Bangkitkan solusi menggunakan algortima DFS. Inisialisasi solusi pertama menjadi NewSolution. 2. Kriteria pengujian yang digunakan. IF NewSolution < Solution then Solution = NewSolution 3. Berhenti pencarian, IF sudah menemukan solusi (jarak terpendek). Else kembali ke langkah 1. Universitas Dian Nuswantoro


Solution = Max



NewSolution = getNewSolution().



If NewSolution < Solution, then Solution = NewSolution.



Iterasi 1 :



F(A-B-D-E-G-Z) = 4+3+4+6+7 = 24



Iterasi 2 :



F(A-B-D-E-G-H-Z) = 4+3+4+6+2+6 = 25



If F(A-B-D-E-G-Z) < F(A-B-D-E-G-H-Z), then Solution = F(A-B-D-E-G-Z) = 24



Iterasi 3 :



F(A-C-E-G-Z) = 5+3+6+7 = 21



If F(A-C-E-G-Z) < F(A-B-D-E-G-Z), then Solution = F(A-C-E-G-Z) = 21



Iterasi 4 :



F(A-C-E-G-H-Z) = 5+3+6+2+7 =23



Karena F(A-C-E-G-H-Z) > F(A-C-E-G-Z), then Solution = F(A-C-E-G-Z) = 21



Tidak ada lagi solusi yang bisa dibangkitkan, iterasi dihentikan.



Kesimpulan : jarak terpendek F(A-C-E-G-Z) = 21 Universitas Dian Nuswantoro

Studi Kasus Penyelesaian dengan Hill Climbing


Algoritma Hill Climbing 





1. Buat sebuah antrian, inisialisasi node pertama dengan root dari tree. 2. Bila node pertama, jika ≠ GOAL, node dihapus diganti dengan anak-anaknya dengan urutan yang paling kecil jaraknya. 3. Bila node pertama = GOAL, selesai.


Algoritma Hill Climbing



Lintasan yang didapat S-B-C-E-Z = 10 Universitas Dian Nuswantoro

Hill Climbing Keuntungan 



Kelemahan

Membutuhkan memori yang relatif kecil.



Algoritma akan berhenti kalau mencapai nilai lokal optimum.

Karena hanya node-node pada lintasan yang aktif saja yang disimpan.



Perlu menentukan yang tepat.

Menemukan solusi tanpa harus menguji lebih banyak lagi dalam ruang keadaan.


aturan

Studi Kasus Penyelesaian dengan Best First Search


Algoritma Best First Search 



1. Buat sebuah antrian/queue, inisialisasi node pertama dengan root dari tree. 2. Bila node pertama, jika ≠ GOAL, node dihapus & diganti dengan anak-anaknya. Selanjutnya keseluruhan node yang di Queue di-sort ascending.



3. Bila node pertama = GOAL, selesai.


Algoritma Best First Search S



B

A

C

A

A

E

A

A

D

Z

A

A

D

Lintasan yang didapat : S-B-C-E-Z = 10 Universitas Dian Nuswantoro

Best First Search Keuntungan 



Kelemahan

Membutuhkan memori yang relatif kecil.



Algoritma akan berhenti kalau mencapai nilai lokal optimum.

karena hanya node-node pada lintasan yang aktif saja yang disimpan.



Tidak diijinkan untuk melihat satupun langkah sebelumnya.

Secara kebetulan, metode best first search akan menemukan solusi tanpa harus menguji lebih banyak lagi dalam ruang keadaan.


Latihan   

Halaman 118 : No. 3 No. 6 a, b


Terima Kasih


ALGORITMA PENCARIAN (HEURISTIC)

Recommend Documents