--- title: "Korlátozás és szétválasztás" source: "https://systems-analysis.info/int/Korl%C3%A1toz%C3%A1s_%C3%A9s_sz%C3%A9tv%C3%A1laszt%C3%A1s" wiki: "systems-analysis.info/int" article: "Korlátozás_és_szétválasztás" language: "hu" categories: - "Category:Hungarian" - "Category:Operations research" revision_id: 3489 wiki_created_at: 2026-09-06T23:21:35Z wiki_modified_at: 2026-09-06T23:21:35Z downloaded_at: 2026-09-07T22:57:15Z --- # Korlátozás és szétválasztás **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\]](https://systems-analysis.info/int/Korl%C3%A1toz%C3%A1s_%C3%A9s_sz%C3%A9tv%C3%A1laszt%C3%A1s#cite_note-en-wiki-bnb-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\]](https://systems-analysis.info/int/Korl%C3%A1toz%C3%A1s_%C3%A9s_sz%C3%A9tv%C3%A1laszt%C3%A1s#cite_note-ru-wiki-bnb-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\]](https://systems-analysis.info/int/Korl%C3%A1toz%C3%A1s_%C3%A9s_sz%C3%A9tv%C3%A1laszt%C3%A1s#cite_note-land-doig-1960-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 $S_{i}$ rekurzív felosztásának folyamata több kisebb, jellemzően diszjunkt részhalmazra $S_{i1},S_{i2},\ldots,S_{ik}$. 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 \geq U$. - Ha a relaxáció megoldása megengedett az eredeti feladatban, frissíteni a rekordot: $U\leftarrow 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\]](https://systems-analysis.info/int/Korl%C3%A1toz%C3%A1s_%C3%A9s_sz%C3%A9tv%C3%A1laszt%C3%A1s#cite_note-conitzer-duke-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\]](https://systems-analysis.info/int/Korl%C3%A1toz%C3%A1s_%C3%A9s_sz%C3%A9tv%C3%A1laszt%C3%A1s#cite_note-maudet-danoy-2024-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ó $x_{j}$ szerint történik, két részfeladatot hozva létre további feltételekkel $x_{j} \leq \lfloor x_{j}^{\ast}\rfloor$ és $x_{j} \geq \lceil x_{j}^{\ast}\rceil$. - **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\]](https://systems-analysis.info/int/Korl%C3%A1toz%C3%A1s_%C3%A9s_sz%C3%A9tv%C3%A1laszt%C3%A1s#cite_note-little-1963-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\]](https://systems-analysis.info/int/Korl%C3%A1toz%C3%A1s_%C3%A9s_sz%C3%A9tv%C3%A1laszt%C3%A1s#cite_note-en-wiki-bnb-1) [\[2\]](https://systems-analysis.info/int/Korl%C3%A1toz%C3%A1s_%C3%A9s_sz%C3%A9tv%C3%A1laszt%C3%A1s#cite_note-ru-wiki-bnb-2) [\[3\]](https://systems-analysis.info/int/Korl%C3%A1toz%C3%A1s_%C3%A9s_sz%C3%A9tv%C3%A1laszt%C3%A1s#cite_note-land-doig-1960-3) [\[4\]](https://systems-analysis.info/int/Korl%C3%A1toz%C3%A1s_%C3%A9s_sz%C3%A9tv%C3%A1laszt%C3%A1s#cite_note-conitzer-duke-4) [\[5\]](https://systems-analysis.info/int/Korl%C3%A1toz%C3%A1s_%C3%A9s_sz%C3%A9tv%C3%A1laszt%C3%A1s#cite_note-maudet-danoy-2024-5) [\[6\]](https://systems-analysis.info/int/Korl%C3%A1toz%C3%A1s_%C3%A9s_sz%C3%A9tv%C3%A1laszt%C3%A1s#cite_note-little-1963-6) \ 1. ↑ [1.0](https://systems-analysis.info/int/Korl%C3%A1toz%C3%A1s_%C3%A9s_sz%C3%A9tv%C3%A1laszt%C3%A1s#cite_ref-en-wiki-bnb_1-0) [1.1](https://systems-analysis.info/int/Korl%C3%A1toz%C3%A1s_%C3%A9s_sz%C3%A9tv%C3%A1laszt%C3%A1s#cite_ref-en-wiki-bnb_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](https://systems-analysis.info/int/Korl%C3%A1toz%C3%A1s_%C3%A9s_sz%C3%A9tv%C3%A1laszt%C3%A1s#cite_ref-ru-wiki-bnb_2-0) [2.1](https://systems-analysis.info/int/Korl%C3%A1toz%C3%A1s_%C3%A9s_sz%C3%A9tv%C3%A1laszt%C3%A1s#cite_ref-ru-wiki-bnb_2-1) Wikipedia contributors. (2023). Метод ветвей и границ. In *Русская Википедия*. Retrieved 2025-10-26, from https://ru.wikipedia.org/wiki/Метод_ветвей_и_границ 3. ↑ [3.0](https://systems-analysis.info/int/Korl%C3%A1toz%C3%A1s_%C3%A9s_sz%C3%A9tv%C3%A1laszt%C3%A1s#cite_ref-land-doig-1960_3-0) [3.1](https://systems-analysis.info/int/Korl%C3%A1toz%C3%A1s_%C3%A9s_sz%C3%A9tv%C3%A1laszt%C3%A1s#cite_ref-land-doig-1960_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](https://systems-analysis.info/int/Korl%C3%A1toz%C3%A1s_%C3%A9s_sz%C3%A9tv%C3%A1laszt%C3%A1s#cite_ref-conitzer-duke_4-0) [4.1](https://systems-analysis.info/int/Korl%C3%A1toz%C3%A1s_%C3%A9s_sz%C3%A9tv%C3%A1laszt%C3%A1s#cite_ref-conitzer-duke_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](https://systems-analysis.info/int/Korl%C3%A1toz%C3%A1s_%C3%A9s_sz%C3%A9tv%C3%A1laszt%C3%A1s#cite_ref-maudet-danoy-2024_5-0) [5.1](https://systems-analysis.info/int/Korl%C3%A1toz%C3%A1s_%C3%A9s_sz%C3%A9tv%C3%A1laszt%C3%A1s#cite_ref-maudet-danoy-2024_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](https://systems-analysis.info/int/Korl%C3%A1toz%C3%A1s_%C3%A9s_sz%C3%A9tv%C3%A1laszt%C3%A1s#cite_ref-little-1963_6-0) [6.1](https://systems-analysis.info/int/Korl%C3%A1toz%C3%A1s_%C3%A9s_sz%C3%A9tv%C3%A1laszt%C3%A1s#cite_ref-little-1963_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