A kombinatorikus optimalizálás egy matematikai megközelítés, amely diszkrét vagy véges struktúrák (például gráfok, permutációk, halmazok) optimalizálásával foglalkozik. A cél általában egy adott kritérium szerint “legjobb” megoldás megtalálása egy véges megoldástérben.
A dinamikus programozás egy népszerű megközelítés a kombinatorikus optimalizálásra.
def knapsack(values, weights, capacity):
n = len(values)
dp = * (capacity + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
for w in range(1, capacity + 1):
if weights <= w:
dp = max(dp, dp] + values)
else:
dp = dp
return dp
# Példa
values =
weights =
capacity = 50
print(f"A maximális érték: {knapsack(values, weights, capacity)}")
A itertools.permutations segítségével egyszerűen generálhatjuk az összes lehetséges útvonalat.
import itertools
def tsp_bruteforce(graph):
n = len(graph)
vertices = range(n)
min_path = float("inf")
for perm in itertools.permutations(vertices):
current_path_weight = sum(graph]] for i in range(n - 1))
current_path_weight += graph]]
min_path = min(min_path, current_path_weight)
return min_path
# Példa gráf (szimmetrikus mátrix)
graph = [
,
,
,
]
print(f"Minimális útvonal hossza: {tsp_bruteforce(graph)}")
A NetworkX könyvtárat használhatjuk gráf-alapú optimalizálási problémákra.
import networkx as nx
def max_flow_example():
G = nx.DiGraph()
G.add_edge('A', 'B', capacity=10)
G.add_edge('A', 'C', capacity=5)
G.add_edge('B', 'C', capacity=15)
G.add_edge('B', 'D', capacity=10)
G.add_edge('C', 'D', capacity=10)
G.add_edge('C', 'E', capacity=10)
G.add_edge('D', 'E', capacity=10)
flow_value, flow_dict = nx.maximum_flow(G, 'A', 'E')
print(f"Maximális áram: {flow_value}")
print("Árameloszlás:", flow_dict)
max_flow_example()
A SciPy könyvtár különböző kombinatorikus optimalizálási problémák megoldására használható, például lineáris programozásra.
from scipy.optimize import linprog
# Célfüggvény: Minimalizáljuk c^T * x
c = # Maximalizáláshoz a célfüggvényt negatívra állítjuk.
# Egyenlőtlenségi korlátok: Ax <= b
A = , ]
b =
# Nemnegatív korlátok: x >= 0
x_bounds = (0, None)
res = linprog(c, A_ub=A, b_ub=b, bounds=(x_bounds, x_bounds), method='highs')
print("Optimalizált célfüggvény érték:", -res.fun)
print("Megoldás:", res.x)
A kombinatorikus optimalizálás problémái széles körben alkalmazhatók, és Pythonban számos hatékony eszköz áll rendelkezésre: 1. Alap algoritmusok (dinamikus programozás, brute force): Alkalmas kisebb problémákhoz. 2. Specializált könyvtárak (NetworkX, SciPy): Nagyobb méretű és gyakorlati alkalmazásokhoz ideális. 3. Heurisztikus megoldások (genetikus algoritmusok, szimulált lehűlés): Ha a teljes keresési tér átvizsgálása nem lehetséges.
Az optimális módszer kiválasztása mindig a konkrét problémától és annak méretétől függ.