Wikiszótár

ládapakolási probléma

Magyar

Kiejtés

  • IPA: [ ˈlaːdɒpɒkolaːʃiprobleːmɒ]

Főnév

ládapakolási probléma

  1. (matematika, algoritmusok, számításelmélet)

Ládapakolási probléma (Bin Packing Problem)

A ládapakolási probléma egy NP-nehéz kombinatorikus optimalizációs probléma. A cél az, hogy egy adott tárgyhalmazt úgy helyezzük el fix méretű ládákba (konténerekbe), hogy a felhasznált ládák száma minimális legyen.


Probléma formális megfogalmazása

  • Adott:
    • Egy ( S ) tárgyhalmaz, ahol minden tárgy mérete ( s_i ) (( 0 < s_i )).
    • Ládák (konténerek), amelyek kapacitása 1.
  • Cél:
    • A tárgyakat úgy helyezzük el a ládákba, hogy a ládák száma minimális legyen.


Megoldási stratégiák

  1. Heurisztikus algoritmusok (gyors, de nem garantáltan optimális):
    • First Fit: A tárgyat az első olyan ládába helyezzük, amelybe belefér.
    • Best Fit: A tárgyat abba a ládába helyezzük, amelyben a legkevesebb hely marad, de még belefér.
    • Next Fit: Csak az aktuálisan nyitott ládába próbálunk pakolni, és ha nem fér bele, nyitunk egy újat.
  2. Exakt algoritmusok (optimális megoldás, de lassabb):
    • Dinamikus programozás.
    • Branch and Bound technika.
  3. Metaheurisztikák:
    • Genetikus algoritmusok.
    • Szimulált lehűlés (Simulated Annealing).


Python implementáció - First Fit algoritmus

Az alábbi implementáció a First Fit algoritmust mutatja be, amely egyszerű, de hatékony megoldást kínál a ládapakolási problémára. 

def first_fit(items, bin_capacity=1.0):
    """
    First Fit algoritmus a ládapakolási problémára.

    :param items: A tárgyak listája (méretekkel).
    :param bin_capacity: A ládák kapacitása (alapértelmezett: 1.0).
    :return: A ládák tartalma.
    """
    bins = []  # Lista a ládákról, amelyek tartalmazzák a tárgyakat

    for item in items:
        placed = False
        # Próbáljuk elhelyezni a tárgyat a már nyitott ládák egyikébe
        for b in bins:
            if sum(b) + item <= bin_capacity:
                b.append(item)
                placed = True
                break
        # Ha nem találtunk helyet, nyitunk egy új ládát
        if not placed:
            bins.append([item])

    return bins

# Példa használat
items = [0.4, 0.7, 0.2, 0.5, 0.6, 0.3, 0.8, 0.2]
print("Tárgyak mérete:", items)

# Ládapakolás futtatása
result = first_fit(items)

# Eredmény kiírása
print("\nLádák tartalma:")
for i, b in enumerate(result):
    print(f"Láda {i + 1}: {b}")

print(f"\nFelhasznált ládák száma: {len(result)}")

Kimenet

Példa bemeneti adatokkal: 

Tárgyak mérete: [0.4, 0.7, 0.2, 0.5, 0.6, 0.3, 0.8, 0.2]

Ládák tartalma:
Láda 1: [0.4, 0.2, 0.3]
Láda 2: [0.7, 0.2]
Láda 3: [0.5, 0.3]
Láda 4: [0.6]
Láda 5: [0.8]

Felhasznált ládák száma: 5

Elemzés

  1. First Fit algoritmus:
    • Időbonyolultság: ( O(n m) ), ahol ( n ) a tárgyak száma, ( m ) a ládák száma.
    • Heurisztikus módszer: Nem mindig adja meg az optimális megoldást.
  2. Optimalizáció:
    • Ha a tárgyakat csökkenő sorrendben helyezzük a ládákba (First Fit Decreasing), az eredmény gyakran közelebb áll az optimálishoz.


First Fit Decreasing (FFD) algoritmus

def first_fit_decreasing(items, bin_capacity=1.0):
    """First Fit Decreasing algoritmus."""
    items_sorted = sorted(items, reverse=True)
    return first_fit(items_sorted, bin_capacity)

# Példa használat
result_ffd = first_fit_decreasing(items)

print("\nFFD algoritmus - Ládák tartalma:")
for i, b in enumerate(result_ffd):
    print(f"Láda {i + 1}: {b}")

print(f"\nFelhasznált ládák száma (FFD): {len(result_ffd)}")

Kimenet (FFD)

FFD algoritmus - Ládák tartalma:
Láda 1: [0.8, 0.2]
Láda 2: [0.7, 0.3]
Láda 3: [0.6, 0.4]
Láda 4: [0.5, 0.2]

Felhasznált ládák száma (FFD): 4

Összefoglalás

  1. Ládapakolási probléma:
    • Cél: A tárgyak minimális számú ládába helyezése.
    • Nehézség: NP-nehéz probléma.
  2. Algoritmusok:
    • First Fit: Egyszerű és gyors.
    • First Fit Decreasing (FFD): Optimalizált változat, amely gyakran jobb eredményt ad.
  3. Python implementáció:
    • Heurisztikus módszerekkel gyorsan közelítő megoldás érhető el.

Az FFD algoritmus gyakorlati esetekben jól használható, mivel gyors és jó közelítő megoldást ad.

Fordítások

Tartalom

További információk

A lap eredeti címe: „https://hu.wiktionary.org/w/index.php?title=ládapakolási_probléma&oldid=3480713”