Design and Analysis of Algorithms CNH2G3- Week 7 Brute Force Algorithm Part 2: Exhaustive Search Dr. Putu Harry Gunawan (PHN)
Daftar Isi 1 Pendahuluan . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1
2 Traveling Salesman Problem . . . . . . . . . . . . . . . . . . . . . . . . . . .
1
3 Knapsack Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5
4 Assignment Cost Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
6
1
Pendahuluan
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. 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). 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.
2
Traveling Salesman Problem
Traveling salesmen problem (TSP) sudah menjadi hal yang sering diperhatikan oleh peneliti dari 150 tahun yang lalu, karena merupakan formula yang sederhana, aplikasi
1
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. 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. (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.)
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. Example 2.1 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
optimal optimal
Gambar 1: Solusi dari contoh traveling salesman problem menggunakan exhaustive search. Jadi rute perjalanan terpendeknya adalah: 1. a − − > b − − > d − − > c − − > a 2
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. 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). • 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. • 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.
3
Exercise 2.2 Tentukan rute dan jarak terpendek dari contoh-contoh berikut. 1. Pada TSP berikut:
2. Pada TSP berikut (UTS 2004):
3. Pada TSP berikut:
4
3
Knapsack Problem
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. 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.
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. Formualsi matemntaikanya dapat dibentuk menjadi: Maximumkan F =
n X
p i xi
i
dengan kendala n X
wi x i ≤ K
i
dengan i = 0 atau 1, ∀i = 1, 2, · · · n. 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. Example 3.1 Diberikan data untuk n = 4 seperti berikut ini: w1 = 2;
p1 = 20
w2 = 5;
p2 = 30
w3 = 10;
p3 = 50
w4 = 5;
p4 = 10 5
Kapasitas knapsack K = 16. Langkah - langkah pencarian solusi 0/1 Knapsack secara exhaustive search dirangkum dalam tabel di bawah ini :
Tabel 1: Solusi menggunakan exhaustive search, bagian tebal menyatkan solusi optimal.
Himpunan bagian objek yang memberikan keuntungan maksimum adalah {2, 3} dengan total keuntungan adalah 80. Sehingga solusi: X = {0, 1, 1, 0}. 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. Exercise 3.2 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.
4
Assignment Cost Problem
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 6
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: 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
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. 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. 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 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]). 7
References 1. Anany, L. (2003). Introduction to the design and analysis of algorithms. Villanova University. 2. http://www.csd.uoc.gr/ hy583/papers/ch11.pdf 3. [Kol95] Kolman, B. and Beck, R.E. Elementary Linear Programming with Applications, 2nd ed. Academic Press, 1995.
8
