ALGORITMA BRANCH AND BOUND PADA JAVA
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 :
1. Branch yang artinya membangun semua cabang tree yang mungkin menuju solusi.
2. 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
Ada beberapa teknik dalam Branch and Bound yaitu:
1. FIFO Branch and Bound
Adalah teknik Branch and Bound yang menggunakan bantuan queue untuk perhitungan Branch and Bound secara First In First Out.
2. LIFO Branch and Bound
Adalah teknik Branch and Bound yang menggunakan bantuan stack untuk perhitungan Branch and Bound secara Last In First Out.
3. 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 DENGAN ALGORITMA BRANCH AND BOUND
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
PENGGUNAAN PADA TEKNIK BRANCH AND BOUND
FIFO BRANCH AND BOUND
Menggunakan queue :
1. E-node dimasukkan ke dalam queue, kemudian dibangun branch (cabang) berikutnya.
2. D-node tidak digunakan untuk membangun branch berikutnya.
3. Didapatkan Partial Space Tree yang dicari.
LIFO BRANCH AND BOUND
Menggunakan stack :
1. E-node dimasukkan ke dalam stack, kemudian dibangun branch (cabang) berikutnya.
2. D-node tidak digunakan untuk membangun branch berikutnya.
3. Didapatkan Partial Space Tree yang dicari.
LEAST COST BRANCH AND BOUND
Pada teknik FIFO dan LIFO node dibuka sesuai urutannya. Pada LC Branch and Bound node yang memiliki cost terendah dibuka terlebih dulu (menjadi E-node berikutnya).
Pada sebuah node x berlaku b ≤ c(x) ≤ u
- b adalah batas bawah
- c(x) adalah cost node x
- u adalah batas atas
Jika terjadi b > u maka simpul x dapat dimatikan (dinyatakan sebagai D-node).
Contoh LC Branch and Bound yaitu Traveling Salesman Problem dapat dipecahkan dengan Least Cost Branch and Bound
Langkah-langkah penyelesaian
- Gambarkan problem dengan weigthed digraph G={V,E}
- C(i,j) = nilai (cost) pada edge <i,j>, dimana C(i,j)= ∞ , jika tidak ada edge antara i dan j.
- Dengan definisi nilai (cost) di atas, bangun Cost Matrix dari TSP.
- Lakukan reduksi terhadap Cost Matrix, didapat Reduced Cost Matrix.
- Gunakan fungsi pembatas (bound), untuk membangun Search Tree dari Reduced Cost Matrix.
- Dan seterusnya hingga didapat set solusi yang diinginkan.
Impelementasinya Pada Java
package com.sanfoundry.hardgraph;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Scanner;
public class BranchandBound
{
static int[][] wt; // Matrix of edge
// weights
static String[] city; // Vector of city
// names
static int n; // Dimension for wt
// and city
static ArrayList<Tour> soln = new ArrayList<Tour>();
static int bestTour; // Initialized in
// init()
static int blocked; // Ditto
static boolean DEBUG = true; // Show
// accept/reject
// decisions
static boolean VERBOSE = true; // Show all tours
// discovered
@SuppressWarnings("rawtypes")
private static class Tour implements Comparable
{
int[] soln;
int index; // In branch-and-bound, start of variable
int dist;
static int nTours = 0;
// Best-first based on dist, or DFS based on maxheap of index
static boolean DFS = true;
static boolean DBG = true;
/*
* Presumable edges up to [index-1] have been verified before
* this constructor has been called. So compute the fixed
* distance from [0] up to [index-1] as dist.
*/
private Tour(int[] vect, int index, int[][] wt)
{
dist = 0;
for (int k = 1; k < index; k++)
// Add edges
dist += wt[vect[k - 1]][vect[k]];
if (index == n)
dist += wt[vect[n - 1]][vect[0]]; // Return edge
soln = new int[n]; // Deep copy
System.arraycopy(vect, 0, soln, 0, n);
this.index = index; // Index to permute
nTours++; // Count up # of tours
if (DBG)
System.out.printf("Idx %d: %s\n", index, toString());
}
public int compareTo(Object o)
{
Tour rt = (Tour) o;
int c1 = rt.index - this.index, c2 = this.dist - rt.dist;
if (DFS)
return c1 == 0 ? c2 : c1;
else
return c2;
}
public String toString()
{
StringBuilder val = new StringBuilder(city[soln[0]]);
for (int k = 1; k < n; k++)
val.append(", " + city[soln[k]]);
val.append(", " + city[soln[0]]);
val.append(String.format(" for %d", dist));
return val.toString();
}
}
private static void init(Scanner inp)
{
int sub1, sub2;
String line;
n = inp.nextInt();
wt = new int[n][n];
city = new String[n];
// Initially, there are NO edges; hence -1.
for (sub1 = 0; sub1 < n; sub1++)
Arrays.fill(wt[sub1], -1);
inp.nextLine(); // Discard rest of first line
for (sub1 = 0; sub1 < n; sub1++)
city[sub1] = inp.nextLine();
Arrays.sort(city); // Just to be sure (binarySearch)
inp.nextLine(); // Discard blank spacing line;
blocked = 0; // Accumulate ALL weights for upper bound
while (inp.hasNext())
{
int head, tail;
int dist;
String src, dst;
line = inp.nextLine(); // E.g.: "George" "Pasco" 91
// Chop out the double-quoted substrings.
head = line.indexOf('"') + 1;
tail = line.indexOf('"', head);
src = line.substring(head, tail);
head = line.indexOf('"', tail + 1) + 1;
tail = line.indexOf('"', head);
dst = line.substring(head, tail);
dist = Integer.parseInt(line.substring(tail + 1).trim());
sub1 = Arrays.binarySearch(city, src);
sub2 = Arrays.binarySearch(city, dst);
wt[sub1][sub2] = wt[sub2][sub1] = dist;
blocked += dist;
}
blocked += blocked; // Double the total
bestTour = blocked; // And initialize bestTour
}
// Used below in generating permutations.
private static void swap(int[] x, int p, int q)
{
int tmp = x[p];
x[p] = x[q];
x[q] = tmp;
}
// Generate the available tours by branch-and-bound.
// Generate the initial permutation vector, then save that state
// as the first examined in the branch-and-bound.
public static void tour()
{
int[] vect = new int[n];
int start;
Queue<Tour> work = new PriorityQueue<Tour>();
// First permutation vector.
for (int k = 0; k < n; k++)
vect[k] = k;
start = Arrays.binarySearch(city, "Spokane");
if (start >= 0)
{
vect[start] = 0;
vect[0] = start;
}
work.add(new Tour(vect, 1, wt));
while (!work.isEmpty()) // Branch-and-bound loop
{
Tour current = work.poll();
int index = current.index;
vect = current.soln;
if (index == n) // I.e., Full permutation vector
{
if (wt[vect[n - 1]][vect[0]] > 0) // Return edge?
{
if (current.dist < bestTour) // Better than earlier?
{// Save the state in the list
bestTour = current.dist;
soln.add(current);
if (DEBUG)
System.out.println("Accept " + current);
}
else if (DEBUG)
System.out.println("Too long: " + current);
}
else if (DEBUG)
System.out.println("Invalid: " + current);
}
else
// Continue generating permutations
{
int k; // Loop variable
int hold; // Used in regenerating the original state
for (k = index; k < n; k++)
{
swap(vect, index, k);
if (wt[vect[index - 1]][vect[index]] < 0)
continue;
work.add(new Tour(vect, index + 1, wt));
}
// Restore original permutation
hold = vect[index];
for (k = index + 1; k < n; k++)
vect[k - 1] = vect[k];
vect[n - 1] = hold;
}
}
}
@SuppressWarnings("unchecked")
public static void main(String[] args) throws Exception
{
String filename = args.length == 0 ? "RoadSet.txt" : args[0];
Scanner inp = new Scanner(new java.io.File(filename));
System.out.println("Data read from file " + filename);
init(inp);
tour();
if (VERBOSE)
{
System.out.println("Tours discovered:");
for (Tour opt : soln)
System.out.println(opt);
}
if (soln.size() == 0)
{
System.out.println("NO tours discovered. Exiting.");
System.exit(0);
}
System.out.println(Tour.nTours + " Tour objects generated.");
Collections.sort(soln);
System.out.println("Best tour: ");
System.out.println(soln.get(0));
}
}
Berikut pembahasan mengenai Algoritma Branch and Bound semoga bisa membantu rekan-rekan bloger semua.
Nama : Muhammad Dandy
NPM : 19316004
Kelas : TK19B
Universitas : https://teknokrat.ac.id/
Fakultas : http://ftik.teknokrat.ac.id/
Komentar
Posting Komentar