Thursday, October 6, 2016

Knapsack Problem

By  1 comment:



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.
Knapsack Problem bisa kita gambarkan, misalnya kita mempunyai sebuah kantong atau tas dengan kapasitas tertentu sedangkan dihadapan kita terdapat begitu banyak pilihan barang, maka kita harus memilih barang mana saja yang kira-kira akan kita angkut sesuai kapasitas kantong yang kita miliki supaya kita bisa mendapatkan keuntungan yang sebesar-besarnya atau maksimal.
Dalam menghadapi masalah di atas, metode Greedy memiliki 3 pilihan strategi pengangkutan, yaitu:
  • Greedy by Profit, strategi ini mengharapkan keuntungan maksimal dengan cara memasukan barang atau objek dengan nilai keuntungan terbesar terlebih dahulu ke dalam kantong atau knapsack. Jadi strategi ini hanya mempertimbangkan jumlah keuntungan dari sekumpulan barang, dengan catatan berat barang yang akan dibawa tidak melebihi kapasitas kantong yang kita miliki.
  • Greedy by weight, pada strategi ini kita berusaha memasukan barang sebanyak-banyaknya kedalam kantong, jadi barang atau objek yang dimasukan terlebih dahulu adalah barang dengan bobot paling ringan terlebih dahulu, dengan harapan dengan banyaknya barang atau objek yang terangkut kita bisa mendapatkan keuntungan sebesar-besarnya.
  • Greedy by density, strategi ini mengharapkan keuntungan sbesar-besarnya dengan memasukan barang  yang memiliki keuntungan per unit terbesar (Pi/Wi) terlebih dahulu kedalam kantong.  

Contoh 1 :

       Seorang pencuri ingin mencuri perhiasan di sebuah toko perhiasan, di toko tersebut perhiasan-perhiasan itu ditempatkan pada 4 buah kotak, setiap kotak perhiasan memiliki bobot perhiasan berbeda-beda(w₁=3, w₂=5, w3=6, w4=10) dan memiliki keuntungan berbeda-beda(p1=15, p2=25, p3=24, p4=50) tetapi pencuri itu hanya membawa sebuah tas yang hanya bisa menampung maksimal (Wmax=20). Bagaimana caranya pencuri itu dalam mengambil perhiasan-perhiasan tersebut dengan mempertimbangkan keuntungan maksimal yang dapat diperoleh.



Properti objek
Greedy by
Solusi
Optimal
i
wi
pi
Pi/wi
profit
weight
density
1
3
15
5
1
1
1
1
2
5
25
5
1
0
1
1
3
6
24
4
0
1
0
0
4
10
50
5
1
1
1
1
Total Bobot
18
19
18
18
Total Keuntungan
90
89
90
90
nb:
->  1 menandakan barang dimasukan
->  0 menandakan barang tidak dimasukan
->  pada bagian "profit" utamakan memasukan jumlah barang agar mendekati keuntungan maksimal
->  pada bagian " weight" utamakan memasukan jumlah barang agar mendekati beban maksimal
-> pada bagian " density" utamakan memasukan jumlah barang agar mendekati harga keuntungan per-unit barang maksimal.

Contoh 2 :

       Seseorang penjual memiliki lima buah tempat sayuran yang isinya memiliki bobot berbeda(w1=2, w2=4, w3=5, w4=3, w5=7) dan harga yang tentunya berbeda pula(p1=12, p2=8, p3=15, p4=12, p5=14). Ia ingin menjual sayuran dengan berbagai macam sayuran berbeda dalam satu buah kantung yang bisa menampung beban maksimal(Wmax=12). Bagaimana penjual itu mengatur nya agar penjual itu bisa mendapat keuntungan maksimal.
Properti objek
Greedy by
Solusi
Optimal
i
wi
pi
Pi/wi
profit
weight
density
1
2
12
6
1
0
1
1
2
4
8
2
0
0
0
0
3
5
15
3
1
1
1
1
4
3
12
4
1
0
1
1
5
7
14
2
0
1
0
0
Total Bobot
10
12
10
10
Total Keuntungan
39
29
39
39
nb:
->  1 menandakan barang dimasukan
->  0 menandakan barang tidak dimasukan
->  pada bagian "profit" utamakan memasukan jumlah barang agar mendekati keuntungan maksimal
->  pada bagian " weight" utamakan memasukan jumlah barang agar mendekati beban maksimal
->  pada bagian " density" utamakan memasukan jumlah barang agar mendekati harga keuntungan           per-unit barang maksimal.


Referensi :


Share:
Read More

Penyelesaian Game 8-Puzzle menggunakan Algoritma Greedy dengan Dua Fungsi Heuristik

By  No comments:


8-Puzzle merupakan salah satu jenis permainan puzzle dimana kita harus mencapai goal puzzle dari initial puzzle yang diberikan. Untuk mencapai goal puzzle, 8-puzzle ini menyediakan satu grid kosong agar grid-grid lain disekitarnya dapat digerakkan. Sebagai contoh Inisial State dan Goal State dari sebuah puzzle adalah :
Pada puzzle berukuran 3x3 ini jika kita mencoba semua kemungkinan pergeserannya, maka akan sangat susah untuk mencapai solusi. Untuk menyederhakan semua state puzzle yang mungkin, kita bisa menggunakan struktur pohon untuk menelusuri semua kemungkinan dari state puzzle ini dengan algoritma-algoritma lain misalnya dengan DFS, BFS, dll.

Pada pembahasan kali ini, saya ingin menyelesaikan puzzle ini dengan suatu algoritma, yaitu Algoritma Greedy, dengan menggunakan dua fungsi heuristik. 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.
Dalam bahasan ini, fungsi heuristik yang akan kita tampilkan yaitu adalah sebagai berikut.
  • h₁(n) : sebagai banyak grid yang menempati tempat yang salah.
  • h₂(n) : sebagai total keseluruhan jarak tiap grid yang menempati tempat yang salah terhadap posisi grid yang benar, atau sering disebut dengan manhattan distance.



Solusi Penyelesaian dengan fungsi Heuristik Pertama yaitu banyak grid yang menempati tempat yang salah

Solusi :
Initial State -> Right -> Up -> Right -> Down -> Down -> Left -> Up -> Right -> Down(Goal)




Solusi Penyelesai dengan fungsi Heuristik Kedua yaitu total keseluruhan jarak tiap grid yang menempati tempat yang salah terhadap posisi grid yang benar, atau sering disebut dengan manhattan distance.

Solusi :
Initial State -> Right -> Up -> Right -> Down -> Down -> Left -> Up -> Right -> Up(Goal)





Kesimpulan
Dari semua yang telah dipaparkan diatas, penggunaan dari dua fungsi heuristik Algoritma Greedy pada solusi penyelesaian 8-puzzle, baik fungsi heuristik pertama dan kedua sama sama mampu memberikan solusi penyelesaian dari awal state sampai ke goal state. Tetapi menurut pendapat saya, pada penggunaan fungsi heuristik pertama jumlah State puzzle yang memiliki fungsi heuristik yang sama lebih banyak dari pada penggunaan fungsi heuristik kedua. Jadi, penggunaan solusi dari fungsi heuristik kedua dalam contoh penyelesaian 8-puzzle diatas lebih optimal dari pada fungsi heuristik pertama.





Referensi :
http://informatika.stei.itb.ac.id/~rinaldi.munir/Stmik/2010-2011/Makalah2010/MakalahStima2010-011.pdf.
http://kuliahkusayang.blogspot.co.id/2010/04/8-puzzle-problem-ai.html

Share:
Read More
whitenote03. Powered by Blogger.