8 Puzzle problem AI

permasalahan pada 8 puzzle adalah bagaimana caranya agar dapat menyusun petak2/ubin puzzle sesuai dengan urutannya. namun seblumnya petak-petak pada puzzle akan di acak letaknya.
lihat gambar.


untuk menyelesaikan permasalahan 8 puzzle kita menggunakan metode Heuristic search yang Greddy Best

Sebelumnya sudah di jelaskan bahwa pada Greddy best nilai f(n) = h(n)
maka pada permassalahan 8 puzzle, menentukan nilai heuristic atau h(n)nya ada 2 cara
1. jumlah ubin yang salah tempat.
2. total jarak.

1. LETAK UBIN SALAH TEMPAT.
kalau kita lihat, banyak ubin yang salah tempat ada 6 buah

kita mulai menyelesaikan puzzle ini dengan patokan pada ubin kosong, jika kita lihat ada 3 pilihan yang dapat kita lakukan
1. naikkan ubin 7 (DOWN) jika kita hitung jmlah 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
pindah kan 8 (UP) = 5 (banyak ubin yang salah tempat)
ppindahkan 6 (DOWN) = 5
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
[1    2]
[4 8 3]
[7 6 5]

kemudian ada 2 kemungkinan yang dapat kita lakukan
pindahkan 1 (LEFT) = f(n)=6 (ubin yang salah tempat)
pindahkan 2 (RIGHT) = f(n)=4 (kita pilih karena f(n) kecil
sehingga puzzle menjadi
[1 2   ]
[4 8 3]
[7 6 5]
pindahkan 3 (DOWN)
[1 2 3]
[4 8   ]
[7 6 5]

kembali muncul pilihan
pindahkan 8 (RIGHT) = f(n) = 3
pindahkan 5 (DOWN) = f(n) = 3
karena kedua pilihan memiliki nilai n yang sama maka kita pilih pilihan pertama (LEFT)
[1 2 3]
[4   8]
[7 6 5]

kemungkinan
pindahkan 4 (LEFT) = f(n)= 4
pindahkan 6 (DOWN) = f(n)= 3 (dipilih)
[1 2 3]
[4 6 8]
[7   5]
pindah 5 (LEFT) = f(n)=3 (dipilih)
pindah 7 (RIGHT) = f(n)=3
[1 2 3]
[4 6 8]
[7 5  ]

pindah 8 (UP)
[1 2 3]
[4 6  ]
[7 5 8]

pindah 6 (LEFT)= f(n)= 2. (dipilih)
pindah 3 (UP) = f(n) = 4
[1 2 3]
[4   6]
[7 5 8]

lakukan terus menerus langkah diatas sehingga nanti akan didapat perpindahan 5, dan terakhir perpindahan 8
[1 2 3]
[4 5 6]
[7 8  ] GOAL STATE ^^

selanjutnya
2. TOTAL JARAK.
contoh:

dengan patokan ubin yang kosong, kita dapatkan 3 kemungkinan yang dapat di lakukan. UP,RIGHT,LEFT.

maksud dari penambahan di bawah puzzle tersebut adalah total jarak yang harus di tempuh agar ubin tersusun.
misalnya pada kotak pertama. 1+2+1+1+1 karena
1 (jarak ubin 2 ke posisi aslinya) +
2 (jarak ubin 4 ke posisinya) +
1 (jarak ubin 1 ke posisinya) +
1 (jarak ubin 7 ke posisinya) +
1 (jarak ubin 6 ke posisinya) sehingga total nilai huristiknya = 6

karena UP memiliki nilai heuristik terkecil, kita pilih proses ini.
[243]
[1  5]
[678]
lanjutkan lagi dengan melihat kemungkinan yang dapat terjadi.
di dapat 3 kemungkinan
RIGHT
[243]
[15  ]
[678] 1+2+1+1= 5

LEFT
[243]
[  15]
[678] 1+1+1+2=5

UP
[2  3]
[145]
[678] 1+1+1 = 3 (dipilih)

selanjutnya akan terpilih LEFT
[  23]
[145]
[678] 1+1= 2

lalu DOWN
[123]
[  45]
[678]

dan terakhir RIGHT
[123]
[4  5]
[678] MENCAPAI GOAL STATE




Artikel yang berhubungan




4 comments:

Projo said...

Terima kasih atas artikelnya, sangat membantu sekali

Anonymous said...

Terima kasih saya dpt mengerjakan tugas AI tanpa barus mencari satu persatu menggunakan cara lama dan panjang

Unknown said...

Saya mau tanya, kalau ada 2 heuristik dengan nilai yang sama maka kita harus pilih ubin yang pertama yang ingin dipindahkan, bisa jelaskan lebih detail gk?
Terimakasih

Mita said...

artikelnya sangat membantu, terima kasih.. izin repost ya :)

Post a Comment

Related Posts Plugin for WordPress, Blogger...