Tugas ke-3 dibawah ini dibuat untuk
memenuhi tugas mata kuliah Pengantar Kecerdasan Tiruan ( AI ) yang diampu oleh
Mia Kamayani ST,MT.
8 - PUZZLE with
GREEDY
[ Salah Tempat , h1
= (n) ]
Catatan : State yang kita pilih berwarna kotak merah dengan panah merah, sedangkan sisanya state yang tidak dipilih. Jangan lupa perhatikan Goal State diatas untuk memastikan kebenarannya. Angka berwarna merah menandakan angka yang salah tempat dan yang berwarna hitam angka yang letaknya sudah sesuai Goal State diatas.
LANGKAH
– LANGKAHNYA :
BINARY
TREE 8 - PUZZLE with GREEDY diatas :
8 - PUZZLE with
GREEDY
[ Total Jarak
Manhattan , h2 = (n) ]
Catatan : State yang kita pilih berwarna kotak merah dengan panah merah, sedangkan sisanya state yang tidak dipilih. Jangan lupa perhatikan Goal State diatas untuk memastikan kebenarannya.
LANGKAH
– LANGKAHNYA :
BINARY
TREE 8 - PUZZLE with GREEDY diatas :
KESIMPULANNYA
:
8-Puzzle Greedy dengan total jarak
manhattan lebih efisien dibandingkan dengan jumlah angka yang salah tempat.
8-Puzzle Greedy dengan jumlah angka yang salah tempat terlalu banyak membuat
state apabila angkanya jauh dari tempat goal state.
SOAL BONUS
( KNAPSACK PROBLEM with
GREEDY)
DEFINISI
Metode yang
digunakan untuk memecahkan persoalan optimasi dengan pencarian solusi optimum.
Ada 2 macam
persoalan optimasi:
1. Maksimasi
(maximization)
2. Minimasi (minimization)
a) Solusi optimum (terbaik) adalah
solusi yang bernilai minimum atau maksimum
dari sekumpulan alternatif solusi yang mungkin.
b) Prinsip greedy: “take what
you can get now!”
KNAPSACK
PROBLEM
Knapsack problem adalah suatu
masalah bagaimana cara menentukan pemilihan barang dari sekumpulan barang di
mana setiap barang tersebut mempunyai berat dan profit masing masing, sehingga
dari pemilihan barang tersebut didapatkan profit yang maksimum.
Note:
1
menandakan barang dimasukan
0
menandakan barang tidak dimasukan
Contoh
1 :
w1 =
10; p1 = 2
w2 =
5; p2 = 3
w3 =
15; p3 = 5
w4 =
7; p4 = 7
w5 =
6; p5 = 1
w6 =
18; p6 = 4
w7 =
3; p7 = 1
M
= 15
KESIMPULAN
dari gambar diatas :
Pada soal ini, algoritma greedy
dengan strategi pemilihan objek berdasarkan profit memberikan solusi
optimal, sedangkan pemilihan objek berdasarkanweight dan density tidak
memberikan solusi optimal.
Contoh
2 :
w1 =
3; p1 = 9
w2 =
5; p2 = 10
w3 =
4; p3 = 12
w4 =
2; p4 = 4
w5 =
6; p5 = 18
W
max= 16
KESIMPULAN
gambar diatas:
Algoritma greedy tidak
selalu berhasil menemukan solusi optimal untuk masalah 0/1 Knapsack.
SUMBER
:
Tidak ada komentar:
Posting Komentar