Knapsack Problem (Soal Bonus)

Pada kesempatan kali ini saya akan menjelaskan tentang Knapsack Problem.

 

Knapsack Problem

Salah satu penggunaan metode greedy adalah untuk menyelesaiakan permasalahan Knapsack (Knapsack problem), 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:

1. 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.
2. 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.
3. Greedy by density
    Strategi ini mengharapkan keuntungan sbesar-besarnya dengan memasukan barang  yang memiliki keuntungan per unit terbesar (Pi/Wi) terlebih dahulu kedalam kantong. 

Tata cara penggunaan metode greedy dalam persoalan knapsack adalah

• Masukkan objek satu per satu ke dalam knapsack. Sekali objek dimasukkan ke dalam knapsack, objek tersebut tidak bisa dikeluarkan lagi. 

Namun karena metode greedy hanya mempertimbangkan keuntungan local dengan harapan mendapat keuntungan global –seperti yang sudah dijelaskan sebelumnya-, maka metode ini juga tidak menjamin akan memberikan solusi optimal.

Contoh 1 :

N = 4;  Maksimum kapasitas = 20 kg

W1 = 20 kg     P1 = 120

W2 = 10 kg     P2 = 80

W3 = 5 kg       P3 = 50

W4 = 10 kg     P4 = 70

Kesimpulan nya adalah dengan menggunakan metode greedy tidaklah selalu mendapatkan hasil yang optimal.

Source :

http://bloglogika.blogspot.co.id/2011/01/knapsack-problem.html

Penyelesaian 8puzzle Menggunakan Metode Greedy

8-Puzzle adalah representasi permainan teka-teki yang dapat diselesaikan dengan mengurutkan atau menyusun komponen-komponen pembentuknya sesuai dengan kondisi yang diinginkan. Komponen pada 8-Puzzle adalah berupa kotak-kotak bernomor atau bergambar (sesuai kebutuhan) yang dapat diacak sedemikian hingga menjadi suatu pola random yang dapat dicari jalan penyelesaiannya. Sesuai namanya, 8-Puzzle terdiri atas 8 kotak dan 1 tempat kosong yang dapat digerakkan dengan aturan tertentu. Aturan pergerakannya hanya berupa empat (4) arah pergerakan, yaitu: atas, bawah, kanan, dan kiri. Serta terlimitasi oleh ukuran dimensi papan yang ditempatinya. Pada 8-Puzzle, batasannya adalah ukuran 3×3. Sehingga, 8 kotak yang dimiliki hanya dapat bergerak dalam lingkup ukuran tersebut.

Disini saya akan menjelaskan cara menyelesaikan puzzle tersebut menggunakan Algoritma Greedy, dengan menggunakan 2 heuristik. 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 kotak yang menempati tempat yang salah.

·         h₂(n) : sebagai total keseluruhan jarak tiap kotak yang menempati tempat yang salah terhadap posisi kotak yang benar.

Initial State dan Goal State yang dipakai disini adalah sebagai berikut.

Berikut adalah penyelesaian dari fungsi heuristik yang pertama atau h₁(n)

Dan ini merupakan penyelesaian dari fungsi heuristik kedua atau h₂(n)

Kesimpulan yang dapat diambil dari pembahasan ini adalah penyelesaian yang paling optimal adalah dengan menggunakan fungsi heuristik yang kedua atau h₂(n) dikarenakan pada h₁(n) pemilihan state berikut nya sedikit sulit ini diakibatkan oleh banyak nya heuristik yang sama besar.

Source :

http://whitenote03.blogspot.co.id/2016/10/penyelesaian-game-8-puzzle-menggunakan.html

https://andiktaufiq.wordpress.com/2010/04/16/8-puzzle-problem-bagian-1/ 

Penyelesaian The Missionaries and The Canibal Problem

Disini saya akan menjelaskan cara penyelesaian The Missionaries dan The Canibal Problem dengan meggunakan teknik DFS atau Depth First Search.

Penyelesaian ini saya dapatkan dari sebuah makalah yang telah di upload ke sebuah website. Berikut link website tersebut https://id.scribd.com/doc/288475990/Penyelesaian-Masalah-the-Missionaries-and-Cannibals-Problem-Menggunakan-Algoritma-Searching-BFS-Dan-DFS .

Pertama saya akan menjelaskan apa itu The Missionaries and The Canibal Problem dan rules awal dari problem tersebut :

1)      Terdapat 3 orang misionaris dan 3 kanibal di salah satu sisi sungai.

2)         Mereka semua harus menyeberangi sungai menggunakan 1 kapal yang bermuatan maksimal 2 orang.

3)      Jika pada salah satu sisi sungai terdapat misionaris dan jumlah misionaris pada sisi tersebut lebih sedikit dari jumlah kanibal pada sisi sungai yang sama maka misionaris akan dimakan oleh kanibal.

Diasumsikan bahwa :

x          = jumlah misionaris di sisi kiri sungai,

y          = jumlah kanibal di sisi kiri sungai,

z          = jumlah kapal di sisi kiri sungai. Jika 0, berarti kapal berada di sisi kanan sungai.

