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 typ algoritmů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í.

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[editovat | editovat zdroj]