Exhaustive search
Pencarian solusi terbaik dari objek-objek dengan criteria tertentu dengan menggunakan algoritma Exhaustive Search adalah dengan mencari semua kombinasi dan permutasi dari objek-objek yang ada. Semakin banyak objek, semakin banyak juga kemungkinan solusinya. Biasanya kompleksitas waktu dari algoritma Exhaustive Search masi heksponensial, sehingga algoritma ini cenderung untuk di hindari walaupun solusi yang ditemukan adalah solusi yang memangbenar-benar terbaik. Untuk mempercepat pencarian solusi dengan Exhaustive Search dapat digunakan suatu teknik yang disebut teknik heuristik (heuristic). Teknik ini meliputi salah satunya adalah mengeliminasi kemungkinan solusi yang tidak mungkin menjadi solusi terbaik, ataupun mengadopsi metode lain.
Pencarian solusi terbaik dari objek-objek dengan criteria tertentu dengan menggunakan algoritma Exhaustive Search adalah dengan mencari semua kombinasi dan permutasi dari objek-objek yang ada. Semakin banyak objek, semakin banyak juga kemungkinan solusinya. Biasanya kompleksitas waktu dari algoritma Exhaustive Search masi heksponensial, sehingga algoritma ini cenderung untuk di hindari walaupun solusi yang ditemukan adalah solusi yang memangbenar-benar terbaik. Untuk mempercepat pencarian solusi dengan Exhaustive Search dapat digunakan suatu teknik yang disebut teknik heuristik (heuristic). Teknik ini meliputi salah satunya adalah mengeliminasi kemungkinan solusi yang tidak mungkin menjadi solusi terbaik, ataupun mengadopsi metode lain.
Exhaustive search adalah teknik pencarian solusi secara solusi brute force untuk masalah yang melibatkan pencarian elemen dengan sifat khusus, biasanya di antara objek-objek kombinatorik seperti permutasi, kombinasi, atau himpunan bagian dari sebuah himpunan.
Metode exhaustive search dapat dirumuskan langkah-langkahnya sebagai berikut:
1.Enumerasi (list) setiap solusi yang mungkin dengan cara yang sistematis.
2.Evaluasi setiap kemungkinan solusi satu per satu, mungkin saja beberapa kemungkinan solusi yang tidak layak dikeluarkan, dan simpan solusi terbaik yang ditemukan sampai sejauh ini (the best solusi found so far).
3.Bila pencarian berakhir, umumkan solusi terbaik (the winner).
Metode exhaustive search dapat dirumuskan langkah-langkahnya sebagai berikut:
1.Enumerasi (list) setiap solusi yang mungkin dengan cara yang sistematis.
2.Evaluasi setiap kemungkinan solusi satu per satu, mungkin saja beberapa kemungkinan solusi yang tidak layak dikeluarkan, dan simpan solusi terbaik yang ditemukan sampai sejauh ini (the best solusi found so far).
3.Bila pencarian berakhir, umumkan solusi terbaik (the winner).
Beberapa contoh masalah dengan penyelesaian exhaustive search
1.
Misalkan kita mempunyai tiga pelanggan dengan
t1 = 5, t2 = 10, t3 = 3,
maka enam urutan pelayanan yang mungkin adalah:
Urutan T
=================================
1, 2, 3: 5 + (5 + 10) + (5 + 10 + 3 ) = 38
1, 3, 2: 5 + (5 + 3) + (5 + 3 + 10) = 31
2, 1, 3: 10 + (10 + 5) + (10 + 5 + 3) = 43
2, 3, 1: 10 + (10 + 3) + (10 + 3 + 5) = 41
3, 1, 2: 3 + (3 + 5) + (3 + 5 + 10) = 29 ¬ (optimal)
3, 2, 1: 3 + (3 + 10) + (3 + 10 + 5) = 34
Penyeleseian dengan Exhaustive search,
– Urutkan pelanggan yang dilayani oleh server merupakan suatu permutasi.
– Jika n orang pelangan, maka terdapat n! urutan pelanggan.
– Untuk mengevaluasi fungsi obyektif : O(n).
– Kompleksitas algoritma exhaustive search = O(nn!).
Algoritma,
C : input himpunan_pelanggan
S : himpunan_pelanggan
I : pelanggan
S {}
While ( C != {} ) do
I pelanggan yang mempunyai t[i] terkecil
C C – {i}
S S {i}
Endwhile
Return S
2.
Masalah penukaran uang
Nilai uang yang ditukar : A, himpunan koin (multiset) : {d1,d2,…,dn}, himpunan solusi : X={x1,x2,…,xn}, xi = 1 jika di dipilih, xi = 0 jika di tidak dipilih.
Penyeleseian dengan Exhaustive search,
– Terdapat 2n kemungkinan solusi ( nilai-nilai X = {x1,x2,…,xn}).
– Untuk mengevaluasi fungsi obyektif = O(n).
– Kompleksitas algoritma exhaustive search seluruhnya = O( n.2n )
Algoritma,
S : himpunan_koin
x : koin
S = {}
while ((jumlah semua nilai koin di dalam S) !=A) and (C != {} ) do
x = koin yang mempunyai nilai terbesar
C = C – {x}
if (((jumlah semua nilai koin di dalam S) + nilai koin x) kurang dari sama dengan A)
then S = S {x}
Endifend while
if ((jumlah semua nilai koin di dalam S) = A )
then return S
else write(‘tidak ada solusi’)
endif
3.
Diberikan n buah objek dan sebuah knapsack dengan kapasitas tertentu (K). Setiap objek memilki property bobot w(weight) dan keuntungan p(profit). Objektif persoalan adalah bagaimana memilih objek-objek yang dimasukkan ke dalam knapsack sehingga tidak melebihi kapasitas knapsack namun memaksimumkan total keuntungan yang diperoleh.”
Langkah -langkahnya adalah:
Misalkan terdapat n objek yang memiliki profit dan berat masing-masing Dan kapasitas knapsack sebanyak Maks.
Cari himpunan bagian dari n objek
Uji jumlah berat dari himpunan bagian tersebut. Jika beratnya melebihi kapasitas, kembali ke nomor 2. Jika tidak, lanjut ke nomer 3
Uji jumlah profit dari himpunan bagian tersebut. Jika profitnya melebihi profit maksimal sementara, simpan profit baru sebagai profit maksimal dan himpunan bagiannya. Jika tidak, kembali ke nomor 2.
Jika seluruh himpunan bagian sudah diuji, himpunan bagian dengan profit maksimal terakhir adalah solusi terbaik dari knapsack
Contoh soal
Tinjau persoalan 0/1 Knapsack dengan n = 4. Misalkan objek-objek tersebut kita beri nomor 1, 2, 3, dan 4. Properti setiap objek i dan kapasitas knapsack adalah sebagai berikut
w1 = 2; p1 = 20
w2 = 5; p1 = 30
w3 = 10; p1 = 50
w4 = 5; p1 = 10
Kapasitas knapsack W = 16
Langkah-langkah pencarian solusi 0/1 Knapsack secara exhaustive search dirangkum dalam tabel di bawah ini:
1.
Misalkan kita mempunyai tiga pelanggan dengan
t1 = 5, t2 = 10, t3 = 3,
maka enam urutan pelayanan yang mungkin adalah:
Urutan T
=================================
1, 2, 3: 5 + (5 + 10) + (5 + 10 + 3 ) = 38
1, 3, 2: 5 + (5 + 3) + (5 + 3 + 10) = 31
2, 1, 3: 10 + (10 + 5) + (10 + 5 + 3) = 43
2, 3, 1: 10 + (10 + 3) + (10 + 3 + 5) = 41
3, 1, 2: 3 + (3 + 5) + (3 + 5 + 10) = 29 ¬ (optimal)
3, 2, 1: 3 + (3 + 10) + (3 + 10 + 5) = 34
Penyeleseian dengan Exhaustive search,
– Urutkan pelanggan yang dilayani oleh server merupakan suatu permutasi.
– Jika n orang pelangan, maka terdapat n! urutan pelanggan.
– Untuk mengevaluasi fungsi obyektif : O(n).
– Kompleksitas algoritma exhaustive search = O(nn!).
Algoritma,
C : input himpunan_pelanggan
S : himpunan_pelanggan
I : pelanggan
S {}
While ( C != {} ) do
I pelanggan yang mempunyai t[i] terkecil
C C – {i}
S S {i}
Endwhile
Return S
2.
Masalah penukaran uang
Nilai uang yang ditukar : A, himpunan koin (multiset) : {d1,d2,…,dn}, himpunan solusi : X={x1,x2,…,xn}, xi = 1 jika di dipilih, xi = 0 jika di tidak dipilih.
Penyeleseian dengan Exhaustive search,
– Terdapat 2n kemungkinan solusi ( nilai-nilai X = {x1,x2,…,xn}).
– Untuk mengevaluasi fungsi obyektif = O(n).
– Kompleksitas algoritma exhaustive search seluruhnya = O( n.2n )
Algoritma,
S : himpunan_koin
x : koin
S = {}
while ((jumlah semua nilai koin di dalam S) !=A) and (C != {} ) do
x = koin yang mempunyai nilai terbesar
C = C – {x}
if (((jumlah semua nilai koin di dalam S) + nilai koin x) kurang dari sama dengan A)
then S = S {x}
Endifend while
if ((jumlah semua nilai koin di dalam S) = A )
then return S
else write(‘tidak ada solusi’)
endif
3.
Diberikan n buah objek dan sebuah knapsack dengan kapasitas tertentu (K). Setiap objek memilki property bobot w(weight) dan keuntungan p(profit). Objektif persoalan adalah bagaimana memilih objek-objek yang dimasukkan ke dalam knapsack sehingga tidak melebihi kapasitas knapsack namun memaksimumkan total keuntungan yang diperoleh.”
Langkah -langkahnya adalah:
Misalkan terdapat n objek yang memiliki profit dan berat masing-masing Dan kapasitas knapsack sebanyak Maks.
Cari himpunan bagian dari n objek
Uji jumlah berat dari himpunan bagian tersebut. Jika beratnya melebihi kapasitas, kembali ke nomor 2. Jika tidak, lanjut ke nomer 3
Uji jumlah profit dari himpunan bagian tersebut. Jika profitnya melebihi profit maksimal sementara, simpan profit baru sebagai profit maksimal dan himpunan bagiannya. Jika tidak, kembali ke nomor 2.
Jika seluruh himpunan bagian sudah diuji, himpunan bagian dengan profit maksimal terakhir adalah solusi terbaik dari knapsack
Contoh soal
Tinjau persoalan 0/1 Knapsack dengan n = 4. Misalkan objek-objek tersebut kita beri nomor 1, 2, 3, dan 4. Properti setiap objek i dan kapasitas knapsack adalah sebagai berikut
w1 = 2; p1 = 20
w2 = 5; p1 = 30
w3 = 10; p1 = 50
w4 = 5; p1 = 10
Kapasitas knapsack W = 16
Langkah-langkah pencarian solusi 0/1 Knapsack secara exhaustive search dirangkum dalam tabel di bawah ini:
Himpunan bagian objek yang memberikan keuntungan maksimum adalah {2, 3} dengan total keuntungan adalah 80.
Solusi persoalan 0/1 Knapsack di atas adalah X = {0, 1, 1, 0}
Berapa banyak himpunan bagian dari sebuah himpunan dengan n elemen? Jawab adalah 2n. Ini berarti, algoritma exhaustive search untuk persoalan 0/1 Knapsack mempunyai kompleksitas O(2n).
0/1 Knapsack adalah contoh persoalan yang mempunyai kompleksitas algoritma eksponensial. Knapsack digolongkan sebagai persoalan NP (Non-deterministic Polynomial), karena tidak mungkin dapat ditemukan algoritma polinomial untuk memecahkannya.
Solusi persoalan 0/1 Knapsack di atas adalah X = {0, 1, 1, 0}
Berapa banyak himpunan bagian dari sebuah himpunan dengan n elemen? Jawab adalah 2n. Ini berarti, algoritma exhaustive search untuk persoalan 0/1 Knapsack mempunyai kompleksitas O(2n).
0/1 Knapsack adalah contoh persoalan yang mempunyai kompleksitas algoritma eksponensial. Knapsack digolongkan sebagai persoalan NP (Non-deterministic Polynomial), karena tidak mungkin dapat ditemukan algoritma polinomial untuk memecahkannya.
Himpunan bagian total bobot total keuntungan
{} 0 0
{1} 2 20
{2} 5 30
{3} 10 50
{4} 5 10
{1,2} 7 50
{1,3} 12 70
{1,4} 7 30
{2,3} 15 80
{2,4} 10 40
{3,4} 15 60
{1,2,3} 17 tidak layak
{1,2,4} 12 60
{1,3,4} 17 tidak layak
{2,3,4} 20 tidak layak
{1,2,3,4} 22 tidak layak
{} 0 0
{1} 2 20
{2} 5 30
{3} 10 50
{4} 5 10
{1,2} 7 50
{1,3} 12 70
{1,4} 7 30
{2,3} 15 80
{2,4} 10 40
{3,4} 15 60
{1,2,3} 17 tidak layak
{1,2,4} 12 60
{1,3,4} 17 tidak layak
{2,3,4} 20 tidak layak
{1,2,3,4} 22 tidak layak
Sumber :blog.ub.ac.id
