Design and Analysis of Algorithm

Design and Analysis of Algorithm Week 7: Brute Force Algorithm Part 2: Exhaustive Search

Dr. Putu Harry Gunawan1 1 Department

of Computational Science School of Computing Telkom University

Dr. Putu Harry Gunawan (Telkom University)

Design and Analysis of Algorithm

1 / 40

Outline 1

Introduction Introduction

2

Traveling Salesman Problem Traveling Salesman Problem

3

Knapsack Problem Knapsack Problem

4

Assignment Cost Problem

5

References References



2 / 40

Outline 1


2


3


4


5




3 / 40

Introduction

Berbagai macam masalah biasanya perlu menemukan sebuah elemn dengan properti khusus pada sebuah domain yang dapat membesar secara exponensial. Biasanya terdapat pada masalah yang masuk secara implisit maupun explisit ke dalam kombinatorik, seperti permutasi, kombinasi, dan subset dari sebuah himpunan. Seperti pada masalah optimasi: yaitu bertujuan untuk menemukan suatu elemen yang memaksimumkan atau meminimumkan beberapa karakteristik yang diinginkan seperti pada sebuah panjang lintasan atau sebuah biaya.



4 / 40

Introduction

Exhaustive search merupakan sutau pendekatan brute force untuk masalah yang berkaitan dengan kombinatorik. Algoritma ini mengijinkan:



5 / 40

Introduction

Exhaustive search merupakan sutau pendekatan brute force untuk masalah yang berkaitan dengan kombinatorik. Algoritma ini mengijinkan: membentuk setiap elemen dari domain permasalahan,



5 / 40

Introduction

Exhaustive search merupakan sutau pendekatan brute force untuk masalah yang berkaitan dengan kombinatorik. Algoritma ini mengijinkan: membentuk setiap elemen dari domain permasalahan, menyeleksi elemen yang memenuhi semua konstrain,



5 / 40

Introduction

Exhaustive search merupakan sutau pendekatan brute force untuk masalah yang berkaitan dengan kombinatorik. Algoritma ini mengijinkan: membentuk setiap elemen dari domain permasalahan, menyeleksi elemen yang memenuhi semua konstrain, menemukan sebuah elemen yang diinginkan ( sesuatu yang mengoptimalkan fungsi objek).



5 / 40

Introduction

Catatan bahawa, meskipun ide dari exhaustive search straightforward/ lempeng, implementasinya membutuhkan secara khusus algoritma yang membentuk kombinasi obkjek.



6 / 40

Introduction

Catatan bahawa, meskipun ide dari exhaustive search straightforward/ lempeng, implementasinya membutuhkan secara khusus algoritma yang membentuk kombinasi obkjek. Berikut akan diberikan beberapa contoh dalam algoritma exhaustive search seperti: Traveling Salesman Problem, Knapsack 0/1, dan assignment problem.



6 / 40

Outline 1


2


3


4


5




7 / 40

TSP

Traveling salesmen problem (TSP) sudah menjadi hal yang sering diperhatikan oleh peneliti dari 150 tahun yang lalu, karena merupakan formula yang sederhana, aplikasi penting, dan koneksi menarik untuk masalah kombinasi lainnya. Salah satu contoh masalah TSP adalah menemukan tour terpendek dari sebuah himpunan n kota yang harus dikunjungi tepat sekali dan balik kembali ke kota awal keberangkatan.



8 / 40

TSP

