Penyelesaian 8-Puzzle dengan Greedy
8-Puzzle adalah representasi permainan teka-teki yang dapat diselesaikan dengan mengurutkan atau menyusun komponen-komponen pembentuknya sesuai dengan kondisi yang diinginkan. Komponen pada 8-Puzzle adalah berupa kotak-kotak bernomor atau bergambar (sesuai kebutuhan) yang dapat diacak sedemikian hingga menjadi suatu pola random yang dapat dicari jalan penyelesaiannya. Sesuai namanya, 8-Puzzle terdiri atas 8 kotak dan 1 tempat kosong yang dapat digerakkan dengan aturan tertentu. Aturan pergerakannya hanya berupa empat (4) arah pergerakan, yaitu: atas, bawah, kanan, dan kiri. Serta terlimitasi oleh ukuran dimensi papan yang ditempatinya. Pada 8-Puzzle, batasannya adalah ukuran 3×3. Sehingga, 8 kotak yang dimiliki hanya dapat bergerak dalam lingkup ukuran tersebut.
Pada pembahasan kali ini, saya ingin menyelesaikan puzzle ini dengan suatu algoritma, yaitu Algoritma Greedy, dengan menggunakan dua fungsi heuristik. Algoritma Greedy merupakan algoritma yang sederhana dan lempeng (straightforward). Secara harafiah greedy artinya rakus atau tamak.
Algoritma Greedy membentuk solusi langkah per langkah. Terdapat banyak pilihan yang perlu dieksplorasi pada setiap langkah solusi. Oleh karena itu, pada setiap langkah harus dibuat keputusan yang terbaik dalam menentukan pilihan.
Dalam bahasan ini, fungsi heuristik yang akan kita tampilkan yaitu adalah sebagai berikut.
1. h1(n) = jumlah dari tile yang salah tempat
2. h2(n) = total jarak Manhattan (jumlah tile dari lokasi yang seharusnya untuk setiap tile)
Solusi yang pertama saya menggunakan cara heurestik yang nomor 1 :
Pada pembahasan kali ini, saya ingin menyelesaikan puzzle ini dengan suatu algoritma, yaitu Algoritma Greedy, dengan menggunakan dua fungsi heuristik. Algoritma Greedy merupakan algoritma yang sederhana dan lempeng (straightforward). Secara harafiah greedy artinya rakus atau tamak.
Algoritma Greedy membentuk solusi langkah per langkah. Terdapat banyak pilihan yang perlu dieksplorasi pada setiap langkah solusi. Oleh karena itu, pada setiap langkah harus dibuat keputusan yang terbaik dalam menentukan pilihan.
Dalam bahasan ini, fungsi heuristik yang akan kita tampilkan yaitu adalah sebagai berikut.
1. h1(n) = jumlah dari tile yang salah tempat
2. h2(n) = total jarak Manhattan (jumlah tile dari lokasi yang seharusnya untuk setiap tile)
Solusi yang pertama saya menggunakan cara heurestik yang nomor 1 :
Priority queue :
1. F(0)=4
2. F(0)=4 F(1)=5 F(2)=3 F(3)=4
3. F(2)=3 F(3)=4 F(1)=5
4. F(2)=3 F(3)=4 F(1)=5 F(4)=4
5. F(4)=4 F(3)=4 F(1)=5
6. F(4)=4 F(3)=4 F(1)=5 F(5)=5 F(6)=4
7. F(6)=4 F(3)=4 F(1)=5 F(5)=5
8. F(6)=4 F(3)=4 F(1)=5 F(5)=5 F(7)=4 F(8)=5 F(9)=2
9. F(9)=2 F(3)=4 F(1)=5 F(5)=5 F(7)=4 F(8)=5
10. F(9)=2 F(3)=4 F(1)=5 F(5)=5 F(7)=4 F(8)=5 F(10)=3 F(11)=0
11. F(11)=0 F(3)=4 F(1)=5 F(5)=5 F(7)=4 F(8)=5 F(10)=3
12. F(11)=0 F(3)=4 F(1)=5 F(5)=5 F(7)=4 F(8)=5 F(10)=3
13. F(0) --> F(2) --> F(4) --> F(6) --> F(11)
1. F(0)=4
2. F(0)=4 F(1)=5 F(2)=3 F(3)=4
3. F(2)=3 F(3)=4 F(1)=5
4. F(2)=3 F(3)=4 F(1)=5 F(4)=4
5. F(4)=4 F(3)=4 F(1)=5
6. F(4)=4 F(3)=4 F(1)=5 F(5)=5 F(6)=4
7. F(6)=4 F(3)=4 F(1)=5 F(5)=5
8. F(6)=4 F(3)=4 F(1)=5 F(5)=5 F(7)=4 F(8)=5 F(9)=2
9. F(9)=2 F(3)=4 F(1)=5 F(5)=5 F(7)=4 F(8)=5
10. F(9)=2 F(3)=4 F(1)=5 F(5)=5 F(7)=4 F(8)=5 F(10)=3 F(11)=0
11. F(11)=0 F(3)=4 F(1)=5 F(5)=5 F(7)=4 F(8)=5 F(10)=3
12. F(11)=0 F(3)=4 F(1)=5 F(5)=5 F(7)=4 F(8)=5 F(10)=3
13. F(0) --> F(2) --> F(4) --> F(6) --> F(11)
Solusi yang Kedua saya memakai heurestik yang nomor 2 :
1. F(0)=5
2. F(0)=5 F(1)=6 F(2)=6 F(3)=4
3. F(2)=6 F(3)=4 F(1)=6
4. F(2)=6 F(3)=4 F(1)=6 F(4)=3
5. F(4)=3 F(3)=4 F(1)=6
6. F(4)=3 F(3)=4 F(1)=6 F(5)=4 F(6)=2
7. F(6)=2 F(3)=4 F(1)=6 F(5)=4
8. F(6)=2 F(3)=4 F(1)=6 F(5)=4 F(7)=3 F(8)=3 F(9)=1
9. F(9)=1 F(3)=4 F(1)=6 F(5)=4 F(7)=3 F(8)=3
10. F(9)=2 F(3)=4 F(1)=6 F(5)=4 F(7)=3 F(8)=3 F(10)=2 F(11)=0
11. F(11)=0 F(3)=4 F(1)=6 F(5)=4 F(7)=3 F(8)=3 F(10)=2
12. F(11)=0 F(3)=4 F(1)=6 F(5)=4 F(7)=3 F(8)=3 F(10)=2
13. F(0) --> F(2) --> F(4) --> F(6) --> F(11)
Kesimpulan :
Lebih baik menggunakan solusi yang kedua yaitu menggunakan total jarak manhattan karena lebih terlihat jalan keluar nya daripada menggunakan solusi yang pertama yang agak mudah sekali terjadi perulangan.
Referensi :
https://andiktaufiq.wordpress.com/2010/05/02/8-puzzle-problem-bagian-2/
http://informatika.stei.itb.ac.id/~rinaldi.munir/Stmik/2010-2011/Makalah2010/MakalahStima2010-011.pdf.
http://kuliahkusayang.blogspot.co.id/2010/04/8-puzzle-problem-ai.html
0 Komentar