Metoda větví a mezí

Metoda větví a mezí (angl. Branch and bound - BB) je obecný algoritmus v lineárním programování pro hledání optimálních řešení různých optimalizačních problémů, zvláště v diskrétní optimalizaci a kombinatorické optimalizaci. Princip metody je v systematickém procházení všech potenciálních řešení, přičemž velké podmnožiny nevhodných kandidátů jsou vyloučeny najednou. Při prořezávání se využívá horní a dolní odhad hodnoty, která se optimalizuje a tyto odhady se v průběhu výpočtu zpřesňují.

Metodu poprvé navrhli A. H. Land a A. G. Doig v roku 1960 pro lineární programování.

Související články

• Optimalizace (matematika)
• Alfa-beta ořezávání využívá tento princip při procházení stromu hry