---
title: "Metoda větví a hranic"
source: "https://systems-analysis.info/int/Metoda_v%C4%9Btv%C3%AD_a_hranic"
wiki: "systems-analysis.info/int"
article: "Metoda_větví_a_hranic"
language: "cs"
categories:
  - "Category:Czech"
  - "Category:Operations research"
revision_id: 4312
wiki_created_at: 2026-09-06T23:33:27Z
wiki_modified_at: 2026-09-06T23:33:27Z
downloaded_at: 2026-09-07T23:01:58Z
---

# Metoda větví a hranic

**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<sup>[\[1\]](https://systems-analysis.info/int/Metoda_v%C4%9Btv%C3%AD_a_hranic#cite_note-en-wiki-bnb-1)</sup>. 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í<sup>[\[2\]](https://systems-analysis.info/int/Metoda_v%C4%9Btv%C3%AD_a_hranic#cite_note-ru-wiki-bnb-2)</sup>.

Metoda byla poprvé navržena A. Landem a A. Doigem v roce 1960 pro řešení úloh celočíselného programování<sup>[\[3\]](https://systems-analysis.info/int/Metoda_v%C4%9Btv%C3%AD_a_hranic#cite_note-land-doig-1960-3)</sup>. 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í $S_{i}$ na několik menších, zpravidla disjunktních podmnožin $S_{i1},S_{i2},\ldots,S_{ik}$. 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 \geq U$.
    - Pokud je řešení relaxace přípustné pro původní úlohu, aktualizovat rekord: $U\leftarrow 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)<sup>[\[4\]](https://systems-analysis.info/int/Metoda_v%C4%9Btv%C3%AD_a_hranic#cite_note-conitzer-duke-4)</sup>.
- **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<sup>[\[5\]](https://systems-analysis.info/int/Metoda_v%C4%9Btv%C3%AD_a_hranic#cite_note-maudet-danoy-2024-5)</sup>.

## 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é $x_{j}$ a vytváří dvě podúlohy s dodatečnými omezeními $x_{j} \leq \lfloor x_{j}^{\ast}\rfloor$ a $x_{j} \geq \lceil x_{j}^{\ast}\rceil$.
- **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<sup>[\[6\]](https://systems-analysis.info/int/Metoda_v%C4%9Btv%C3%AD_a_hranic#cite_note-little-1963-6)</sup>.

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

<sup>[\[1\]](https://systems-analysis.info/int/Metoda_v%C4%9Btv%C3%AD_a_hranic#cite_note-en-wiki-bnb-1)</sup> <sup>[\[2\]](https://systems-analysis.info/int/Metoda_v%C4%9Btv%C3%AD_a_hranic#cite_note-ru-wiki-bnb-2)</sup> <sup>[\[3\]](https://systems-analysis.info/int/Metoda_v%C4%9Btv%C3%AD_a_hranic#cite_note-land-doig-1960-3)</sup> <sup>[\[4\]](https://systems-analysis.info/int/Metoda_v%C4%9Btv%C3%AD_a_hranic#cite_note-conitzer-duke-4)</sup> <sup>[\[5\]](https://systems-analysis.info/int/Metoda_v%C4%9Btv%C3%AD_a_hranic#cite_note-maudet-danoy-2024-5)</sup> <sup>[\[6\]](https://systems-analysis.info/int/Metoda_v%C4%9Btv%C3%AD_a_hranic#cite_note-little-1963-6)</sup> \</references\>

1.  <span id="cite_note-en-wiki-bnb-1">↑ <sup>[1.0](https://systems-analysis.info/int/Metoda_v%C4%9Btv%C3%AD_a_hranic#cite_ref-en-wiki-bnb_1-0)</sup> <sup>[1.1](https://systems-analysis.info/int/Metoda_v%C4%9Btv%C3%AD_a_hranic#cite_ref-en-wiki-bnb_1-1)</sup> Wikipedia contributors. (2025). Branch and bound. In *Wikipedia, The Free Encyclopedia*. Retrieved 2025-10-26, from <a href="https://en.wikipedia.org/wiki/Branch_and_bound" class="external free" rel="nofollow">https://en.wikipedia.org/wiki/Branch_and_bound</a></span>
2.  <span id="cite_note-ru-wiki-bnb-2">↑ <sup>[2.0](https://systems-analysis.info/int/Metoda_v%C4%9Btv%C3%AD_a_hranic#cite_ref-ru-wiki-bnb_2-0)</sup> <sup>[2.1](https://systems-analysis.info/int/Metoda_v%C4%9Btv%C3%AD_a_hranic#cite_ref-ru-wiki-bnb_2-1)</sup> Wikipedia contributors. (2023). Метод ветвей и границ. In *Русская Википедия*. Retrieved 2025-10-26, from <a href="https://ru.wikipedia.org/wiki/Метод_ветвей_и_границ" class="external free" rel="nofollow">https://ru.wikipedia.org/wiki/Метод_ветвей_и_границ</a></span>
3.  <span id="cite_note-land-doig-1960-3">↑ <sup>[3.0](https://systems-analysis.info/int/Metoda_v%C4%9Btv%C3%AD_a_hranic#cite_ref-land-doig-1960_3-0)</sup> <sup>[3.1](https://systems-analysis.info/int/Metoda_v%C4%9Btv%C3%AD_a_hranic#cite_ref-land-doig-1960_3-1)</sup> 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: <a href="https://www.jstor.org/stable/1910129" class="external free" rel="nofollow">https://www.jstor.org/stable/1910129</a></span>
4.  <span id="cite_note-conitzer-duke-4">↑ <sup>[4.0](https://systems-analysis.info/int/Metoda_v%C4%9Btv%C3%AD_a_hranic#cite_ref-conitzer-duke_4-0)</sup> <sup>[4.1](https://systems-analysis.info/int/Metoda_v%C4%9Btv%C3%AD_a_hranic#cite_ref-conitzer-duke_4-1)</sup> Conitzer, V. (2008). *Solving (mixed) integer programs using branch and bound*. Duke University, Department of Computer Science. URL: <a href="https://courses.cs.duke.edu/spring08/cps296.2/branch_and_bound.pdf" class="external free" rel="nofollow">https://courses.cs.duke.edu/spring08/cps296.2/branch_and_bound.pdf</a></span>
5.  <span id="cite_note-maudet-danoy-2024-5">↑ <sup>[5.0](https://systems-analysis.info/int/Metoda_v%C4%9Btv%C3%AD_a_hranic#cite_ref-maudet-danoy-2024_5-0)</sup> <sup>[5.1](https://systems-analysis.info/int/Metoda_v%C4%9Btv%C3%AD_a_hranic#cite_ref-maudet-danoy-2024_5-1)</sup> 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: <a href="https://arxiv.org/abs/2412.09444" class="external free" rel="nofollow">https://arxiv.org/abs/2412.09444</a></span>
6.  <span id="cite_note-little-1963-6">↑ <sup>[6.0](https://systems-analysis.info/int/Metoda_v%C4%9Btv%C3%AD_a_hranic#cite_ref-little-1963_6-0)</sup> <sup>[6.1](https://systems-analysis.info/int/Metoda_v%C4%9Btv%C3%AD_a_hranic#cite_ref-little-1963_6-1)</sup> 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: <a href="https://dspace.mit.edu/bitstream/handle/1721.1/46907/branchboundmetho00litt.pdf" class="external free" rel="nofollow">https://dspace.mit.edu/bitstream/handle/1721.1/46907/branchboundmetho00litt.pdf</a></span>