Tugas 3 AI -> 8-puzzle dan greedy

HALLO …

Setelah minggu yang lalu saya membahas tentang Penyelesaian mencari solusi dengan menggunakan DFS, kali ini saya akan membahas mengenai mencari sebuah solusi pada sebuah permasalahan 8 puzzle menggunakan algoritma greedy dengan menggunakan kedua heuristic. Tulisan ini dibuat untuk memenuhi tugas  mata kuliah Pengantar Kecerdasan Tiruan (AI) yang diampu oleh Mia Kamayani ST, MT . Fakultas Teknik, Prodi Teknik Informatika, UHAMKA.->

Penyelesaian 8 puzzle menggunakan algoritma greedy dengan menggunakan kedua heuristic.

Sebelum kita menuju ke sebuah permasalahan pada 8 puzzle, , terlebih dahulu kita perlu tahu apa yang disebut sebagai algoritma greedy dan heuristic itu sendiri.

Apa itu Algoritma Greedy?

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. Keputusan yang telah diambil pada suatu langkah tidak dapat diubah lagi pada langkah selanjutnya. 

Apa itu Heuristic ?

Heuristic dalam konteks yang luas dapat didefinisikan sebagai suatu nilai informasi yang “dianggap” mendekati nilai solusi dari suatu permasalahan. Sebagai contoh, jika kita misalkan ada seseorang yang berada di Bandung hendak menuju Surabaya, lalu orang tersebut ingin mencari rute jalan darat terpendek yang dapat dilalui dari Bandung menuju Surabaya. Maka nilai heuristicnya bisa kita tentukan dari, misal jarak estimasi dari setiap titik keberangkatan menuju Surabaya berdasarkan jarak yang tertulis pada peta. Atau bisa saja nilai heuristicnya didasarkan pada jarak setiap titik keberangkatan terhadap stasiun kereta api terdekat. Yang jelas, nilai heuristic ini dapat sangat relatif berdasar penilaian masing-masing pembuat keputusan. Tapi perlu diingat, nilai heuristic ini digunakan dalam proses evaluasi setiap periode tertentu atau setiap titik evaluasi tertentu. Jadi sebisa mungkin nilai heuristic yang kita tentukan bersifat admissible atau dapat diterima secara semantik, baik karena kedekatannya dengan solusi maupun “masuk akal” dari sisi logika. Jika tidak demikian, maka bisa jadi bahwa proses pencarian yang kita lakukan malah akan menjauhkan kita dari solusi.

Ada 4 operator yang dapat digunakan untuk menggerakkan dari satu keadaan ke keadaan yang baru.:

1. Ubin kosong digeser ke kiri
2. Ubin kosong digeser ke kanan
3. Ubin kosong digeser ke bawah
4. Ubin kosong digeser ke atas

Untuk lebih jelasnya di sini kita akan membahas mengenai menyelesaikan studi kasus permasalahan pada 8 Puzzle dengan metode Informed Search Algoritma Greedy dan Heuristic. 

Berikut Eigth Puzzle yang akan kita cari solusinya dari Initial State hingga Goal State : ->

Pada studi kasus ini kita akan menggunakan dua Heuristic, perlu diingatkan kembali pada Algoritma Greedy fungsi evaluasinya adalah f(n) = h(n)
berikut kedua heuristic yang diketahui untuk menyelesaikan permasalahan ini:
h1(n) = jumlah tile yang salah tempat
h2(n) = total jarak manhattan (jumlah tile dari lokasi yang seharusnya untuk tiap tile)

1.) H1

Penjelasan gambar

h1 adalah berapa jumlah tile yang salah tempat jadi kita menghitung tile yang salah tempat sesuai dengan goal state

Sebelum menuju jawabannya kita pahami dahulu disana terdapat goal state dengan urutan goal statenya yaitu 1,2,3,4,5,6,7,8,x (kosong/tidak di hitung) setelah itu kita liat d initial state nya urutan initial statenya yaitu 1,2,3,4,8,x,7,6,5 (H1(A)) di situ baru kita ketahui berarti terdapat ada 3 tail yang salah tempat yaitu 8,6,5.

 

