Wikiszótár

kombinatorikus optimalizálás

Magyar

Kiejtés

  • IPA: [ ˈkombinɒtorikuʃoptimɒlizaːlaːʃ]

Főnév

kombinatorikus optimalizálás

  1. (matematika, kombinatorika, operációkutatás)

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.


Probléma példák

  1. Utazó ügynök problémája (TSP): Egy gráf csomópontjait kell bejárni úgy, hogy a teljes út hossza minimális legyen.
  2. Hátizsák probléma (Knapsack Problem): Adott értékű és súlyú tárgyakat kell elhelyezni egy hátizsákban, amely korlátozott kapacitású, úgy, hogy az érték maximális legyen.
  3. Maximális áram problémája: Egy gráf adott forrásából egy célig maximalizáljuk a szállítható áramot.


1. Hátizsák probléma Pythonban

A dinamikus programozás egy népszerű megközelítés a kombinatorikus optimalizálásra.

Dinamikus programozási megoldás

def knapsack(values, weights, capacity):
    n = len(values)
    dp = [[0] * (capacity + 1) for _ in range(n + 1)]

    for i in range(1, n + 1):
        for w in range(1, capacity + 1):
            if weights[i - 1] <= w:
                dp[i][w] = max(dp[i - 1][w], dp[i - 1][w - weights[i - 1]] + values[i - 1])
            else:
                dp[i][w] = dp[i - 1][w]

    return dp[n][capacity]


# Példa
values = [60, 100, 120]
weights = [10, 20, 30]
capacity = 50
print(f"A maximális érték: {knapsack(values, weights, capacity)}")

2. Utazó ügynök problémája (TSP) Pythonban

Brute Force megközelítés

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[perm[i]][perm[i + 1]] for i in range(n - 1))
        current_path_weight += graph[perm[-1]][perm[0]]
        min_path = min(min_path, current_path_weight)

    return min_path


# Példa gráf (szimmetrikus mátrix)
graph = [
    [0, 10, 15, 20],
    [10, 0, 35, 25],
    [15, 35, 0, 30],
    [20, 25, 30, 0]
]
print(f"Minimális útvonal hossza: {tsp_bruteforce(graph)}")

3. Maximális áram problémája Pythonban

A NetworkX könyvtárat használhatjuk gráf-alapú optimalizálási problémákra.

Példa: Edmonds-Karp algoritmus

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()

4. Kombinatorikus optimalizálás: Scipy optimalizáló

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.

Lineáris programozási példa

from scipy.optimize import linprog

# Célfüggvény: Minimalizáljuk c^T * x
c = [-1, -2]  # Maximalizáláshoz a célfüggvényt negatívra állítjuk.

# Egyenlőtlenségi korlátok: Ax <= b
A = [[2, 1], [1, 1]]
b = [20, 16]

# 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)

Összegzés

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.

Fordítások

Tartalom

További információk

A lap eredeti címe: „https://hu.wiktionary.org/w/index.php?title=kombinatorikus_optimalizálás&oldid=3480167”