Metoda větví a mezí

Z Wikipedie, otevřené encyklopedie
Skočit na navigaci Skočit na vyhledávání

Jako metoda větví a mezí nebo též metoda větví a hranic či B&B, anglicky branch and bound, se označuje obecný algoritmuslineá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í (prohledávání stavového prostoru), 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í. Typickou úlohou, kde se využívá, je problém batohu.

Metodu poprvé navrhly Ailsa Land a A. G. Doig v roce 1960 pro lineární programování.

Související články[editovat | editovat zdroj]