Artificial Intelligence (AI)

Tugas ke-5 dibawah ini dibuat untuk memenuhi tugas mata kuliah Pengantar Kecerdasan Tiruan ( AI ) yang diampu oleh Mia Kamayani ST,MT.

PARTIAL ORDER PLANNING

(POP)

            Partial Order Planning (POP) adalah sebuah pendekatan untuk perencanaan otomatis yang meninggalkan keputusan tentang pemesanan tindakan seterbuka mungkin.Ini kontras dengan perencanaan keseluruhan-order , yang menghasilkan urutan yang tepat dari tindakan.

1)   SHOPPING

STEP 1

Step awal memperlihatkan Initial State dan kondisinya 

STEP 2

Step 2 memperlihatkan bahwa initial state akan menuju ke goal state dengan memperlihatkan kondisinya masing-masing. 

STEP 3

Pada step 3 pertama-tama kita akan pergi ke Hardware Store dengan “Precondition and Effect” nya. 

STEP 4

Pada step 4 memperlihatkan setelah pergi ke Hardware Store maka kita kan membeli Drill serta memperlihatkan precondition nya dan effect nya 

STEP 5

Pada step 5 terjadi Clobber karena Precondition dan Effect nya sama pada bagian At(Home) dan ~At(Home) warna biru dan warna hijau maka dari itu Precondition At(Home)  dan Effect ~At(Home) warna hijau akan diganti pada step selanjutnya, dalam pemikiran saya sendiri kondisi tersebut tidak mungkin terjadi karena kita tidak bisa berada didua tempat secara bersamaan maka dari itu kita akan memilih kemana kita akan pergi terlebih dahulu. 

STEP 6

Pada step 6 garis putus-putus menunjukkan bahwa kita akan pergi untuk membeli Drill terlebih dahulu sebelum pergi ke SuperMarket. 

STEP 7

Pada step 7 selanjutkan kita membeli Milk dengan Precondition and Effect nya. 

STEP 8

Step 8 kita langsung menuju untuk membeli Banana karena tempat yang dituju sama seperti membeli Milk, Banana juga memperlihatkan precondition and effect nya 

Step 9

Step 9 merupakan step akhir yaitu dimana setelah kita membeli Milk atau Banana kita bisa langsung kembali menuju rumah dengan Precondition and Effect nya dengan At(x) merupakan dimana tempat kita sebelum kerumah. 

GRAPH PLAN

            Graph Plan adalah adalah algoritma untuk perencanaan otomatis yang dikembangkan oleh Avrim Blum dan Merrick Furst pada tahun 1995. Graphplan mengambil sebagai masukan masalah perencanaan dinyatakan dalam strip dan menghasilkan, jika salah satu kemungkinan, urutan operasi untuk mencapai keadaan tujuan.

1)   Birthday Dinner

STEP 1

Step 1 memberikan gambar initial and goal state

STEP 2

Step 2 memberikan gambaran untuk setiap kondisi

STEP 3

Mari kita membuat Graph Plan. Kita mulai dengan menempatkan dalam kondisi awal.

STEP 4

Mengingat kondisi  awal, semua ke empat dari tindakan kita mungkin bisa dijalankan pada langkah pertama, jadi kami menambahkannya ke Graph.

STEP 5

Sekarang kita tambahkan semua proposisi lama kita ke lapisan berikutnya, serta semua proposisi yang bisa menjadi efek dari tindakan. Dan kita menarik dalam

tindakan perawatan, juga.

STEP 6

Jadi pertama-tama, mari kita coba untuk mengajukan pertanyaan, bisa dibayangkan tujuan menjadi kenyataan? Kami Tujuannya adalah! sampah dan makan malam dan sekarang. Layer 2 berisi! Sampah dan makan malam dan sekarang. Sehingga terlihat seperti ini mungkin bisa menjadi kenyataan. Mereka tidak jelas tidak konsisten

STEP 7

Jadi, kita akan mulai mencari rencana dengan menemukan cara untuk membuat tidak sampah benar.

STEP 8

Kami akan mencoba menggunakan carry tindakan.

STEP 9

Sekarang, kita akan mencoba untuk membuat makan malam yang benar-satunya cara kita bisa, dengan tindakan masak.

STEP 10

Membeli memasak dan membawa yang mutex, jadi ini tidak akan bekerja.