a          = jumlah misionaris di sisi kanan sungai.

b          = jumlah kanibal di sisi kanan sungai.

Dibuatkan State Space Sebagai berikut

State berlatar kuning merupakan state yang tidak diperbolehkan, sebab jumlah misionaris pada salah salah satu sisi lebih sedikit dari jumah kanibalnya, sehingga misionaris akan dimakan kanibal.

Setelah itu kita mendefinisikan problem dari pembahasan ini yaitu :

-Initial State atau State awal State awal daari problem ini yaitu berada pada (3,3,1)

-Succesor Function disini merupakan Production Rule dari permasalahan yang akan dibahas disini

- Goal Test atau tujuan yang ingin dicapai yaitu berada pada (0,0,0)

- Path Cost atau jumlah aksi yang diperlukan untuk menyelesaikan permasalahan

Dalam penyelesaian menggunakan DFS terdapat beberapa Production Rule atau syarat pemecahan, berikut Production Rulenya

1)      1 misionaris menyeberang ke sisi kanan sungai.

Jika x≥1 dan z=1 maka (x-1, y, 0).

2)      2 misionaris menyeberang ke sisi kanan sungai.

Jika x≥2 dan z=1 maka (x-2, y, 0).

3)      1 kanibal menyeberang ke sisi kanan sungai.

Jika y≥1 dan z=1 maka (x, y-1, 0).

4)      2 kanibal menyeberang ke sisi kanan sungai.

Jika y≥2 dan z=1 maka (x, y-2, 0).

5)      1 misionaris dan 1 kanibal menyeberang ke sisi kanan sungai.

Jika x≥1 dan y≥1 dan z=1 maka (x-1, y-1, 0).

6)      1 misionaris kembali ke sisi kiri sungai.

Jika x<3 dan z=0 maka (x+1, y, 1).

7)      2 misionaris kembali ke sisi kiri sungai.

Jika x<2 dan z=0 maka (x+2, y, 1).

8)      1 kanibal kembali ke sisi kiri sungai.

Jika y<3 dan z=0 maka (x, y+1, 1).

9)      2 kanibal kembali ke sisi kiri sungai.

Jika y<2 dan z=0 maka (x, y+2, 1).

10)    1 misionaris dan 1 kanibal kembali ke sisi kiri sungai.

Jika x<3 dan y<3 dan z=0 maka (x+1, y+1, 1).

Selain Production Rule di atas, terdapat aturan lain yaitu jika pada salah satu sisi sungai terdapat misionaris dan jumlah misionaris pada sisi tersebut lebih sedikit dari jumlah kanibal pada sisi sungai yang sama maka misionaris akan dimakan oleh kanibal. Hal ini tidak boleh terjadi.

Aturan tersebut dituliskan :

Untuk sisi kiri sungai: Jika x > 0 dan x < y maka state tidak diperbolehkan.

Untuk sisi kanan sungai: Jika a > 0 dan a < b maka state tidak diperbolehkan.

Diketahui bahwa a = 3-x dan b= 3-y;

a  > 0;

3-x  > 0;

3  > x;

x < 3;

a  < b;

3-x  < 3-y;

-x  < -y;

x  > y;

Sehingga aturan untuk sisi kanan sungai dapat ditulis menjadi:

Jika x < 3 dan x > y maka state tidak diperbolehkan.

Penyelesaian dengan Algoritma Depth First Search

Initial State = (3,3,1) dan Goal State = (0,0,0).

Algoritma DFS menggunakan stack yang bersifat LIFO (Last In First Out). State akan dimasukkan ke dalam stack dan di-expand dari data terakhir. Jika state sudah pernah masuk ke dalam stack S, akan diberi tanda X. Jika terdapat beberapa state dengan kedalaman yang sama, akan dimasukkan sekaligus ke dalam stack. State yang memiliki kedalaman yang sama tersebut akan di-expand sesuai urutan (dari yang paling kiri). Untuk menunjukkan perbedaan kedalaman, akan digunakan tanda pembatas ||.

1) S = [ |(3,3,1)| ]

Expand (3,3,1).

R1 → (2,3,0) Masuk ke S.

R2 → (1,3,0) Masuk ke S.

R3 → (3,2,0) Masuk ke S.

R4 → (3,1,0) Masuk ke S.

R5 → (2,2,0) Masuk ke S.

2) S = [ |(2,3,0); (1,3,0); (3,2,0); (3,1,0); (2,2,0)| ]

Expand (2,3,0). Merupakan state yang tidak diperbolehkan, pada sisi kiri sungai terdapat misionaris tetapi lebih sedikit dari jumlah kanibal di sisi sungai yang sama (x>0 dan x<y).

3) S = [ |(1,3,0); (3,2,0); (3,1,0); (2,2,0)| ]

Expand (1,3,0). Merupakan state yang tidak diperbolehkan, pada sisi kiri sungai terdapat misionaris tetapi lebih sedikit dari jumlah kanibal di sisi sungai yang sama (x>0 dan x<y).