lalu setelah itu langsung kita jabarkan atau di pecah lagi sesuai dengan gambar dan di pecah dengan memindahkan/menggeserkan angka dari suatu keadaan ke keadaan yang baru dengan memindahkan ke atas,bawah,kanan,atau kiri, kita mulai dari urutan succesor function yaitu  dengan memulai dari angka 5 yang berada di bawah kita pindahkan ke atas (H1(B)) dan ada 1 opsi lagi yaitu memindahkan angka 3 ke bawah (H1C)) nah bila sudah di pindahkan kita baca lagi urutan tile tersebut yang di mana urutan nya adalah H1(B) :1,2,3,4,8,5,7,6,x dan H1(C): 1,2,x,3,4,8,3,7,6,5,

Nah baru kita bandingkan 

H1(B) : hanya 3 tile yang salah tempat sama seperti sebelumnya

H1(C) : menjadi 4 tile yang salah tempat 

Maka kita ambil yang lebih kecil dari sebelumnya terus sampe selesai begitu dan selalu mengikuti aturan succesor function.

2.) H2

Penjelasan Gambar
h2 adalah total jarak tile manhattam ( jumlah lokasi seharusnya untuk setiap tile) jadi di sini hanya menghitung jarak saja

Caranya hampir sama dengan h1, kita liat terlebih dahulu initial state dan goal state sama seperti h1 bedanya kalo h1 adalah jumlah tile salah tempat maka h2 itu adalah total jarak jadi initial state nya h2 adalah 1,2,3,4,8,x(tidak di hitung/kososng),7,6,5 nah sedangkan goal state nya adalah 1,2,3,4,5,6,7,8,x maka kita akan menemui jarak untuk posisi tile seharunya yaitu :

1 = 0 karena sudah sampai di posisi seharusnya
2 = 0 karena sudah sampai di posisi seharusnya

3 = 0 karena sudah sampai di posisi seharusnya

4 = 0 karena sudah sampai di posisi seharusnya
8 = 1 jarak dari posisi seharusnya
7 = 0 karena sudah sampai di posisi seharusnya

6 = 2 jarak dari posisi seharusnya

5 = 2 jarak dari posisi seharusnya

Jadi akan di dapatkan total nya yaitu 5 jarak

Selanjutnya sama seperti h1 kita gerakan puzzle sesuai succesor function nya dan hitung jarak statenya yang telah kita gerakan/pindahkan dan pilih jarak yang terkecil lagi, terus sampe selesai sampai menemui goal state. Perlu diingat bahwa proses evaluasi yang dilakukan akan selalu mengambil nilai heuristic yang paling kecil. Setelah selesai menemui goal state maka kita hitung jumlah jarak dari initial state sampai goal state, jadi pada gambar di atas dapat di ketahui jarak state yaitu :

SOLUSI : A>C>D>F>I>J

 f(B) = g(B) + h(B) = 4 + 3 + 2 + 2 + 0

                              = 11

Maka dapat di dapat jaraknya yaitu dengan jarak 11.

  

KESIMPULAN: Maka dapat di simpulkan pada solusi Permasalahan 8 Puzzle di atas dengan dilihat dan dibandingkan goal state dari kedua heuristic tersebut, maka H1(N) lebih memungkinkan mendapat jalan atau cost yang lebih sedikit dengan Fringe lebih sedikit / kecil pula dan lebih efisien dari pada H2(N).

Refrensi : 1. http://andiktaufiq.wordpress.com/2010/05/02/8-puzzle-problem-bagian-2/

     2. https://courses.cs.washington.edu/courses/cse573/12sp/lectures/03-hsearch.pdf Russell and P. Norvig, Artificial intelligence: a modern approach. 2009.