Korlátozás és szétválasztás

From Systems analysis wiki
Jump to navigation Jump to search

A korlátok és elágazások módszere (angolul Branch and Bound, rövidítve B&B vagy BnB) — egy általános paradigma pontos algoritmusok felépítéséhez diszkrét és kombinatorikus optimalizálási feladatok megoldására, különösen NP-nehéz feladatok esetén[1]. A módszer egy irányított keresési stratégia, amelyben a megengedett megoldások teljes halmaza fokozatosan részhalmazokra bomlik (elágazás), és mindegyikre kiszámításra kerülnek a célfüggvény értékének becslései (korlátok). Ezek a becslések lehetővé teszik azoknak a részhalmazoknak az elvetését (levágását), amelyek biztosan nem tartalmaznak optimális megoldást, ami lényegesen csökkenti a keresési teret[2].

A módszert először A. Land és A. Doig javasolta 1960-ban egészértékű programozási feladatok megoldására[3]. Azóta az operációkutatás és az informatika egyik legalapvetőbb megközelítésévé vált. A módszer legfontosabb jellemzője a rugalmassága: nem egy konkrét algoritmus, hanem egy magas szintű stratégiai séma (keretrendszer), amely alkalmazkodik a megoldandó feladat szerkezetéhez.

A módszer kulcsfontosságú összetevői

A módszer alapját három alapvető művelet képezi, amelyeket a keresési fában szervezett megoldástér-részhalmazokra alkalmaznak.

  • Elágazás (angolul Branching) — ez a megengedett megoldások aktuális halmazának Si rekurzív felosztásának folyamata több kisebb, jellemzően diszjunkt részhalmazra Si1,Si2,…,Sik. Minden ilyen részhalmaz egy új részfeladatnak felel meg, és a keresési fában gyermekcsúcsként jelenik meg. Például egészértékű programozási feladatokban az elágazás gyakran azon változó szerint történik, amelynek töredékes értéke van az LP-relaxáció megoldásában.
  • Korlátbecslés (angolul Bounding) — a keresési fa minden csúcsára (azaz minden részfeladatra) kiszámításra kerül a célfüggvény értékének becslése. Minimalizálási feladat esetén ez az alsó korlát (lower bound), amely garantált alsó becslést jelent az adott részhalmazban lévő bármely megoldásra. Ezt a becslést leggyakrabban az eredeti részfeladat relaxációjának megoldásával kapjuk — egy egyszerűsített változatban, amelyben egyes nehéz feltételeket (például az egészértékűséget) ideiglenesen figyelmen kívül hagyunk. A legelterjedtebb az LP-relaxáció.
  • Levágás (angolul Pruning) — ez a csúcsok (és a nekik megfelelő teljes részfák) kizárásának folyamata, amelyek biztosan nem tartalmazhatnak optimális megoldást. Egy csúcsot az alábbi esetekben vágunk le:
  1. Levágás korlát alapján: Az adott csúcs alsó korlátja nem jobb (azaz minimalizálási feladatnál nagyobb vagy egyenlő), mint a jelenleg talált legjobb megengedett megoldás értéke, amelyet rekordnak (incumbent) nevezünk.
  2. Levágás megengedhetőség alapján: A csúcs relaxációjának megoldása megengedett az eredeti feladatban (például minden változó egészértékű). Ezt a megoldást összehasonlítjuk az aktuális rekorddal, és ha jobb, a rekordot frissítjük. Ebből a csúcsból nem szükséges további elágazás.
  3. Levágás megoldhatatlanság alapján: A csúcsnak megfelelő részfeladatnak nincs megengedett megoldása.

Általános algoritmus

A korlátok és elágazások módszerének általánosított algoritmusa minimalizálási feladatra a következő lépésekkel írható le:

  1. Inicializálás: Megkeresni egy kezdeti megengedett megoldást (például heurisztika segítségével), és annak értékét kezdeti felső korlátként (rekordként) beállítani U. Létrehozni az aktív csúcsok várólistáját Q, amely a gyökércsúcsot (az eredeti feladatot) tartalmazza.
  2. Főciklus: Amíg a várólista Q nem üres:
    • Kiválasztani egy csúcsot a Q-ból a keresési stratégiának megfelelően (például mélységi vagy legjobb becslés szerinti keresés).
    • Megoldani az adott csúcs relaxációját, megkapva az alsó korlátot L.
    • Levágni a csúcsot, ha L≥U.
    • Ha a relaxáció megoldása megengedett az eredeti feladatban, frissíteni a rekordot: U←L.
    • Ha a csúcs nem lett levágva és a megoldás nem megengedett, elágazást végrehajtani, felosztva azt gyermekcsúcsokra, és hozzáadni azokat a várólistához Q.
  3. Befejezés: Amikor a várólista Q üressé válik, az algoritmus befejeződik. A rekordnak U megfelelő talált megoldás globálisan optimális.

