Algoritma Brute Force Algoritma Greedy

Alg. Brute ForceAlg. Greedy

Masayu Leylia KhodraIF-ITB

2

Brute Force

Pendekatan problem solving Berdasarkan pernyataan masalah dandefinisi konsep yang dilibatkanStrategi design yang paling sederhanaPaling mudah untuk diaplikasikan

3

Contoh Brute Force: Pangkat

• Menghitung an (a > 0, n ≥ 0)an=a*a*…*a (n kali) , jika n > 0an=1, jika n = 0Algoritma:

kalikan 1 dgn a sebanyak n kali

4

2. Menghitung n! (n ≥ 0)n!=1*2*3*…*n , jika n > 0n!=1, jika n = 0 Algoritma:

kalikan n buah bilangan, yaitu 1* 2* 3* …* n

Contoh Brute Force: Faktorial

5

Problem of sorting:Diberikan list of n orderable items, urutkanitems list dalam urutan menaik/menurun

Contoh list: 89 45 68 90 29 34 17Terurut menaik: 17 29 34 45 68 89 90Terurut menurun: 90 89 68 45 34 29 17

Contoh Brute Force: Selection Sort

6

89 45 68 90 29 34 1717 | 45 68 90 29 34 8917 29 | 68 90 45 34 8917 29 34 | 90 45 68 8917 29 34 45 | 90 68 8917 29 34 45 68 | 90 8917 29 34 45 68 89 | 90

Selection Sort: MinSort

7

Persoalan Kombinatorial

Tipe masalah yang diminta untukmenemukan objek kombinatorial yang memenuhi constraints tertentu danmemiliki properti yang diinginkanJumlah objek kombinatorial biasanyatumbuh sangat cepat dengan ukuranmasalah

8

Penukaran uang: 2n

Travelling Salesperson Problem: (n-1)! 1/0 KnapsackPenjadwalanPohon merentang minimumLintasan terpendek

Contoh Persoalan Kombinatorial

9

Exhaustive Search

Pendekatan brute force untuk persoalankombinatorial

Enumerasi setiap solusi yang mungkindengan sistematisEvaluasi setiap solusi satu per satu, buangsolusi yang tidak layak (tidak memenuhiconstraints), dan simpan solusi terbaik

10

Contoh Kasus Penukaran Uang

1. Misalkan koin yang tersedia ada 12 yaitu: 5 koin bernilai 1, 3 koin bernilai 5,3 koin bernilai 10, 1 koin bernilai 25.

Carilah solusi dengan menggunakan algoritmaBrute Force jika uang yang akan ditukarbernilai 35 (minimasi jumlah koin)

11

Solusi: Brute Force5(1)+3(5)+1(10) tidak layak5(1)+3(10) 8 koin1(5)+3(10) 4 koin3(5)+2(10) 5 koin…2(5)+1(25) 3 koin1(10)+1(25) 2 koinSolusi optimal: 1(10)+1(25) 2 koin

Jumlah kemungkinan: 212 = 4096

12

Solusi: Brute Force (2)

Koin: C={c1, c2,.., cn}Solusi: X={x1,x2,…, xn}xi=1 jika koin dipilihxi=0 jika koin tidak dipilihObjektif: minimasi F=Kendala:

∑=

n

iix

1Axc

n

iii =∑

=1

13

Solusi: Brute Force (3)

Koin: C={1,1,1,1,1,5,5,5,10,10,10,25}Objektif: minimasi F (jumlah koin)Kendala: 35

1=∑

=

n

iii xc

14

Calon Solusi1 1 1 1 1 5 5 5 10 10 10 25 F0 0 0 0 0 0 0 0 0 0 0 0 01 0 0 0 0 0 0 0 0 0 0 0 1…0 0 0 0 0 0 0 0 1 0 0 1 20 0 0 0 0 0 0 0 0 1 0 1 20 0 0 0 0 0 0 0 0 0 1 1 2…0 0 0 0 0 1 0 0 1 1 1 0 4…0 0 0 0 0 1 1 1 1 1 0 0 5…1 1 1 1 1 0 0 0 1 1 1 0 8…1 1 1 1 1 1 1 1 1 1 1 1 1

15

GreedyPrinsip: take what you can get now.Membentuk solusi langkah per langkahPilihan yang dibuat pada setiap langkah:

Feasible: memenuhi problem’s constraintsLocally optimum: optimum lokal (tanpamemperhatikan pilihan sebelumnya ataukonsekuensinya ke depan), dan berharap akanberakhir dengan optimum globalIrrevocable: Keputusan yang telah diambil pada suatulangkah tidak dapat diubah lagi pada langkahselanjutnya.

