Metoda větví a mezí
Jako metoda větví a mezí nebo též metoda větví a hranic či B&B, anglicky branch and bound se označuje typ algoritmů v diskrétní a kombinatorické optimalizaci, které při prohledávání stavového prostoru postupují, jako by se jednalo o strom; pro jednotlivé větve reprezentující části prostoru možných řešení odhadují horní a spodní meze cílové funkce, a vylučují větve, ve kterých se na základě těchto odhadů nemůže vyskytovat optimální řešení. Metoda se používá i pro nekonvexní spojitou optimalizace bez omezení. Metoda je implementována například v programu BARON ([1]). Metoda hledá vždy globální řešení optimalizačního problému.
Metodu poprvé navrhly Ailsa Land a A. G. Doig v roce 1960 pro lineární programování.
Typickou úlohou, kde se využívá, je problém batohu.
Související články
- Optimalizace (matematika)
- Alfa-beta ořezávání
![]() | Tento článek je příliš stručný nebo postrádá důležité informace. Pomozte Wikipedii tím, že jej vhodně rozšíříte. Nevkládejte však bez oprávnění cizí texty. |