STEP 11

Karena tidak ada cara lain untuk membuat makan malam, kita gagal, dan harus mencoba cara yang berbeda untuk membuat tidak sampah benar. Kali ini, kami akan mencoba dolly.

STEP 12

Sekarang, kita bisa memasak makan malam, dan kami tidak memiliki masalah mutex dengan dolly.

STEP 13

Kita harus membuat ini benar juga. Satu-satunya cara untuk melakukannya adalah dengan bungkus, tapi bungkus adalah mutex dengan dolly. Jadi, kami benar-benar gagal. Tanda.

STEP 14

Tidak ada cara untuk mencapai semua tujuan ini secara paralel. Jadi kita harus mempertimbangkan kedalaman dua rencana. Kita mulai dengan menambahkan lapisan lain untuk grafik rencana.

STEP 15

Sekarang kita harus yakin bahwa kita dapat memenuhi semua prasyarat tersebut di tingkat 0. Kami sub tujuan sekarang adalah sampah, bersih, dan bungkus. Mereka semua benar pada tingkat 0, jadi kita dilakukan! Ada sebenarnya banyak rencana yang akan bekerja, tapi di sini satu dari mereka. Jika kita akan melakukan tindakan dalam rangka, rencana ini akan memungkinkan kita untuk melakukan cook kemudian bungkus kemudian membawa, atau masak kemudian dibawa, lalu bungkus. Yang paling penting adalah bahwa hal itu memaksa kita untuk melakukan memasak sebelum carry, yang kita tidak bisa menegakkan di kedalaman 1 rencana.

DILARANG COPY-PASTE TANPA IZIN YA GUYS, HARGAI PEMBUAT BLOG ^^,

SUMBER :

https://www.youtube.com/watch?v=kyCibTQQQBE

https://en.wikipedia.org/wiki/Partial-order_planning
https://en.wikipedia.org/wiki/Graphplan

https://docs.google.com/viewer?a=v&pid=sites&srcid=cGFydWx1bml2ZXJzaXR5LmFjLmlufGFpXzhfaXRfMjAxNS0xNnxneDo1MGFmNzM1NmZhMDM0NDQ0

Artificial Intelligence (AI)

Tugas ke-4 dibawah ini dibuat untuk memenuhi tugas mata kuliah Pengantar Kecerdasan Tiruan ( AI ) yang diampu oleh Mia Kamayani ST,MT.

 “ SUDOKU dengan BACKTRACKING ”

SUDOKU

            Sudoku adalah permainan teka-teki angka yang terdiri dari 81 kotak (9 x 9) yang berisi angka-angka antara 1 sampai 9 yang harus diisi penuh pada setiap kotaknya. Tujuan permainan ini adalah refreshing dengan mengasah otak. Pemain sudoku diharuskan untuk mengisi semua kotak kosong yang tersedia sedemikian setiap angkanya akan unik pada baris, kolom, dan daerahnya (akan dijelaskan). Contoh sudoku dapat dilihat pada gambar 1. Saat pertama memainkan sudoku, beberapa kotak sudah diisi angka yang merupakan hints untuk mengisi kotak kosong lain hingga penuh. Pada gambar di bawah, dapat kita lihat bahwa adanya perbedaan tebal garis kotak. Garis tebal kotak menandakan batas daerah unik yang harus diisi angka yang unik dari 1-9. Daerah unik terdiri dari 9 kotak (3x3). Sebagai contoh, Daerah unik pada posisi terkiri-teratas terdiri dari angka 5,3,6,9, dan 8, untuk itu 4 kotak kosong lain harus diisi dengan angka unik selain angka sudah ada pada daerah itu yaitu 1,2,4, dan 7. Setiap angka yang diisi pada suatu kotak harus unik secara horizontal, vertikal, dan daerahnya. Kita harus mencari semua nilai yang unik pada setiap kotak dengan strategi tertentu sehingga semua kotak kosong terisi oleh angka.

Hasil penyelesaian kasus sudoku pada gambar 1 ini dapat dilihat pada gambar 2 di bawah ini. Angka yang berwarna merah adalah angka yang kita isikan pada kotak kosong sudoku. Semua angka pada kotak sudoku memiliki nilai yang unik pada baris, kolom, dan daerahnya. Dengan demikian sudoku telah berhasil terselesaikan.

