Metoda větví a hranic

From Systems analysis wiki
Jump to navigation Jump to search

Metoda větví a hranic (angl. Branch and Bound, zkr. B&B nebo BnB) — je obecná paradigma konstrukce přesných algoritmů pro řešení úloh diskrétní a kombinatorické optimalizace, zejména NP-těžkých úloh[1]. Metoda představuje strategii řízeného prohledávání, při níž je celá množina přípustných řešení postupně rozdělována na podmnožiny (větvení), a pro každou z nich jsou vypočítávány odhady (hranice) hodnoty účelové funkce. Tyto odhady umožňují vyřazovat (odřezávat) ty podmnožiny, které zjevně nemohou obsahovat optimální řešení, což podstatně zmenšuje prostor prohledávání[2].

Metoda byla poprvé navržena A. Landem a A. Doigem v roce 1960 pro řešení úloh celočíselného programování[3]. Od té doby se stala jedním z nejzákladnějších přístupů v operačním výzkumu a informatice. Klíčovou vlastností metody je její flexibilita: není konkrétním algoritmem, ale vysokoúrovňovým strategickým schématem (frameworkem), přizpůsobitelným struktuře řešené úlohy.

Klíčové komponenty metody

Základem metody jsou tři fundamentální operace, které se aplikují na podmnožiny prostoru řešení organizované ve formě stromu prohledávání.

  • Větvení (angl. Branching) — je proces rekurzivního dělení aktuální množiny přípustných řešení Si na několik menších, zpravidla disjunktních podmnožin Si1,Si2,…,Sik. Každá taková podmnožina odpovídá nové podúloze a je reprezentována jako podřízený uzel ve stromu prohledávání. Například v úlohách celočíselného programování se větvení provádí podle proměnné, která má v řešení LP-relaxace zlomkovou hodnotu.
  • Odhad hranic (angl. Bounding) — pro každý uzel stromu prohledávání (tj. pro každou podúlohu) je vypočítán odhad hodnoty účelové funkce. Pro úlohu minimalizace je to dolní hranice (lower bound), která je garantovaným odhadem zdola pro libovolné řešení v dané podmnožině. Nejčastěji se tento odhad získává řešením relaxace původní podúlohy — zjednodušené verze, v níž jsou některá složitá omezení (například celočíselnosti) dočasně ignorována. Nejrozšířenější je LP-relaxace.
  • Odřezávání (angl. Pruning) — je proces vyloučení uzlů (a odpovídajících celých podstromů) z dalšího uvažování, pokud zjevně nemohou obsahovat optimální řešení. Uzel je odříznut v jednom z následujících případů:
  1. Odřezání podle hranice: Dolní hranice pro daný uzel není lepší (tj. je větší nebo rovna pro úlohu minimalizace) než hodnota aktuálně nejlepšího nalezeného přípustného řešení, označovaného jako rekord (incumbent).
  2. Odřezání podle přípustnosti: Řešení relaxace uzlu je přípustné pro původní úlohu (například všechny proměnné jsou celočíselné). Toto řešení je porovnáno s aktuálním rekordem a pokud je lepší, rekord je aktualizován. Další větvení z tohoto uzlu není třeba.
  3. Odřezání podle nepřípustnosti: Podúloha odpovídající uzlu nemá přípustná řešení.

Obecný algoritmus

Obecný algoritmus metody větví a hranic pro úlohu minimalizace lze popsat následujícími kroky:

  1. Inicializace: Nalézt počáteční přípustné řešení (například pomocí heuristiky) a nastavit jeho hodnotu jako počáteční horní hranici (rekord) U. Vytvořit frontu aktivních uzlů Q obsahující kořenový uzel (původní úlohu).
  2. Hlavní cyklus: Dokud fronta Q není prázdná:
    • Vybrat uzel z Q v souladu se strategií prohledávání (například prohledávání do hloubky nebo podle nejlepšího odhadu).
    • Vyřešit relaxaci pro tento uzel a získat dolní hranici L.
    • Odříznou uzel, pokud L≥U.
    • Pokud je řešení relaxace přípustné pro původní úlohu, aktualizovat rekord: U←L.
    • Pokud uzel nebyl odříznut a řešení není přípustné, provést větvení, rozdělit jej na podřízené uzly a přidat je do fronty Q.
  3. Ukončení: Když se fronta Q vyprázdní, algoritmus skončí. Nalezené řešení odpovídající rekordu U je globálně optimální.

Klíčové vlastnosti a věty

  • Korektnost a konvergence: Algoritmus garantovaně nalezne globálně optimální řešení v konečném počtu kroků, pokud je množina přípustných řešení konečná a procedura větvení je konvergentní (tj. při rekurzivním dělení se podmnožiny „smršťují" k bodům)[4].
  • Strategie prohledávání: Efektivita algoritmu silně závisí na strategii výběru dalšího uzlu k větvení (například prohledávání do hloubky, do šířky, podle nejlepšího odhadu) a na výběru proměnné pro větvení. Moderní řešiče často používají hybridní strategie[5].

Příklady

  • Úloha celočíselného programování: Klasická aplikace metody. Jako relaxace se používá lineární programování. Větvení probíhá podle zlomkové proměnné xj a vytváří dvě podúlohy s dodatečnými omezeními xj≤⌊xj*⌋ a xj≥⌈xj*⌉.
  • Problém obchodního cestujícího: Prostor řešení tvoří všechny možné Hamiltonovy cykly v grafu. Větvení může probíhat podle hran (zahrnout/vyloučit hranu z trasy). Jako dolní hranice mohou být použita řešení jednodušších úloh, jako je přiřazovací úloha nebo konstrukce minimální kostry grafu[6].

Související pojmy a aplikace

  • Metoda větví a řezů (Branch-and-Cut): Hybridní metoda kombinující B&B s metodou řezných rovin. V každém uzlu stromu prohledávání jsou kromě řešení relaxace generována dodatečná nerovnicová omezení (řezy), která zpřesňují dolní hranici, což vede k efektivnějšímu odřezávání větví.
  • Prohledávání s navracením (Backtracking): Metodu větví a hranic lze chápat jako zobecnění tohoto algoritmu pro optimalizační úlohy.
  • Alfa-beta odřezávání: Konceptuální analogie používaná v herních stromech pro odřezávání zjevně prohraných větví.

Viz také

  • Celočíselné programování
  • Kombinatorická optimalizace
  • Problém obchodního cestujícího
  • NP-těžká úloha
  • Simplexová metoda

Poznámky

[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=Metoda_větví_a_hranic&oldid=17057"