Tugas ke-2 dibawah ini dibuat untuk
memenuhi tugas mata kuliah Pengantar Kecerdasan Tiruan ( AI ) yang diampu oleh
Mia Kamayani ST,MT.
8 – PUZZLE
Permasalahan pada 8 puzzle adalah
bagaimana caranya agar dapat menyusun petak2/ubin puzzle sesuai dengan urutannya,
namun sebelumnya petak-petak pada puzzle akan
diacak letaknya. Perhatikan gambar dibawah ini:
Untuk
menyelesaikan permasalahan 8 puzzle kita menggunakan metode Heuristic Search
yang Greddy Best.
Sebelumnya
sudah dijelaskan bahwa pada Greddy Best nilai f(n) = h(n), maka pada
permasalahan 8 puzzle, menentukan nilai heuristic atau h(n)nya ada 2 cara,
yaitu : Jumlah ubin yang salah tempat dan Total Jarak.
Pada
pembahasan kali ini saya akan membahas permasalahan 8 puzzle dengan jumlah ubin
yang salah tempat.
# LETAK
UBIN SALAH TEMPAT #
Perhatikan gambar dibawah ini :
Jika kita perhatikan baik-baik jumlah ubin yang salah tempat sebanyak 6 buah. Ingat kembali kita ingin membuat goal state seperti gambar 1.0.
Kita mulai menyelesaikan puzzle ini
dengan patokan pada ubin kosong, jika kita lihat ada 3 pilihan yang dapat kita
lakukan, yaitu :
1)) Naikkan ubin
7 (DOWN) jika kita hitung jumlah ubin yang salah tempat menjadi 7
buah.
2)) Turunkan ubin
1 (UP) ubin yang salah tempat = 7 buah.
3)) Geser ubin 4 ke kiri (RIGHT) ubin
yang salah tempat = 5 buah ( maka langkah ini lah yang di ambil ).
Selanjutnya ada 3 kemungkinan yang dapat kita lakukan :
1)) Pindah kan 8 (UP) = 5 (banyak ubin
yang salah tempat).
2)) Pindahkan 6 (DOWN) = 5.
3)) Pindahkan 3 (RIGHT) = 5
Karena
semuanya memiliki nilai f(n) yang sama, maka kita pilih ubin yang pertama kali
kita pindahkan sehingga posisi ubin menjadi seperti dibawah ini.
Kemudian ada 2 kemungkinan yang dapat kita lakukan :
1)) Pindahkan 1 (LEFT) = f(n)=6 (ubin
yang salah tempat).
2)) Pindahkan 2 (RIGHT) = f(n)=4 ( kita
pilih 2 karena f(n) kecil ), Sehingga puzzle menjadi :
Kemudian
pindahkan 3 (DOWN), sehingga menjadi :
Kembali
muncul pilihan :
1)) Pindahkan 8 (LEFT) = f(n) = 3.
2)) Pindahkan 5 (DOWN) = f(n) = 3.
Karena
kedua pilihan memiliki nilai n yang sama maka kita pilih pilihan pertama (LEFT),
sehingga :
Kemungkinan selanjutnya terdapat dua pilihan :
1)) Pindahkan 4 (LEFT) = f(n)= 4.
2)) Pindahkan 6 (DOWN) = f(n)= 3
(dipilih), Sehingga
menjadi :
Kemungkinan berikutnya :
1)) Pindahkan 5 (LEFT) = f(n)=3
(dipilih).
2)) Pindahkan 7 (RIGHT) = f(n)=3, Sehingga
menjadi :
Kemudian pindahkan 8 (UP), sehingga menjadi :
Kemudian muncul pilihan kembali, yaitu :
1)) Pindah 6 (LEFT)= f(n)= 2. (dipilih)
2)) Pindah 3 (UP) = f(n) = 4, Sehingga menjadi :
Kemudian pindahkan 5 (DOWN), sehingga posisinya menjadi :
Dan langkah terakhir untuk mencapai Goal State yaitu pindahkan 8 (RIGHT), sehingga posisinya seperti berikut :
Selanjutnya dari proses tersebut dapat dibuat Binary Tree sebagai berikut :
>> Note
: warna hijau adalah state yang dipilih, sedangkan warna kuning state yang tidak dipilih.
>> QUEUE FIFO dengan BFS :
>> SEQUENCE penelusuran Node : a
-> b -> c -> d -> e -> f -> g -> h -> i -> j -> k
-> l -> m -> n -> o -> p -> q -> r -> s -> t ->
u.
>> DEFINISI PROBLEM 4 ITEMS :
i.
Initial State : definisi awal dari
sebuah state yang bermasalah.
ii.
Successor Function : ubin kosong
bergerak ke atas, kanan, bawah dan kiri.
iii.
Path Cost :
> Path
yang kita ambil yaitu dengan warna hijau. Path to Goal :
Right (d)
Up (e)
Right (h)
Down (j)
Left (l)
Down (n)
Right (p)
Up (q)
Left (r)
Down (t)
Right (u)
iv.
Goal State : state akhir yang
diinginkan.
SUMBER :
