Memecahkan Suatu Masalah Dengan Menggunakan Graph Plan

Permasalahan pertama : Shopping

Langkah Penyelesaian : 

1. Buat Initial State dan Goal State, dan hubungkan dengan aksi yang memiliki efek sebagai goal state

2. Masukkan aksi yang lain untuk mendapatkan goal state

3. Inisialisasi aksi dari GO (HDW) dengan diinisial x1=home, dan inisialisasi aksi dari GO (SM) dengan inisial x2=home

4. Dapat kita ketahui GO (SM) tidak dapat tersambung dengan At (Home) dikarenakan sudah dimiliki oleh At(X1) dan juga berlaku untuk GO (HDW).

5. Solusi yang dapat kita ambil yaitu dengan menempatkan GO (SM) setelah Buy (Drill) dengan diberikan garis merah putus-putus sebagai tanda bahwa hal itu terjadi

6. Setelah kita berada di GO (SM) kita bisa melanjutkannya dengan Buy (Milk) dan Buy (Bananas) dan berakhir di At(Home)

Permasalahan Kedua : Birthday Dinner

Langkah Penyelesaian :

1. Letakkan Initial State

2. Hubungkan aksi dengan Initial State

3. Masukkan hasil dari aksi yang dapat dilakukan

4. Karena adanya gangguan pada suatu aksi yang meniadakan precondition dari aksi lain, dan akan menghasilkan 

5. Kita akan mendapatkan not Garbage dengan action Dolly, dan Dinner dengan aksi Cook, serta Present dengan aksi Wrap, tetapi Doly dan Wrap Mutex

6. Dikarenakan tidak ada cara lain untuk mendapatkan goal kita akan menggunakan depth two plan, yaitu dengan menambahkan dua level lagi pada Graph, pada tahap ini kita akan mendapatkan mutex sama seperti di level yang sebelumnya. Tetapi terdapat perbedaan yaitu pada kevek ini Dinner tidak mutex dengan Carry, karena kita bisa mendapatkan Dinner dengan membiarkannya dan tetap bisa melakukan Carry. Begitu juga dengan Present tidak mutex dengan Dolly karena kita bisa mendapatkan Present dengan membiarkannya dan dapat tetap melalukan Dolly.

7. Setelah kita selesai dengan mutex kita mencari lagi dengan cara seperti gambar diatas dan akhirnya dapat berhasil dengan cara seperti yang ditunjukan oleh gambar diatas.

Referensi :

- Lecture11FinalPart1.pdf

- Lecture12FinalPart1.pdf

Penyelesaian Teka Teki Silang dengan CSP (Constraint Satisfaction Problem) menggunakan Algoritma Backtracking

          Pada kali ini kita akan mencoba menyelesaikan Teka Teki Silang dengan menggunakan Algoritma Backtracking. Algoritma Backtracking adalah algoritma yang berbasis pada DFS (Depth First Search) untuk mencari solusi persoalan secara lebih efisien, merupakan perbaikan dari algoritma  brute-force, secara sistematis mencari solusi persoalan diantara semua kemungkinan solusi yang ada. Dengan Algoritma Backtracking kita tidak perlu memeriksa semua kemingkinan solusi yang ada. Hanya pencarian yang mengarah ke solusi saja yang perlu dipertimbangkan. Akibatnya, waktu pencarian dapat dihemat.

Untuk menyelesaika masalah teka teki silang yaitu dengan cara di kaitkan dari kalimat pada teka-teki silang dengan jawaban yang cocok. Pada teka-teki silang telah di sediakan pilihan kata jawabanya.

Mendatar                                        Menurun

1. Cukai                                                               1. Alat Transportasi Umum

3. Tidak Benar                                                     2. Memperbolehkan (B.Ing)

5. Pramuria                                                          3. Jenis Kertas

Pilihan kata : BEA, WTS, ALLOW, SALAH, HVS, BUS

Lakukan pengelompokan pilihan kata berdasarkan isi kotak (domain). Sel merupakan bayaknya node/kotak yang akan di isi.

Pada Kotak TTS diketahui bahwa Syarat :

Huruf ke-1 kotak 1 mendatar= huruf ke-1 kotak 1 Menurun

Huruf ke-3 kotak 1 mendatar= huruf ke-1 kotak 2 Menurun

Huruf ke-3 kotak 1 menurun = huruf ke-1 kotak 3 Mendatar

Huruf ke-3 kotak 1 mendatar= huruf ke-1 kotak 2 Menurun

Huruf ke-5 kotak 2 mendatar= huruf ke-1 kotak 5 Medatar

Huruf ke-5 kotak 3 mendatar= huruf ke-1 kotak 4 Menurun

Huruf ke-3 kotak 5 mendatar= huruf ke-3 kotak 4 Menurun

TTS akan Diselesaikan dengan Backtracking. Urutan pada memasukan kata adalah : 

1 Datar, 1 Turun, 3 Datar, 2 Turun, 4 Turun, 5 Datar

Constraint Satisfaction Problem terdiri dari 3 komponen:

• Set Variabel = Kotak kosong
• Set Domain = Pertanyaan dan kata-kata yang disediakan
• Set Constraint/Batasan = Salah satu huruf pada kata-kata menurun/mendatar harus sesuai dengan salah satu huruf pada kata-kata menurun/mendatar lainnya

Definisi Problem 4 Items :

1. Initial State : 
   
2. Successor Fungtion : Kata-kata yang diisi dari mulai nomor 1 mendatar/menurun, nomor 2, nomor 3 dan seterusnya hingga semua kotak terisi penuh dengan huruf yang menjadi sebuah kata.
3. Path Cost : Menurut berapa banyak kotak yang tersedia pada Teka Teki Silang tersebut.
4. Goal State : 
   

Sumber Referensi :

https://www.academia.edu/19767265/Penggunaan_Algoritma_Backtracking_pada_Penyelesaian_Teka-Teki_Silang

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