Model dari masalah ini dapat dimodelkan dengan graf berbobot (weighted graph, dengan vertek dari graf mempresentasikan kota dan garis menyatakan besaran jarak. Sehingga masalah ini dapat dikategorikan sebagai masalah menemukan sirkuit Hamilton terpendek dari graf.



9 / 40

TSP

Circuit Hamilton (A Hamiltonian circuit is defined as a cycle that passes through all the vertices of the graph exactly once. It is named after the Irish mathematician Sir William Rowan Hamilton (1805-1865), who became interested in such cycles as an application of his algebraic discoveries.)



10 / 40

TSP

Algorithm Algoritma exhaustive search untuk persoalan TSP: 1

Enumerasikan ( list ) semua sirkuit Hamilton dari graf lengkap dengan n buah simpul.

2

Hitung ( evaluasi ) bobot setiap sirkuit Hamilton yang ditemukan pada langkah 1.

3

Pilih sirkuit Hamilton yang mempunyai bobot terkecil.



11 / 40

TSP Berikut diberikan contoh untuk n = 4 dan simpul awal a.



12 / 40

TSP Berikut diberikan contoh untuk n = 4 dan simpul awal a.

Tour 1. 2. 3. 4. 5. 6.

a a a a a a

---> ---> ---> ---> ---> --->

b b c c d d

---> ---> ---> ---> ---> --->

length c d b d b c

---> ---> ---> ---> ---> --->

d c d b c b

---> ---> ---> ---> ---> --->

a a a a a a

I I I I I I

= = = = = =

2 2 5 5 7 7

+ + + + + +

8 3 8 1 3 1

+ + + + + +

1 1 3 3 8 8

+ + + + + +

7 5 7 2 5 2

= = = = = =

18 11 23 11 23 18

Figure : Solusi dari contoh traveling salesman problem menggunakan exhaustive search.



13 / 40

TSP

Jadi rute perjalanan terpendeknya adalah: 1. a − − > b − − > d − − > c − − > a 2. a − − > c − − > d − − > b − − > a yang nilanya sebesar 11. Untuk n buah simpul semua rute perjalanan yang mungkin dibangkitkan dengan permutasi dari n − 1 buah simpul. Permutasi dari n − 1 buah simpul adalah (n − 1)!. Pada contoh di atas, untuk n = 4 akan terdapat (4 − 1)! = 3! = 6 buah rute perjalanan.



14 / 40

TSP Beberapa karakteristik yang didapat dari contoh di atas adalah:



15 / 40

TSP Beberapa karakteristik yang didapat dari contoh di atas adalah: Jika diselesaikan dengan metode exhaustive search, maka kita harus mengenumerasi sebanyak (n − 1)! buah sirkuit Hamilton, menghitung setiap bobotnya , dan memilih sirkuit Hamilton dengan bobot terkecil.



15 / 40

TSP Beberapa karakteristik yang didapat dari contoh di atas adalah: Jika diselesaikan dengan metode exhaustive search, maka kita harus mengenumerasi sebanyak (n − 1)! buah sirkuit Hamilton, menghitung setiap bobotnya , dan memilih sirkuit Hamilton dengan bobot terkecil. Kompleksitas waktu algoritma exhaustive search untuk persoalan TSP sebanding dengan (n − 1)! dikali dengan waktu untuk menghitung bobot setiap sirkuit Hamilton.



15 / 40

TSP Beberapa karakteristik yang didapat dari contoh di atas adalah: Jika diselesaikan dengan metode exhaustive search, maka kita harus mengenumerasi sebanyak (n − 1)! buah sirkuit Hamilton, menghitung setiap bobotnya , dan memilih sirkuit Hamilton dengan bobot terkecil. Kompleksitas waktu algoritma exhaustive search untuk persoalan TSP sebanding dengan (n − 1)! dikali dengan waktu untuk menghitung bobot setiap sirkuit Hamilton. Menghitung bobot setiap sirkuit Hamilton membutuhkan waktu O(n), sehingga kompleksitas waktu algoritma exhaustive search untuk persoalan TSP adalah O(n · n!).



15 / 40

TSP Beberapa karakteristik yang didapat dari contoh di atas adalah: Jika diselesaikan dengan metode exhaustive search, maka kita harus mengenumerasi sebanyak (n − 1)! buah sirkuit Hamilton, menghitung setiap bobotnya , dan memilih sirkuit Hamilton dengan bobot terkecil. Kompleksitas waktu algoritma exhaustive search untuk persoalan TSP sebanding dengan (n − 1)! dikali dengan waktu untuk menghitung bobot setiap sirkuit Hamilton. Menghitung bobot setiap sirkuit Hamilton membutuhkan waktu O(n), sehingga kompleksitas waktu algoritma exhaustive search untuk persoalan TSP adalah O(n · n!). Perbaikan : setengah dari rute perjalanan adalah hasil pencerminan dari setengah rute yang lain, yakni dengan mengubah arah rute perjalanan 1 dan 6, 2 dan 4, 3 dan 5. maka dapat dihilangkan setengah dari jumlah permutasi ( dari 6 menjadi 3).



15 / 40

TSP

Ketiga buah sirkuit Hamilton yang dihasilkan adalah seperti gambar di bawah ini :



16 / 40

TSP

Ketiga buah sirkuit Hamilton yang dihasilkan adalah seperti gambar di bawah ini :

Dengan demikian, untuk graf dengan buah simpul, kita hanya perlu mengevaluasi sirkuit Hamilton sebanyak (n − 1)!/2 buah.



16 / 40

TSP

Untuk ukuran masukan yang besar, algoritma exhaustive search menjadi sangat tidak mangkus.



17 / 40

TSP

Untuk ukuran masukan yang besar, algoritma exhaustive search menjadi sangat tidak mangkus. Pada persoalan TSP misalnya , untuk jumlah simpul n = 20 akan terdapat (19!)/2 = 6 × 1016 sirkuit Hamilton yang harus dievaluasi satu per satu.



17 / 40

TSP

Untuk ukuran masukan yang besar, algoritma exhaustive search menjadi sangat tidak mangkus. Pada persoalan TSP misalnya , untuk jumlah simpul n = 20 akan terdapat (19!)/2 = 6 × 1016 sirkuit Hamilton yang harus dievaluasi satu per satu. Sayangnya, untuk persoalan TSP tidak ada algoritma lain yang lebih baik daripada algoritma exhaustive search.



17 / 40

TSP

Untuk ukuran masukan yang besar, algoritma exhaustive search menjadi sangat tidak mangkus. Pada persoalan TSP misalnya , untuk jumlah simpul n = 20 akan terdapat (19!)/2 = 6 × 1016 sirkuit Hamilton yang harus dievaluasi satu per satu. Sayangnya, untuk persoalan TSP tidak ada algoritma lain yang lebih baik daripada algoritma exhaustive search. Jika anda dapat menemukan algoritma yang mangkus untuk TSP, anda akan menjadi terkenal dan kaya! Algoritma yang mangkus selalu mempunyai kompleksitas waktu dalam orde polinomial.



17 / 40

TSP Exercise Tentukan rute dan jarak terpendek dari contoh-contoh berikut. Pada TSP berikut:



18 / 40

TSP Exercise Tentukan rute dan jarak terpendek dari contoh-contoh berikut. Pada TSP berikut (UTS 2004):



19 / 40

TSP Exercise Tentukan rute dan jarak terpendek dari contoh-contoh berikut. Pada TSP berikut:



20 / 40

Outline 1


2


3


4


5




21 / 40

0/1 Knapsack

Masalah Knapsack adalah masalah yang terkenal dalam algoritma. Diberikan n items/objek yang memiliki properti seperti bobot w1 , w2 , · · · wn dan keuntungan p1 , p2 , · · · , pn . Dengan kapasitas bobot Knapsack K . Permasalahan yang terjadi adalah bagaimana memilih memilih objek - objek yang dimasukkan ke dalam knapsack sedemikian sehingga memaksimumkan keuntungan. Total bobot objek yang dimasukkan ke dalam knapsack tidak boleh melebihi kapasitas knapsack K .



22 / 40

0/1 Knapsack

Idea If you do not like the idea of putting yourself in the shoes of a thief who wants to steal the most valuable loot that fits into his knapsack, think about a transport plane that has to deliver the most valuable set of items to a remote location without exceeding the plane’s capacity.



23 / 40

0/1 Knapsack

Persoalan 0/1 Knapsack dapat kita pandang sebagai mencari himpunan bagian (subset) dari keseluruhan objek yang muat ke dalam knapsack dan memberikan total keuntungan terbesar. Solusi persoalan dinyatakan sebagai vektor n-tupel: X = {x1 , x2 , · · · , xn } dengan xi = 1 jika objek ke-i dimasukkan ke dalam knapsack, xi = 0 jika objek ke-i tidak dimasukkan.



24 / 40

0/1 Knapsack

Formualsi matemntaikanya dapat dibentuk menjadi: Maximumkan F =

n X

pi xi

i

dengan kendala n X

wi xi ≤ K

i

dengan i = 0 atau 1, ∀i = 1, 2, · · · n.



25 / 40

0/1 Knapsack

Algoritma exhaustive search untuk persoalan 0/1 Knapsack : 1

Enumerasikan (list) semua himpunan bagian dari himpunan dengan n objek.

2

Hitung (evaluasi) total keuntungan dari setiap himpunan bagian dari langkah 1.

3

Pilih himpunan bagian yang memberikan total keuntungan terbesar.



26 / 40

0/1 Knapsack

Example Diberikan data untuk n = 4 seperti berikut ini: w1 = 2;

p1 = 20

w2 = 5;

p2 = 30

w3 = 10; w4 = 5;

p3 = 50 p4 = 10

Kapasitas knapsack K = 16.



27 / 40

0/1 Knapsack Langkah - langkah pencarian solusi 0/1 Knapsack secara exhaustive search dirangkum dalam tabel di bawah ini : Table : Solusi menggunakan exhaustive search, bagian tebal menyatkan solusi optimal.



28 / 40

0/1 Knapsack

Solution Himpunan bagian objek yang memberikan keuntungan maksimum adalah {2, 3} dengan total keuntungan adalah 80. Sehingga solusi: X = {0, 1, 1, 0}.



29 / 40

0/1 Knapsack

Berapa banyak himpunan bagian dari sebuah himpunan dengan n elemen? Jawabnya adalah 2n . Waktu untuk menghitung total bobot objek yang dipilih = O(n). Sehingga , Kompleksitas algoritma exhaustive search untuk persoalan 0/1 Knapsack = O(n · 2n ).



30 / 40

0/1 Knapsack

Berapa banyak himpunan bagian dari sebuah himpunan dengan n elemen? Jawabnya adalah 2n . Waktu untuk menghitung total bobot objek yang dipilih = O(n). Sehingga , Kompleksitas algoritma exhaustive search untuk persoalan 0/1 Knapsack = O(n · 2n ). TSP dan 0/1 Knapsack , adalah contoh persoalan eksponensial. Keduanya digolongkan sebagai persoalan NP (Non-deterministic Polynomial), karena tidak mungkin dapat ditemukan algoritma polinomial untuk memecahkannya.



30 / 40

0/1 Knapsack

Exercise Diberikan data untuk n = 4 seperti berikut ini: w1 = 7;

p1 = $42

w2 = 3;

p2 = $12

w3 = 4;

p3 = $40

w4 = 5;

p4 = $25

Kapasitas knapsack K = 10. Tentukan solusi optimalnya.



31 / 40

Assignment Cost

Pada contoh ketiga dari masalah yang bisa diselesaikan dengan exhaustive search, adalah masalah Biaya Kerja. Masalahnya dimulai dengan adanya n orang yang perlu di berikan pekerjaan yang sebanyak n tugas. Syaratnya adalah satu orang satu pekerjaan, yang artinya setiap orang tepat mendapat satu pekerjaan dan setiap pekerjaan dikerjakan oleh tepat satu orang.



32 / 40

Assignment Cost

Pada contoh ketiga dari masalah yang bisa diselesaikan dengan exhaustive search, adalah masalah Biaya Kerja. Masalahnya dimulai dengan adanya n orang yang perlu di berikan pekerjaan yang sebanyak n tugas. Syaratnya adalah satu orang satu pekerjaan, yang artinya setiap orang tepat mendapat satu pekerjaan dan setiap pekerjaan dikerjakan oleh tepat satu orang. Biaya yang dikeluarkan jika orang ke-i ditempatkan pada pekerjaan ke-j disebut sebagai quantity C [i, j] untuk setiap i, j = 1, 2, · · · , n. Selanjutnya akan dicari assignment/penempatan orang terhadap pekerjaan dengan memperhatikan total biaya harus minimum. Sebagai contoh, perhatikan nilai C [i, j] berikut ini:



32 / 40

Assignment Cost

Dono Kasino Indro Toyib


Job 1 9 6 5 7

Job 2 2 4 8 6

Job 3 7 3 1 9


Job 4 8 7 8 4

33 / 40

Assignment Cost

Dengan jelas dapat kita lihat bahwa penempatan pekerja dapat di gambarkan dengan matrik biaya C . Dalam matrix, masalahnya adalah memilih setiap elemen pada baris sehingga setiap elemen memiliki kolom berbeda, dan total biaya minimum. Solusi dari masalsah ini tidak begitu jelas. Misalkan kita memilih satu pekerja pada biaya yang minimum, akan tetapi akan ada kemungkinan pekerja lain memiliki baya minimum pada kolom yang sama.



34 / 40

Assignment Cost

Solusi persoalan dinyatakan sebagai vektor n-tupel: X = {x1 , x2 , · · · , xn } dengan xi menyatakan kolom dari elemen yang dipilih pada baris ke-i. Sebagai contoh pada matrix di atas, {2, 3, 4, 1} mengindikasikan bahwa Dono ke Job 1, Kasino ke Job 3, Indro ke Job 4, Toyib ke Job 1.



35 / 40

Assignment Cost

Exhaustive search menangani masalah ini dengan membangkitkan semua permutasi dari bilangan bulat 1, 2, · · · , n, menghitung total biaya dari setiap assignment. Sebagai contoh, untuk mengerjakan masalah di atas:   9 2 7 8  6 4 3 7   C =  5 8 1 8  7 6 9 4



36 / 40

Assignment Cost Maka kandidat slusinya adalah {1, 2, 3, 4},

cost = 9 + 4 + 1 + 4 = 18

{1, 2, 4, 3},

cost = 9 + 4 + 8 + 9 = 30

{1, 3, 2, 4},

cost = 9 + 3 + 8 + 4 = 24

{1, 3, 4, 2},

cost = 9 + 3 + 8 + 6 = 26

{1, 4, 2, 3},

cost = 9 + 7 + 8 + 9 = 33

{1, 4, 3, 2},

cost = 9 + 7 + 1 + 6 = 23

dst... Karena jumlah permutasi dapat diperumum, maka kompleksitas waktunya adalah O(n!), sehingga exhaustive search sangatlah tidak praktis digunakan. Untungnya, terdapat algoritma yang lebih effisien yang dikenal dengan the Hungarian method setelah matematikawan dari Hungaria K¨ onig and Egerv´ary yang memulai metode tersebut (see, e.g., [Kol95]). Dr. Putu Harry Gunawan (Telkom University)


37 / 40

Outline 1


2


3


4


5




38 / 40

References

References 1

Anany, L. (2003). Introduction to the design and analysis of algorithms. Villanova University.



39 / 40

The end of week 7

Thank you for your attention!



40 / 40

Design and Analysis of Algorithm

Recommend Documents