Ez egy oszd meg és uralkodj típusú algoritmus, amely hatékonyan csökkenti a keresési tér méretét felső- és alsó becslések (bound) segítségével.
BranchAndBound(root):
inicializálj egy üres prioritásos sort (Q)
helyezd a gyökércsomópontot Q-ba
legjobb_megoldás = ∞
amíg Q nem üres:
csomópont = Q legjobb elemének kivétele
ha csomópont alsó becslése ≥ legjobb_megoldás:
folytasd (pruning)
ha csomópont terminális és jobb megoldás, mint legjobb_megoldás:
legjobb_megoldás = csomópont értéke
különben:
oszd fel a csomópontot alcsomópontokra
számíts alsó és felső becslést az alcsomópontokra
helyezd az alcsomópontokat Q-ba
térj vissza legjobb_megoldás
Példa a hátizsák probléma (Knapsack Problem) megoldására:
class Node:
def __init__(self, level, profit, weight, bound):
self.level = level # Az aktuális elem szintje
self.profit = profit # Az aktuális haszon
self.weight = weight # Az aktuális súly
self.bound = bound # Az aktuális csomópont felső korlátja
def knapsack_bound(node, capacity, weights, profits, n):
if node.weight >= capacity:
return 0 # Ha a súly meghaladja a kapacitást, nincs haszon
bound = node.profit
total_weight = node.weight
j = node.level + 1
while j < n and total_weight + weights <= capacity:
total_weight += weights
bound += profits
j += 1
if j < n:
bound += (capacity - total_weight) * (profits / weights)
return bound
def knapsack_branch_and_bound(capacity, weights, profits):
n = len(weights)
items = sorted(range(n), key=lambda i: profits / weights, reverse=True)
weights = for i in items]
profits = for i in items]
queue =
root = Node(-1, 0, 0, 0)
root.bound = knapsack_bound(root, capacity, weights, profits, n)
queue.append(root)
max_profit = 0
while queue:
current_node = queue.pop(0)
if current_node.level == n - 1:
continue
next_level = current_node.level + 1
# 1. Ha a következő elem szerepel
include = Node(
next_level,
current_node.profit + profits,
current_node.weight + weights,
0
)
if include.weight <= capacity and include.profit > max_profit:
max_profit = include.profit
include.bound = knapsack_bound(include, capacity, weights, profits, n)
if include.bound > max_profit:
queue.append(include)
# 2. Ha a következő elem nem szerepel
exclude = Node(next_level, current_node.profit, current_node.weight, 0)
exclude.bound = knapsack_bound(exclude, capacity, weights, profits, n)
if exclude.bound > max_profit:
queue.append(exclude)
return max_profit
# Példa használat
capacity = 50
weights =
profits =
max_profit = knapsack_branch_and_bound(capacity, weights, profits)
print(f"Maximális haszon: {max_profit}")
Kimenet:
Maximális haszon: 220
Példa a hátizsák probléma megoldására:
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
struct Node {
int level;
int profit;
int weight;
double bound;
Node(int lvl, int prof, int wt, double bnd)
: level(lvl), profit(prof), weight(wt), bound(bnd) {}
};
bool cmp(pair<double, int> a, pair<double, int> b) {
return a.first > b.first;
}
double knapsack_bound(Node node, int capacity, vector<int>& weights, vector<int>& profits, int n) {
if (node.weight >= capacity) return 0;
double bound = node.profit;
int total_weight = node.weight;
int j = node.level + 1;
while (j < n && total_weight + weights <= capacity) {
total_weight += weights;
bound += profits;
j++;
}
if (j < n) {
bound += (capacity - total_weight) * ((double)profits / weights);
}
return bound;
}
int knapsack_branch_and_bound(int capacity, vector<int>& weights, vector<int>& profits) {
int n = weights.size();
vector<pair<double, int>> ratios(n);
for (int i = 0; i < n; ++i) {
ratios = {(double)profits / weights, i};
}
sort(ratios.begin(), ratios.end(), cmp);
vector<int> sorted_weights(n), sorted_profits(n);
for (int i = 0; i < n; ++i) {
sorted_weights = weights.second];
sorted_profits = profits.second];
}
queue<Node> q;
Node root(-1, 0, 0, 0);
root.bound = knapsack_bound(root, capacity, sorted_weights, sorted_profits, n);
q.push(root);
int max_profit = 0;
while (!q.empty()) {
Node current = q.front();
q.pop();
if (current.level == n - 1) continue;
int next_level = current.level + 1;
Node include(next_level, current.profit + sorted_profits, current.weight + sorted_weights, 0);
if (include.weight <= capacity && include.profit > max_profit) {
max_profit = include.profit;
}
include.bound = knapsack_bound(include, capacity, sorted_weights, sorted_profits, n);
if (include.bound > max_profit) {
q.push(include);
}
Node exclude(next_level, current.profit, current.weight, 0);
exclude.bound = knapsack_bound(exclude, capacity, sorted_weights, sorted_profits, n);
if (exclude.bound > max_profit) {
q.push(exclude);
}
}
return max_profit;
}
int main() {
int capacity = 50;
vector<int> weights = {10, 20, 30};
vector<int> profits = {60, 100, 120};
int max_profit = knapsack_branch_and_bound(capacity, weights, profits);
cout << "Maximális haszon: " << max_profit << endl;
return 0;
}
Kimenet:
Maximális haszon: 220