MS Excel

s Řešitelem to nějak taky nezvládám citovat

Ahoj, tak jsem to zkusil pomocí vzorců. Je to jak píše Vovka trochu "kostrbaté" řešení, ale mělo by fungovat. Zkušenější uživatele Exelu to určitě zjednoduší. Jinak ta tvá ukázka mi vyšla jako chybná. citovat

Pokud nemáte v ruce nic chytřejšího, než to moje postupné škrtání, pak máte naprostou pravdu, že "můj" automat skončí tím, že už nesmí smazat ani minimum, ani maximum.
Když ten zbytek nebude moc rozsáhlý, šlo by v něm dál škrtat metodou pokus / omyl. S dobře vymyšlenou rekurzí byste nejspíš zpravidla našel řešení hodně blízké optimu. Pokud je cílem najít hodnotu minimálního rozdílu, tak tu dostanete už v rámci první fáze.
Problém ovšem spočívá v tom, jestli zbytek po "mém" škrtání obsahuje alespoň jedno přípustné řešení. Mohlo by se stát, že zbytek nepůjde plně zredukovat, protože některá ze škrtnutých mezních hodnot musí v úloze zůstat, aby úloha zůstala řešitelná do konce.
Kdysi dávno jsem se optimalizacemi zabýval profesionálně. Už jsem všechno zapomněl, protože od těch časů uběhlo třicet let. Přesto si dovolím dát vám tip: zkuste se zeptat strýčka Google na heslo "branch and bound", případně na variace toho pojmu. Jde o stařičkou, ale velice obecnou metodu hledání optimálního řešení. Metoda dává záruku nalezení optima, pokud dostane na hledání dostatečný čas.citovat

to Johan:
v té ukázce je cyklista který jede do dvou měst a také tam jsou dva, kteří nejedou nikam citovat

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