16

Persoalan Penukaran Uang

Objektif persoalan: minimasi jumlah koinStrategi Greedy:

Urutkan uang dalam urutan yang menurunPada setiap langkah, pilihlah koin dengannilai sebesar mungkin dari himpunan koinyang tersisa dengan syarat tidak melebihi nilaiuang yang ditukarkan

17

Contoh Kasus Penukaran Uang

1. Misalkan koin yang tersedia ada 12 yaitu: 5 koin bernilai 1, 3 koin bernilai 5,3 koin bernilai 10, 1 koin bernilai 25.

Carilah solusi dengan menggunakan algoritmaGreedy jika uang yang akan ditukar bernilai 35

18

Solusi: Greedy

Langkah 1: pilih 1 koin 25 (Total = 25)Langkah 2: pilih 1 koin 10 (Total=25+10=35)Solusi: 1(25)+1(10) 2 koin

19

Contoh Kasus Tidak Optimal

Koin: {5,4,3,1,1}, A=7Greedy: {1,0,0,1,1} layak, tidak optimalOptimal: {0,1,1,0,0}Greedy DAPAT GAGAL memberikansolusi optimal.

20

Travelling Salesperson Problem

Input: n kota, jarak antarasetiap kota satu samalain, kota asal

Output: mencari sirkuitHamilton terpendek(melalui setiap kotalainnya hanya sekali)

a b

cd

12

8

15

1095

21

Contoh kasus TSP4 kota, perjalanan dimulai dari a

a b

cd

12

8

15

1095

22

Solusi TSP: Brute Force

a b c d a: 45a b d c a: 41a c b d a: 32a c d b a: 41a d b c a: 32a d c b a: 45

a b

cd

12

8

15

1095

Jumlah sirkuit hamilton: (n-1)! atau (n-1)!/2

23

Solusi TSP: GreedyStrategi: pada setiaplangkah, pilih kota yang belum pernah dikunjungiyang mempunyai jarakterdekat.L-1: a c (5)L-2: a c b (5+8)L-3: a c b d (5+8+9)L-4: a c b d a(5+8+9+10=32)

a b

cd

12

8

15

1095

24

Persoalan 1/0 Knapsack

Diberikan: n objek(weight,profit), 1 knapsack (kapasitas)Objektif: maksimasi total profit dengan total weight objek-objek dalamknapsack tidak melebihikapasitasnya.

25

Persoalan 1/0 Knapsack (2)

Alternatif strategi:Greedy by profit:

Pada setiap langkah, knapsack diisi dengan objekyang mempunyai profit terbesar.

Greedy by weight:Pada setiap langkah, knapsack diisi dengan objekyang mempunyai weight terkecil.

Greedy by density:Pada setiap langkah, knapsack diisi dengan objekyang mempunyai profit per unit weight terbesar.

26

Contoh Kasus 1/0 Knapsack

Misalkan terdapat tiga objek:W1=5; p1=50W2=10;p2=60W3=20;p3=140

Carilah solusi dengan menggunakanalgoritma Greedy jika kapasitas knapsack adalah 30.

27

1/0 Knapsack: Solusi

Greedy by profit: Pilih 3 2 Total profit=140+60=200

Greedy by weight:Pilih 1 2 Total profit=50+60=110

Greedy by density:Pilih 1 3 Total profit=50+140=190

28

Persoalan Penjadwalan

Objektif persoalan: minimasi waktu dalamsistemStrategi greedy:

Pada setiap langkah, pilih job yang membutuhkan waktu pelayanan terkecil diantara job yang belum dilayani

29

Contoh Kasus Penjadwalan

Misalkan ada 3 job dengan waktupelayanan:

t1=5t2=10t3=4

Penjadwalan dengan menggunakanalgoritma Greedy: 3 1 2, dengantotal waktu pelayanan 32.

30

Penjadwalan denganDeadlines

Diberikan: n job (deadline, profit). Profit didapatkan jika job selesai sebelumdeadline. Objektif persoalan: maksimasi total profitStrategi greedy:

Pada setiap langkah, pilih job dengan profit terbesar

31

Contoh KasusPenjadwalan dg Deadlines

Misalkan terdapat 4 job:d1=2; p1=30d2=1; p2=35d3=2; p3=25d4=1; p4=40

Penjadwalan dengan menggunakanalgoritma Greedy: 4 1, dengan total profit 40+30=70