Penyelesaian 8puzzle Menggunakan Metode 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.

Disini saya akan menjelaskan cara menyelesaikan puzzle tersebut menggunakan Algoritma Greedy, dengan menggunakan 2 heuristik. 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.

·         h₁(n)  : sebagai banyak kotak yang menempati tempat yang salah.

·         h₂(n) : sebagai total keseluruhan jarak tiap kotak yang menempati tempat yang salah terhadap posisi kotak yang benar.

Initial State dan Goal State yang dipakai disini adalah sebagai berikut.

Berikut adalah penyelesaian dari fungsi heuristik yang pertama atau h₁(n)

Dan ini merupakan penyelesaian dari fungsi heuristik kedua atau h₂(n)

Kesimpulan yang dapat diambil dari pembahasan ini adalah penyelesaian yang paling optimal adalah dengan menggunakan fungsi heuristik yang kedua atau h₂(n) dikarenakan pada h₁(n) pemilihan state berikut nya sedikit sulit ini diakibatkan oleh banyak nya heuristik yang sama besar.

Source :

http://whitenote03.blogspot.co.id/2016/10/penyelesaian-game-8-puzzle-menggunakan.html

https://andiktaufiq.wordpress.com/2010/04/16/8-puzzle-problem-bagian-1/