Metoda branch and bound sama o sobě je velmi prostá. Jiná otázka je, v jakém vědeckém trojobalu ji dnes na internetu prezentují. O její průhlednosti svědčí to, že jsem si celou metodu bez velkých potíží vybavil, a to jsem lhal se třiceti roky. Z výzkumáku jsem odešel v roce 1975, takže optimalizace už nedělám ne třicet, ale čtyřicet let...
Na své sekernické řešení úlohy jsem se šel ještě jednou podívat a s překvapením jsem zjistil, že na první fázi škrtání extrémů lze plynule navázat. Když v tabulce zůstanou bílé hodnoty, znamená to, že každou z nich mohu bez narušení podmínek úlohy smazat; jak v řádku, tak ve sloupci zatím je pro její smazání prostor. Teprve kdyby smazáním nepodbarvené hodnoty došlo k nepřípustnému podbarvení jiných hodnot, pak by nastala skutečná chyba a musel bych se vrátit krok zpátky. Konkrétně v našem příkladu mi po první fázi zbyly nepodbarvené hodnoty C4, D6 a C9. Jejich postupné mazání nezpůsobilo žádnou poruchu, takže tím nakonec vzniklo zdravé a úplné řešení případu.
Netvrdím, že by to takhle dobře nutně dopadlo pokaždé, ale ta druhá fáze stojí za povšimnutí.
Vzpomínka na moji výzkumnickou éru ve mně probudila zájem o tu úlohu. Nevylučuji, že pro ni vytvořím optimalizační algoritmus s využitím zmíněné metody branch and bound. To na počest naší tehdejší skupině matematických metod a Jirkovi Kubátovi, na kterého jsem si dnes se slzou v oku vzpomněl...
Ale to až jestli na mne přijde ta správná "sedmá chuť".
citovat