Penyelesaian Masalah 8-Puzzle Dengan Menggunakan Metode Greedy

Pada kali ini saya akan mencoba membahas penyelesaian pada permainan 8-Puzzle dengan menggunakan Metode/Algoritma Greedy. Sebelum membahas penyelesaiannya, saya akan sedikit membahas tentang Metode/Algoritma Greedy.

Metode/Algoritma Greedy merupakan jenis algoritma yang digunakan untuk memecahkan persoalan/masalah dengan mencari nilai maksimum ataupun minimum pada setiap langkahnya. Dengan metode Greedy kita bermaksud untuk mencari solusi terbaik dari persoalan/permasalahan tersebut. Pada setiap langkah untuk memecahkan persoalan/permasalahan tersebut akan dipilih keputusan yang paling optimal. Biasanya Algoritma Greedey memberikan solusi yang mendekati nilai optimum dalam waktu yang cukup cepat.

Dalam pembahasan kali ini saya akan mencoba menggunakan dua fungsi heuristik dalam Greedy, yaitu :

• h1(n) : beberapa kotak puzzle yang salah tempat

• h2(n) : jumlah keseluruhan jarak kotak puzzle yang salah menuju ke kotak yang benar atau yang biasa disebut dengan manhattan distance.

• Mengatasi permasalahan 8-Puzzle dengan menggunakan heuristik pertama :

 

Goal Test :

Initial State > Right > Down > Right > Down (Goal State)

• Mengatasi permasalahan 8-Puzzle dengan menggunakan heuristik kedua :

Goal Test :

Initial State > Right > Down > Right > Down (Goal State)

Kesimpulan :

Dari percobaan diatas dengan menggunakan heuristik pertama maupun kedua, keduanya sama saja memiliki goal state yang tepat. Tetapi jika dibandingkan antara heuristik pertama dengan heuristik yang kedua, mungkin dengan menggunakan heuristik yang kedua bisa lebih efisien dikarenakan telah mengetahui seberapa banyak kesalahan yang dimiliki oleh kotak-kotak dari 8-Puzzle tersebut, dengan mengetahui kesalahan tersebut kita dapat meminimalisir kesalahannya agar dapat menyelesaikan masalah tersebut dengan lebih cepat.

Referensi :

• http://bloglogika.blogspot.co.id/2010/12/metode-greedy.html
• https://bertzzie.com/knowledge/analisis-algoritma/Greedy.html
• http://stephanusar.blogspot.co.id/2012/11/pengertian-metode-greedy-dan-algoritma.html

Post ini merupakan tugas-3 yang dibuat untuk memenuhi tugas mata kuliah Pengantar Kecerdasan Tiruan (AI) yang diampu oleh Mia Kamayani ST,MT