Algoritmus ohraničeného větvení
Umožňuje stanovit optimální množinu proměnných za předpokladu, že kriteriální funkce pro selekci proměnných je monotónní. Označíme-li množinu proměnných, pak monotónnost kriteriální funkce znamená, že pro množiny
|
(9) |
splňuje selekční kriteriální funkce vztah
|
(10) |
Pro popis algoritmu uvažme případ selekce dvou proměnných z původních pěti. Všechny možné alternativy vyloučení tří proměnných z výchozí množiny ukazuje graf na Obr.3. Každý uzel v grafu vyjadřuje eliminaci jedné označené proměnné.
Obr.3: Graf algoritmu ohraničeného větvení - selekce 2 z 5 |
Předpokládejme, že vyhodnocujeme hodnotu zvolené kriteriální funkce v každém uzlu stromu, přičemž postupujeme shora dolů a zleva doprava, a srovnáváme ji s dosud nejlepší (největší) dosaženou hodnotou, kterou označíme . Pokud je okamžitá hodnota kriteriální funkce větší než , je stále šance, že optimální řešení bude nalezeno na právě analyzované větvi grafu, a proto bude hledání pokračovat po nejlevější dosud neanalyzované větvi. Jestliže dosáhneme konce větve a odpovídající hodnota selekčního kritéria je větší než , pak tento uzel definuje novou optimální množinu proměnných a modifikujeme hodnotu . Naopak, jestliže je v některém uzlu grafu hodnota selekčního kritéria menší než , pak větve začínající v tomto uzlu nemá smysl dále prohledávat, protože díky monotónnosti kritéria budou jeho hodnoty v dalších uzlech již jenom menší.
Efektivnost prohledávání se ještě zvětší, jestliže se bude výběr odstraňované veličiny na dané úrovni stromu provádět podle změny hodnoty kriteriální funkce a bude se postupovat tím směrem, kde je změna kriteriální funkce nejmenší.
Příklad 5:
Jsou-li jednotlivé uzly algoritmu ohraničeného větvení pro selekci 2 z 5 ohodnoceny hodnotami kriteriální funkce podle Obr.4, určete cestu procházení grafu algoritmu, využije-li se základní formy algoritmu.
Obr.4: Ohodnocený graf algoritmu ohraničeného větvení pro selekci 2 z 5 (příklad 5) |
Řešení:
Postupujeme z kořenového uzlu přes uzly , do , = 12. Návratem přes uzel do uzlu , resp. (v obou případech je hodnota kriteriální funkce rovna 10, tj. menší než ). Návrat do uzlu a pak postup do uzlu . Hodnota kriteriální funkce je rovna 14, tj. je větší než , lze tedy pokračovat na nižší úroveň do uzlu , resp. . V tomto uzlu je hodnota kriteriální funkce větší než dosavadní hodnota , proto dojde k její modifikaci na = 13. Návrat přes uzel do uzlu . Zde již je hodnota kriteriální funkce menší než současná hodnota , není proto třeba pokračovat větví dále. Následuje postup přes kořenový uzel do větve začínající uzlem . Kriteriální funkce je zde menší než , proto není potřeba pokračovat v prohlížení větve do nižších úrovní. Po návratu přes kořenový uzel pokračujeme do větve začínající uzlem . Protože kriteriální funkce nabývá větší hodnoty než , lze pokračovat dále. V následujícím uzlu je však hodnota kriteriální funkce menší než , proto prohledávání grafu končí. Optimální je tedy odstranění proměnných , a , a tudíž výsledkem je selekce proměnných a .