ALGORITMA DFS DAN BACKTRACKING

            Pencarian solusi Algoritma DFS menggunakan pendekatan pencarian solusi penelusuran solusi pohon dinamis. Pada umumnya struktur pohon yang digunakan adalah pohon berakar. Pencarian Solusi dilakukan dengan mengunjungi semua simpul pada pohon. Setiap simpul diperiksa untuk memastikan apakah solusi telah dicapai. Pohon dibentuk dengan dinamis selama solusi berlangsung. Bila sebuah simpul yang dibentuk tidak mengarah ke solusi, maka pencarian solusi dilanjutkan dengan membentuk simpul berikutnya. Teknik penelesuruan simpul yang digunakan pada algoritma DFS adalah penelesuran “Mendalam”. Pencarian solusi dengan DFS dicirikan dengan ekpansi simpul-simpul terdalam lebih dahulu. Mula-mula simpul akar dibangkitkan pertama kali, kemudian sebuah simpul pada aras kedua, lalu sebuah simpul di aras ketiga, dan seterusnya. Jadi, pencarian mengikuti sebuah lintasan tunggal mulai dari simpul akar terus menurun ke “Bawah” ke simpul-simpul pada aras di bawahnya. Sebagai contoh dapat dilihat pada gambar 3. Urutan penelesuran simpul dapat dilihat pada angka yang muncul pada simpul tersebut. Definisi Kedalaman (deept) atau tinggi (heigth) pohon berakar berdasarkan bahwa kedalaman simpul akar adalah 0 dan kedalaman simpul lainnya adalah 1 + kedalaman simpul orang tuanya. Model Pencarian solusi dengan melakukan penelesuran pada struktur pohon ada juga yang dilakukan dengan cara “Melebar” yang biasa disebut Algoritma BFS. Namun, Algoritma tersebut memiliki kelemahan yaitu lamanya waktu yang dibutuhkan untuk menuju simpul solusi. Untuk itu penulis lebih prefer untuk menggunakan algoritma pencarian solusi dengan DFS saja.

Penelusuran semua simpul pada DFS jika dituliskan dengan bahasa pseudocode adalah sebagai berikut :

Procedure DFS (input V : integer) {mengunjungi seluruh simpul graf dengan algoritma pencarian DFS Masukan : V adalah simpul awal kunjungan keluaran : Semua simpul yang dikunjungi ditulis layar } Deklarasi w : integer Algoritma write(v) dikunjungi[v] <- true for tiap simpul w yang bertetangga dengan simpul V do if not dikunjungi[w] then DFS(w) endif endfor

Pencarian solusi dengan metode DFS dilakukan dengan prosedur atau langkah-langkah sebagai berikut (Secara umum) :

1) Masukan simpul akar ke dalam antrian Q. Jika simpul akar adalah simpul tujuan (goal node), maka solusi telah ditemukan. Stop.

2) Jika Q kosong, tidak ada solusi. Stop

3) Ambil simpul v dari kepala (head) antrian. Jika kedalaman simpul v sama dengan batas kedalaman maksimum, kembali ke langkah 2.

4) Bangkitkan semua anak dari simpul v. Jika v tidak mempunyai anak lagi, kembali ke langkah 2. Tempatkan semua anak dari v di awal antrian Q.

5) Jika anak dari simpul v adalah simpul tujuan, berarti solusi telah ditemukan, kalau tidak, kembali lagi ke langkah 3.

            Pada dasarnya penerapan pohon DFS dengan backtracking hanya memerlukan sedikit modifikasi saat terjadi deadend pada simpul. Jika simpul v tidak dapat menciptakan simpul baru namun simpul v tersebut bukan merupakan solusi dari persoalaan, maka simpul v dikatakan mencapai kondisi deadend. Simpul v akan melakukan runut balik pada orang tua simpul v terdekatnya untuk menciptakan simpul baru w yang setara kedalamannya dengan simpul v. Simpul w akan bangkitkan semua anaknya untuk melakukan penelusuran solusi.

ALGORITMA untuk penerapan SUDOKU dengan BACKTRACKING

            Program C++ ini menunjukkan Soal Sudoku menggunakan Backtracking.

Berikut adalah kode sumber C ++ Program untuk memecahkan Sudoku Masalah menggunakan backtracking. C ++ program berhasil dikompilasi dan dijalankan pada sistem Linux. Program output juga ditunjukkan di bawah ini.

