Download - Metode Hill Climbing
![Page 1: Metode Hill Climbing](https://reader036.vdokumen.com/reader036/viewer/2022082404/5681658a550346895dd84c36/html5/thumbnails/1.jpg)
Metode Hill Climbing
Penyusun Denny Agustiawan
![Page 2: Metode Hill Climbing](https://reader036.vdokumen.com/reader036/viewer/2022082404/5681658a550346895dd84c36/html5/thumbnails/2.jpg)
PENDAKIAN BUKIT (HILL CLIMBING)
Metode Hi l l C lambing hampir sama dengan metode pembangk i tan & penguj ian,hanya sa ja proses penguj ian d i lakukan dengan meng gunakan fungs i heur istik . Pembangk itan keadaan ber ikutnya sangat tergantung padafeedback dar i prosedur pengetesan. Tes yang berupa fungsi heuristic ini akan menunjukkan seberapa baiknya nilai terkaan yang diambil terhadap keadaan-keadaan lainnya yang mungkin.
![Page 3: Metode Hill Climbing](https://reader036.vdokumen.com/reader036/viewer/2022082404/5681658a550346895dd84c36/html5/thumbnails/3.jpg)
B.L. Simple Hill Climbing
Metode ini biasanya digunakan untuk traveling salesman problem
![Page 4: Metode Hill Climbing](https://reader036.vdokumen.com/reader036/viewer/2022082404/5681658a550346895dd84c36/html5/thumbnails/4.jpg)
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 : n! 2t(n-2)lSehingga kalau ada 4 kota, kita bisa memperoleh : kombinasi.
Keenam kombinasi ini akan kita pakai 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).
![Page 5: Metode Hill Climbing](https://reader036.vdokumen.com/reader036/viewer/2022082404/5681658a550346895dd84c36/html5/thumbnails/5.jpg)
SteepesLAscent Hill Climbing
Steepest-ascenhti II climbing sebenarnya hampir sama dengan sirnple hitt ctimbing, hanya saja gerakan pencarian tidak dimulai dari posisi paling kiri. Gerakan selanjutnya dicari berdasarkan nilai heuristic terbaik. Dalam hal ini urutan penggunaan operator tidak menentukan penemuan solusi.
![Page 6: Metode Hill Climbing](https://reader036.vdokumen.com/reader036/viewer/2022082404/5681658a550346895dd84c36/html5/thumbnails/6.jpg)
Contoh permasalahannya adalah
![Page 7: Metode Hill Climbing](https://reader036.vdokumen.com/reader036/viewer/2022082404/5681658a550346895dd84c36/html5/thumbnails/7.jpg)
Penyelesaian contoh soalnya dalahP a d a G a m b a t 2 . 2 4 , t e r l i h a t b a h w a , k e a c l a a n a w a l , i i n t a s a n t e r p i i i h a d a l a h A B C D ( 1 9 ) . P a d a l e v e l p e r t a m a , h i l i c l i m b i n g a k a n r n e m i i i h n i l a i h e u r i s ti k t e r b a i k d a r i k e e n a m s u c c e s o r y a n g a d a , y a i t u : B A C D ( 1 7 ) , A C B D ( 1 2 ) , A B D C ( I 8 ) , D B C A ( 1 2 ) , A D C B ( 1 8 ) a t a u C B A D ( 2 0 ) . Te n t u s a j a y a n g t e r p i l i h a d a l a h A C B D , k a r e n a m e m i l i k i n i l a i h e u r i s ti k p a l i n g k e c i l ( = 1 2 ; . D a r i A C B D i n i a k a n d i p i l i h n i l a i h e u r i s ti k t e r b a i k d a r i s u c c e s o r n y a y a i t u : C A B D ( 1 5 ) , A B C D ( 1 9 ) , A C D B ( 1 3 ) , D C B A ( 1 9 ) , A D B C ( 1 6 ) a t a u B C A D ( 1 5 ) . Te r n y a t a d a r i k e e n a m s u c c e s s o r t e r s e b u t m e m i l i k i n i l a i h e u r i s ti k y a n g l e b i h b e s a r d i s b a n d i n g d e n g a n A C B D . S e h i n g g a ti d a k a k a n a d a p e r u b a h a n n i l a i k e a d a a n ( t e t a p A C B D ) . H a s i l y a n g d i p e r o l e h , l i n t a s a n n y a a d a l a h A C B D ( 1 2 ) .
![Page 8: Metode Hill Climbing](https://reader036.vdokumen.com/reader036/viewer/2022082404/5681658a550346895dd84c36/html5/thumbnails/8.jpg)
Contoh soal puzzle:
Operator yang digunakan untuk menggerakkan dari satu keadaan kekeadaan berikutnya adalah:* Ubin kosongkekanan* Ubin kosong ke kiri* Ubin kosong ke atas* Ubin kosong ke bawah
![Page 9: Metode Hill Climbing](https://reader036.vdokumen.com/reader036/viewer/2022082404/5681658a550346895dd84c36/html5/thumbnails/9.jpg)
Penyelesaian soal puzzle:
![Page 10: Metode Hill Climbing](https://reader036.vdokumen.com/reader036/viewer/2022082404/5681658a550346895dd84c36/html5/thumbnails/10.jpg)
Diskripsi penyelesaian soal puzzle:
P a d a G a m b a r 2 . 2 6 t e r l i h a t b a h w a s e m u l a a d a 3 o p e r a t o r y a n g b i a s d i g u n a k a n , y a i t u u b i n k o s o n g d i g e s e r k e k a n a n , k i r i d a n b a w a h . M a s i n g - r n a s i n g k o n d i s i h a s i l d a r i i m p l e m e n t a s i o p e r a t o r m e m b e r i k a n n i l a i h e u r i s ti k 4 , 6 , d a n 5 . N i l a i h e u r i s ti k t e r b e s a r a d a l a h 6 , s e h i n g g a k o n d i s i k e d u a y a n g d i p i l i h . P a d a t a h a p k e d u a , o p e r a t o r y a n g b i a s d i g u n a k a n h a n y a 2 , y a i t u u b i n k o s o n g d i g e s e r k e k a n a n d a n k e b a w a h . m a s i n g - m a s i n g d e n g a n n i l a i h e u r i s ti k 5 d a n 7 . N i l a i h e u r i s ti c y a n g d i h a s i l k a n a d a l a h 7 , d a n k o n d i s i i n i d i p i l i h . P a d a t a h a p k e ti g a , a d a 3 o p e r a t o r y a n g d i g u n a k a n , y a i b u u b i n k o s o n g d i g e s e r k e a t a s , k a n a n , d a n b a w a h . M a s i n g - m a s i n g k o n d i s i m e m i l i k i n i l a i h e u r i s ti k 6 , 8 , d a n 6 . K a r e n a n i l a i 8 m e r u p a k a n s o l u s i , m a k a p e n c a r i a n t e l a h b e r a k h i r.