Kulcstulajdonságok és tételek

  • Helyesség és konvergencia: Az algoritmus garantáltan megtalálja a globálisan optimális megoldást véges számú lépésben, ha a megengedett megoldások halmaza véges, és az elágazási eljárás konvergens (azaz rekurzív felosztás során a részhalmazok pontokká "húzódnak össze")[4].
  • Keresési stratégia: Az algoritmus hatékonysága nagymértékben függ a következő elágaztatandó csúcs kiválasztási stratégiájától (például mélységi keresés, szélességi keresés, legjobb becslés szerinti keresés) és az elágaztatáshoz választott változótól. A modern megoldók gyakran hibrid stratégiákat alkalmaznak[5].

Példák

  • Egészértékű programozási feladat: A módszer klasszikus alkalmazása. Relaxációként lineáris programozást alkalmazunk. Az elágazás a töredékes értékű változó xj szerint történik, két részfeladatot hozva létre további feltételekkel xj≤⌊xj*⌋ és xj≥⌈xj*⌉.
  • Az utazó ügynök feladata: A megoldástér a gráfban lévő összes Hamilton-kör. Az elágazás éleken keresztül valósítható meg (él bevétele/kizárása az útvonalból). Alsó korlátokként egyszerűbb feladatok megoldásai használhatók, mint például a hozzárendelési feladat vagy a minimális feszítőfa meghatározása[6].

Kapcsolódó fogalmak és alkalmazások

  • Elágazás és metszés módszere (Branch-and-Cut): Hibrid módszer, amely a B&B-t a metszősíkok módszerével ötvözi. A keresési fa minden csúcsán a relaxáció megoldásán kívül további egyenlőtlenségeket (metszéseket) generálunk, amelyek erősítik az alsó korlátot, ami hatékonyabb áglevágáshoz vezet.
  • Visszalépéses keresés (Backtracking): A korlátok és elágazások módszere tekinthető ezen algoritmus általánosításának optimalizálási feladatokra.
  • Alfa-béta vágás: Fogalmi analógia, amelyet játékfákban alkalmaznak a biztosan vesztes ágak levágására.

Lásd még

  • Egészértékű programozás
  • Kombinatorikus optimalizálás
  • Az utazó ügynök feladata
  • NP-nehéz feladat
  • Szimplex-módszer

Megjegyzések

[1] [2] [3] [4] [5] [6] </references>

  1. ↑ 1.0 1.1 Wikipedia contributors. (2025). Branch and bound. In Wikipedia, The Free Encyclopedia. Retrieved 2025-10-26, from https://en.wikipedia.org/wiki/Branch_and_bound
  2. ↑ 2.0 2.1 Wikipedia contributors. (2023). Метод ветвей и границ. In Русская Википедия. Retrieved 2025-10-26, from https://ru.wikipedia.org/wiki/Метод_ветвей_и_границ
  3. ↑ 3.0 3.1 Land, A. H.; Doig, A. G. (1960). An automatic method of solving discrete programming problems. Econometrica, 28(3), 497–520. DOI: 10.2307/1910129. URL: https://www.jstor.org/stable/1910129
  4. ↑ 4.0 4.1 Conitzer, V. (2008). Solving (mixed) integer programs using branch and bound. Duke University, Department of Computer Science. URL: https://courses.cs.duke.edu/spring08/cps296.2/branch_and_bound.pdf
  5. ↑ 5.0 5.1 Maudet, G.; Danoy, G. (2024). Search Strategy Generation for Branch and Bound Using Genetic Programming. arXiv preprint arXiv:2412.09444. DOI: 10.48550/arXiv.2412.09444. URL: https://arxiv.org/abs/2412.09444
  6. ↑ 6.0 6.1 Little, J. D. C.; Murty, K. G.; Sweeney, D. W.; Karel, C. (1963). An Algorithm for the Traveling Salesman Problem. Operations Research, 11(6), 972–989. DOI: 10.1287/opre.11.6.972. URL: https://dspace.mit.edu/bitstream/handle/1721.1/46907/branchboundmetho00litt.pdf
Retrieved from "https://systems-analysis.ru/int/index.php?title=Korlátozás_és_szétválasztás&oldid=17065"