4) S = [ |(3,2,0); (3,1,0); (2,2,0)| ]

Expand (3,2,0).

 R8 → (3,3,1) X. Sudah pernah dimasukkan ke dalam S.

5) S = [ |(3,1,0); (2,2,0)| ]

Expand (3,1,0).

R8 → (3,2,1) Masuk ke S.

R9 → (3,3,1) X. Sudah pernah dimasukkan ke dalam S.

6) S = [ |(2,2,0)|; |(3,2,1)| ]

Expand (3,2,1).

R1 → (2,2,0) X.

R2 → (1,2,0) Masuk ke S. 

R3 → (3,1,0) X.

R4 → (3,0,0) Masuk ke S.

R5 → (2,1,0) Masuk ke S.

7) S = [ |(2,2,0)|; |(1,2,0); (3,0,0); (2,1,0)| ]

Expand (1,2,0). State yang tidak diperbolehkan.

8) S = [ |(2,2,0)|; |(3,0,0); (2,1,0)| ]

Expand (3,0,0).

R7 → (3,1,1) Masuk ke S.

R8 → (3,2,1) X. 

9) S = [ |(2,2,0)|; |(2,1,0)|; |(3,1,1)| ]

Expand (3,1,1).

R1 → (2,1,0) X.

R2 → (1,1,0) Masuk ke S.

R3 → (3,0,0) X.

R5 → (2,0,0) Masuk ke S.

10) S = [ |(2,2,0)|; |(2,1,0)|; |(1,1,0); (2,0,0)| ]

Expand (1,1,0).

R6 → (2,1,1) Masuk ke S.

R7 → (3,1,1) X.

R8 → (1,2,1) Masuk ke S.

R9 → (1,3,1) Masuk ke S.

R10 → (2,2,1) Masuk ke S.

11) S = [ |(2,2,0)|; |(2,1,0)|; |(2,0,0)|; |(2,1,1); (1,2,1); (1,3,1); (2,2,1)| ]

Expand (2,1,1). Merupakan state yang tidak diperbolehkan, pada sisi kanan sungai terdapat misionaris tetapi lebih sedikit dari jumlah kanibal di sisi sungai yang sama (x<3 dan x>y).

12) S = [ |(2,2,0)|; |(2,1,0)|; |(2,0,0)|; |(1,2,1); (1,3,1); (2,2,1)| ]

Expand (1,2,1). State yang tidak diperbolehkan.

13) S = [ |(2,2,0)|; |(2,1,0)|; |(2,0,0)|; |(1,3,1); (2,2,1)| ]

Expand (1,3,1). State yang tidak diperbolehkan.

14) S = [ |(2,2,0)|; |(2,1,0)|; |(2,0,0)|; |(2,2,1)| ]

Expand (2,2,1).

R1 → (1,2,0) X.

R2 → (0,2,0) Masuk ke S.

R3 → (2,1,0) X.

R4 → (2,0,0) X.

R5 → (1,1,0) X. 

15) S = [ |(2,2,0)|; |(2,1,0)|; |(2,0,0)|; |(0,2,0)| ]

Expand (0,2,0).

R6 → (1,2,1) X.

R7 → (2,2,1) X.

R8 → (0,3,1) Masuk ke S.

R10 → (1,3,1) X. 

16) S = [ |(2,2,0)|; |(2,1,0)|; |(2,0,0)|; |(0,3,1)| ]

Expand (0,3,1).

R3 → (0,2,0) X.

R4 → (0,1,0) Masuk ke S. 

17) S = [ |(2,2,0)|; |(2,1,0)|; |(2,0,0)|; |(0,1,0)| ]

Expand (0,1,0).

R6 → (1,1,1) Masuk ke S.

R7 → (2,1,1) X.

R8 → (0,2,1) Masuk ke S.

R9 → (0,3,1) X.

R10 → (1,2,1) X. 

18) S = [ |(2,2,0)|; |(2,1,0)|; |(2,0,0)|; |(1,1,1); (0,2,1)| ]

Expand (1,1,1).

R1 → (0,1,0) X.

R3 → (1,0,0) Masuk ke S.

R5 → (0,0,0) Masuk ke S. 

19) S = [ |(2,2,0)|; |(2,1,0)|; |(2,0,0)|; |(0,2,1)|; |(1,0,0); (0,0,0)| ]

Expand (1,0,0). State yang tidak diperbolehkan.

20) S = [ |(2,2,0)|; |(2,1,0)|; |(2,0,0)|; |(0,2,1)|; |(0,0,0)| ]

Expand (0,0,0). Goal State telah dicapai, stop.

Jadi, Algoritma DFS berhasil menemukan solusi untuk the missionaries and cannibals problem setelah melakukan 20 kali perulangan. Dengan melacak jalur yang dilalui, diperoleh solusi:

Ilustrasi penyelesaian dengan Algoritma Depth First Search

Source :

https://id.scribd.com/doc/288475990/Penyelesaian-Masalah-the-Missionaries-and-Cannibals-Problem-Menggunakan-Algoritma-Searching-BFS-Dan-DFS