eight puzzle kotak 8 - final
TRANSCRIPT
Anthon R Tampubolon (23510311)I Putu Agus Eka Pratama (23510310)
I Made Andhika (23510307)Eko Budi Setiawan (23511032)
M. Tirta Mulia (23511037)
Eight Puzzle – Kotak 8
Puzzle-8 adalah permainan menyusun kotak-kotak berlabel dari keadaan awal (initial state) yang acak menjadi tersusun dalam suatu format tertentu (goal
state). Permainan ini terdiri dari 3 baris dan 3 kolom (9 kotak), 8 kotak berlabel dan 1 kotak kosong.
Pernyusunan kotak dilakukan dengan mengeser kotak-kotak berlabel satu per satu ke arah kotak kosong
secara vertikal atau horizontal
Permainan Kotak 8
2 8 3 4 5 6 7 1 0
1 2 3 4 5 6 7 8 0Til
eState
Faktadeskripsi tentang objek yang menjadi
perhatian Kaidah
aturan yang bila diterapkan pada suatu keadaan (state) menghasilkan keadaan yang baru Inferensi
untaian dari kaidah untuk bergerak dari keadaan awal (initial states) menuju keadaan sasaran (goal states)
Komponen AI
Penerapan AI dalam Permasalahan Kotak 8
FAKTA Initial State, Current State, dan Goal State
Penerapan dalan Program
get_new_data merupakan prosedur untuk pengambilan data dari database
Penerapan AI dalam Permasalahan Kotak 8
Rules Kanan, Kiri, Atas, dan BawahMetode yang digunakan adalah metode switch
2 8 3 4 5 6 7 1 0 2 8 3 0 5 6 7 1 4
Penerapan AI dalam Permasalahan Kotak 8
Inferensi
Depth First Search dan Breadth First SearchSistematis Search
Heuristic SearchMisMatch dan Manhattan Distance
Sistematis Search dan Heuristic Search
Depth First Search
Prosedur
Simpul yang lebih dalam diperiksa terlebih dahulu
Penelusuran simpul-simpul pada suatu cabang sampai
kedalaman yang ditentukan.
1. Berikan simpul awal pada daftar open
2. Loop: if open = kosong then exit (fail)
Depth First SearchSimpul yang lebih dalam diperiksa terlebih dahulu
Penelusuran simpul-simpul pada suatu cabang sampai
kedalaman yang ditentukan.3. n : = first (open)
Depth First SearchSimpul yang lebih dalam diperiksa terlebih dahulu
Penelusuran simpul-simpul pada suatu cabang sampai
kedalaman yang ditentukan.
5. Remove (n, open)
Melabelkan “Closed” pada Current State
4. if goal (n) then exit (success)
6. Ekspansikan n, berikan semua simpul anak pada kepala open dan bubuhkan pointer dari simpul anak ke n
Depth First SearchSimpul yang lebih dalam diperiksa terlebih dahulu
Penelusuran simpul-simpul pada suatu cabang sampai
kedalaman yang ditentukan.
If Depth <= Val(Text7.Text) Then Menyatakan Batasan Kedalaman yang harus di telusuri
7. Kembali ke Loop
Depth First SearchSimpul yang lebih dalam diperiksa terlebih dahulu
Penelusuran simpul-simpul pada suatu cabang sampai
kedalaman yang ditentukan.Prosedur AddOpenList()
• Nilai = Nilai Prioritas yang digunakan untuk memeringkatkan Kanan, Kiri, Atas dan Bawah
• Secara Default, Nilai = 0
Testing Program DFS
B A Ka Ki
Ki Ka Jumlah Langkah Solusi
Jumlah Iterasi
Jumlah State yang dibangkitkan
Batas Kedalaman 6
4 Step
41 Step
45 State
Route : Atas, Kiri, Bawah, Kanan
Breadth First SearchEvaluasi dilakukan terhadap simpul-simpul pada suatu level
sebelum dilanjutkan pada level berikutnya
Prosedur
1. Berikan simpul awal pada daftar open
2. Loop: if open = kosong then exit (fail)
Breadth First SearchEvaluasi dilakukan terhadap simpul-simpul pada suatu level
sebelum dilanjutkan pada level berikutnya
3. n : = first (open)
get_new_data merupakan prosedur untuk pengambilan data dari database
Breadth First SearchEvaluasi dilakukan terhadap simpul-simpul pada suatu level
sebelum dilanjutkan pada level berikutnya
4. if goal (n) then exit (success)
5. Remove (n, open)
Melabelkan “Closed” pada Current State
Breadth First SearchEvaluasi dilakukan terhadap simpul-simpul pada suatu level
sebelum dilanjutkan pada level berikutnya
6. Ekspansikan n. Berikan pada ekor open semua simpul anak yang belum muncul pada open atau closed dan bubuhkan pointer ke n.
If Depth <= Val(Text7.Text) Then Menyatakan Batasan Kedalaman yang harus di telusuri
7. Kembali ke Loop
Prosedur AddOpenList()
• get_new_data3(state) adalah Prosedure untuk mengecek State sudah pernah dibangkitkan melalui Parent State yang lain
Breadth First SearchEvaluasi dilakukan terhadap simpul-simpul pada suatu level
sebelum dilanjutkan pada level berikutnya
Testing Program BFS
B A Ka Ki
Ki Ka Jumlah Langkah Solusi
Jumlah Iterasi
Jumlah State yang dibangkitkan
4 Step
32 Step
60 State
Route : Atas, Kiri, Bawah, Kanan
Best First SearchMisMatch
Pembangkitan simpul anak didasarkan pada hasil perbandingan
nilai heuristik tiap simpul yang dibuka. Simpul dengan nilai
heuristik terkecil akan dibuka terlebih dahulu. Nilai heuristik
diperoleh dari penjumlahan tile yang tidak tepat (mismatch tiles)Prosedur
1. Berikan simpul awal pada daftar open
2. Loop: if open = kosong then exit (fail)
3. n : = first (open)
Best First SearchMisMatch
Pembangkitan simpul anak didasarkan pada hasil perbandingan
nilai heuristik tiap simpul yang dibuka. Simpul dengan nilai
heuristik terkecil akan dibuka terlebih dahulu. Nilai heuristik
diperoleh dari penjumlahan tile yang tidak tepat (mismatch tiles)
4. if goal (n) then exit (success)
5. Remove (n, open)
Melabelkan “Closed” pada Current State
Best First SearchMisMatch
Pembangkitan simpul anak didasarkan pada hasil perbandingan
nilai heuristik tiap simpul yang dibuka. Simpul dengan nilai
heuristik terkecil akan dibuka terlebih dahulu. Nilai heuristik
diperoleh dari penjumlahan tile yang tidak tepat (mismatch tiles)
6. Ekspansikan n, berikan semua simpul anak pada kepala open dan bubuhkan pointer dari simpul anak ke n
7. Kembali ke Loop
Best First SearchMisMatch
Pembangkitan simpul anak didasarkan pada hasil perbandingan
nilai heuristik tiap simpul yang dibuka. Simpul dengan nilai
heuristik terkecil akan dibuka terlebih dahulu. Nilai heuristik
diperoleh dari penjumlahan tile yang tidak tepat (mismatch tiles)
Prosedur AddOpenList()
• get_new_data3(state) adalah Prosedure untuk mengecek State sudah pernah dibangkitkan melalui Parent State yang lain
Best First SearchMisMatch
Nilai Heuristik dijumlahkan setiap ada perbedaanPosisi pada current state dan goal state
Testing Program MisMatch
B5 A4 Ka5Ki4
Jumlah Langkah Solusi
Jumlah Iterasi
Jumlah State yang dibangkitkan
4 Step
4 Step
10 State
Route : Atas, Kiri, Bawah, Kanan
Ka5Ki3
B2
Ka0 B3
Best First SearchManhattan Distance
Manhattan Distance adalah jumlah gerakan minimum yang
diperlukan oleh sebuah kotak angka untuk berpindah ke goal
statenya.
Prosedur
1. Berikan simpul awal pada daftar open
2. Loop: if open = kosong then exit (fail)
3. n : = first (open)
Best First SearchManhattan Distance
Manhattan Distance adalah jumlah gerakan minimum yang
diperlukan oleh sebuah kotak angka untuk berpindah ke goal
statenya.
4. if goal (n) then exit (success)
5. Remove (n, open)
Melabelkan “Closed” pada Current State
Best First SearchManhattan Distance
Manhattan Distance adalah jumlah gerakan minimum yang
diperlukan oleh sebuah kotak angka untuk berpindah ke goal
statenya.
6. Ekspansikan n, berikan semua simpul anak pada kepala open dan bubuhkan pointer dari simpul anak ke n
7. Kembali ke Loop
Best First SearchManhattan Distance
Manhattan Distance adalah jumlah gerakan minimum yang
diperlukan oleh sebuah kotak angka untuk berpindah ke goal
statenya.
Prosedur AddOpenList()
• get_new_data3(state) adalah Prosedure untuk mengecek State sudah pernah dibangkitkan melalui Parent State yang lain
Best First SearchManhattan Distance
Testing Program Manhattan Distance
B6 A4 Ka6Ki4
Jumlah Langkah Solusi
Jumlah Iterasi
Jumlah State yang dibangkitkan
4 Step
4 Step
10 State
Route : Atas, Kiri, Bawah, Kanan
Ka6Ki4
B2
Ka0 B4
Kesimpulan
Keterangan DFS BFS MisMatchManhatta
n
Jumlah Langkah Solusi 4 4 4 4
Jumlah Iterasi 41 32 4 4
Jumlah State yang dibangkitkan
45 60 10 10
2 8 3 4 5 6 7 1 0
1 2 3 4 5 6 7 8 0