BRANCH AND BOUND
•
Metode
Branch and Bound adalah sebuah teknik algoritma yang secara khusus mempelajari
bagaimana caranya memperkecil Search Tree menjadi sekecil mungkin.
•
Sesuai
dengan namanya, metode ini terdiri dari 2 langkah yaitu :
–
Branch yang
artinya membangun semua cabang tree yang mungkin menuju solusi.
–
Bound yang artinya menghitung node mana yang merupakan active node (E-node)
dan node mana yang merupakan dead node (D-node) dengan menggunakan syarat batas
constraint (kendala).
TEKNIK
BRANCH AND BOUND
•
FIFO Branch
and Bound
–
Adalah
teknik Branch and Bound yang menggunakan bantuan queue untuk perhitungan Branch
and Bound secara First In First Out.
•
LIFO Branch
and Bound
–
Adalah
teknik Branch and Bound yang menggunakan bantuan stack untuk perhitungan Branch
and Bound secara Last In First Out.
•
Least Cost
Branch and Bound
–
Teknik ini
akan menghitung cost setiap node. Node yang memiliki cost paling kecil
dikatakan memiliki kemungkinan paling besar menuju solusi.
MASALAH YANG
DAPAT DIPECAHKAN
•
Branch and
Bound dapat digunakan untuk memecahkan berbagai masalah yang menggunakan Search
Tree
–
Traveling
Salesman Problem
–
N-Queen Problem
–
15 Puzzle
Problem
–
0/1 Knapsack
Problem
-Shortest
Path
Algoritma Brute Force
Algoritma Brute Force adalah sebuah pendekatan
yang lempang
(straightforward) untuk memecahkan
suatu
masalah, biasanya didasarkan pada pernyataan
masalah
(problem statement) dan definisi konsep
yang
dilibatkan.
Prinsip
– prinsip algoritma brute force untuk
menyelesaikan
persoalan Integer Knapsack ialah:
1) Mengenumerasikan semua himpunan bagian
dari solusi.
2) Mengevaluasi total keuntungan dari
setiap
himpunan
bagian dari langkah pertama
3) Pilih himpunan bagian yang mempunyai total
keuntungan
terbesar
Algoritma Greedy
Secara
harfiah, greedy berarti rakus atau tamak.
Algoritma Greedy
merupakan algoritma sedarhana
dan lempang
yang paling populer untuk pemecahan
persoalan optimasi (maksimum atau minimum).
Prinsip greedy
adalah: “take what you can get
now!”, yang
digunakan dalam konteks positif.
Ada tiga
pendekatan dalam menyelesaikan
persoalan Integer Knapsack dengan algoritma
Greedy:
1) Greedy by profit.
Pada setiap
langkah, knapsack diisi dengan objek
yang
mempunyai keuntungan terbesar. Strategi ini
mencoba
memaksimumkan keuntungan dengan
memilih
objek yang paling menguntungkan terlebih
dahulu.
2) Greedy by weight.
Pada setiap
langkah, knapsack diisi dengan objek
yang
mempunyai berat paling ringan. Strategi
ini
mencoba
memaksimumkan keuntungan dengan
memasukkan
sebanyak mungkin objek ke dalam
knapsack.
3) Greedy by density.
Pada setiap
langkah, knapsack diisi dengan objek
yang
mempunyai densitas, pi /wi
terbesar. Strategi
ini
mencoba memaksimumkan keuntungan dengan
memilih
objek yang mempunyai keuntungan per unit
berat
terbesar.
Algoritma Dynamic Programming
Program
Dinamis (dynamic programming): metode
pemecahan
masalah dengan cara menguraikan solusi
menjadi sekumpulan langkah (step) atau tahapan
(stage)
sedemikian sehingga solusi dari persoalan
dapat
dipandang dari serangkaian
keputusan yang
saling
berkaitan.
Pada
penyelesaian persoalan dengan metode ini:
(1) terdapat sejumlah berhingga pilihan yang
mungkin,
(2) solusi pada setiap tahap dibangun dari hasil
solusi tahap
sebelumnya,
(3) kita menggunakan persyaratan
optimasi dan
kendala
untuk membatasi sejumlah pilihan yang
harus
dipertimbangkan pada suatu tahap.
Dua pendekatan yang digunakan dalam
Dynamic
Progamming adalah maju (forward atau up-down)
dan mundur
(backward atau bottom-up).
Misalkan x1,
x2, …, xn menyatakan peubah (variable)
keputusan yang harus dibuat masing-masing untuk
tahap 1, 2,
…, n. Maka,
a. Program dinamis maju: Program dinamis
bergerak
mulai dari tahap 1, terus maju ke tahap 2, 3, dan seterusnya sampai tahap n. Runtunan
peubah
keputusan adalah x1, x2, …, xn.
b. Program dinamis mundur: Program dinamis
bergerak
mulai dari tahap n, terus mundur ke
tahap n – 1,
n – 2, dan seterusnya sampai tahap
1. Runtunan peubah keputusan adalah
xn, xn-1,
…, x1.
Secara umum, ada empat langkah yang dilakukan
dalam mengembangkana algoritma program
dinamis:
1. Karakteristikkan struktur solusi optimal.
2. Definisikan secara rekursif nilai solusi
optimal.
3. Hitung nilai solusi optimal secara maju atau
mundur.
4. Konstruksi solusi optimal.
Algoritma Divide and Conquer
Algoritma divide and conquer sudah lama diperkenalkan
sebagai sumber dari
pengendalian
proses paralel, karena masalah-masalah yang terjadi dapat diatasi
secara
independen. Banyak arsitektur dan bahasa pemrograman paralel mendesain
implementasinya
(aplikasi) dengan struktur dasar dari algoritma divide and conquer.
Untuk
menyelesaikan masalah-masalah yang besar, dan dibagi (dipecah) menjadi
bagian yang
lebih kecil dan menggunakan sebuah solusi untuk menyelesaikan
problem awal
adalah prinsip dasar dari pemrograman/strategi divide and conquer.
Sumber : Herman Teknik
Written by Unknown
We are Creative Blogger Theme Wavers which provides user friendly, effective and easy to use themes. Each support has free and providing HD support screen casting.
0 komentar:
Posting Komentar