/* * C++ Program to Solve Sudoku Problem using BackTracking */ #include <iostream> #include <cstdio> #include <cstring> #include <cstdlib> using namespace std; #define UNASSIGNED 0 #define N 9 bool FindUnassignedLocation(int grid[N][N], int &row, int &col); bool isSafe(int grid[N][N], int row, int col, int num); /* assign values to all unassigned locations for Sudoku solution   */ bool SolveSudoku(int grid[N][N]) {     int row, col;     if (!FindUnassignedLocation(grid, row, col))        return true;     for (int num = 1; num <= 9; num++)     {         if (isSafe(grid, row, col, num))         {             grid[row][col] = num;             if (SolveSudoku(grid))                 return true;             grid[row][col] = UNASSIGNED;         }     }     return false; } /* Searches the grid to find an entry that is still unassigned. */ bool FindUnassignedLocation(int grid[N][N], int &row, int &col) {     for (row = 0; row < N; row++)         for (col = 0; col < N; col++)             if (grid[row][col] == UNASSIGNED)                 return true;     return false; } /* Returns whether any assigned entry n the specified row matches    the given number. */ bool UsedInRow(int grid[N][N], int row, int num) {     for (int col = 0; col < N; col++)         if (grid[row][col] == num)             return true;     return false; } /* Returns whether any assigned entry in the specified column matches    the given number. */ bool UsedInCol(int grid[N][N], int col, int num) {     for (int row = 0; row < N; row++)         if (grid[row][col] == num)             return true;     return false; } /* Returns whether any assigned entry within the specified 3x3 box matches    the given number. */ bool UsedInBox(int grid[N][N], int boxStartRow, int boxStartCol, int num) {     for (int row = 0; row < 3; row++)         for (int col = 0; col < 3; col++)             if (grid[row+boxStartRow][col+boxStartCol] == num)                 return true;     return false; } /* Returns whether it will be legal to assign num to the given row,col location.  */ bool isSafe(int grid[N][N], int row, int col, int num) {     return !UsedInRow(grid, row, num) && !UsedInCol(grid, col, num) &&            !UsedInBox(grid, row - row % 3 , col - col % 3, num); } /* print grid  */ void printGrid(int grid[N][N]) {     for (int row = 0; row < N; row++)     {         for (int col = 0; col < N; col++)             cout<<grid[row][col]<<"  ";         cout<<endl;     } } /* Main */ int main() {     int grid[N][N] = {{3, 0, 6, 5, 0, 8, 4, 0, 0},                       {5, 2, 0, 0, 0, 0, 0, 0, 0},                       {0, 8, 7, 0, 0, 0, 0, 3, 1},                       {0, 0, 3, 0, 1, 0, 0, 8, 0},                       {9, 0, 0, 8, 6, 3, 0, 0, 5},                       {0, 5, 0, 0, 9, 0, 6, 0, 0},                       {1, 3, 0, 0, 0, 0, 2, 5, 0},                       {0, 0, 0, 0, 0, 0, 0, 7, 4},                       {0, 0, 5, 2, 0, 6, 3, 0, 0}};     if (SolveSudoku(grid) == true)           printGrid(grid);     else         cout<<"No solution exists"<<endl;     return 0; }

Constraint Satisfaction Problem terdiri dari 3 komponen:

o   Set variabel = Kotak yang sudah diisi angka yang merupakan hints untuk mengisi kotak kosong lain hingga penuh.

o   Set domain = Angka-angka berwarna merah.

o   Set constraint/batasan = Semua angka pada kotak Sudoku harus memiliki nilai yang unik pada baris, kolom, dan daerahnya. Dengan demikian sudoku telah berhasil terselesaikan.

Definisi problem 4 items :

1.  Initial State :

2. Successor Function : angka yang diisi dari baris teratas lalu diisi dari kiri ke kanan kemudian berpindah baris lagi sampai semua kotak kosong terisi angka unik.

3.Path cost : menurut ( baris, kolom ) dalam suatu kumpulan kotak pada Sudoku.

4. Goal State :

SUMBER :

https://www.academia.edu/8481107/Artificial_Intelegence_Dalam_Sudoku

http://www.sanfoundry.com/cpp-program-solve-sudoku-problem-backtracking/