8 PUZZLE Informed Search Greddy

8 PUZZLE Metode Greddy

Pada pembahasan kali ini, saya akan menyelesaikan PUZZLE ini dengan Metode Algoritma Greddy dengan menggunakan dua fungsi Heuristic. Algoritma Greddy merupakan Algoritma yang Straighforwad atau sederhana dan lurus.

Permasalahan 8 Puzzle, Start State dan Goal State Seperti gambar dibawah ini.

 

Diketahui 2 jenis Heuristic :

• h1(n) = Jumlah Kotak yang salah tempat.
• h2(n) = Total jarak Manhattan (jumlah kotak dari lokasi yang seharusnya untuk setiap kotak. 

Berikut adalah Pohon State dari 8 Puzzle diatas :

• h1(n) : 
  

Solusi : Initial State > Right > Up > Right > Down > Down > Left > Up > Right > Down (GOAL).

• h2(n) :

 

Solusi : Initial State > Right > Up > Right > Down > Down > Left > Up > Right > Up (GOAL).
 

Kesimpulan :  Dari dua fungsi Heuristic Algoritma Greedy pada 8 Puzzle diatas, kedua fungsi bisa memberikan solusi penyelesaian dari Start State hingga ke Goal State. Tetapi pada penggunaan Heuristic pertama jumlah State yang memiliki Heuristic sama lebih banyak dari Heuristic kedua. Jadi, dari dua solusi penyelesaian diatas fungsi Heuristic yang Kedua lebih optimal.

Referensi : 

• http://whitenote03.blogspot.co.id/2016/10/penyelesaian-game-8-puzzle-menggunakan.html 
• http://kuliahkusayang.blogspot.co.id/2010/04/8-puzzle-problem-ai.html