Omezující podmínky hledání svatého grálu programování

Přes řadu populárních aplikací z oblasti komunikací, grafiky,
multimédií a her zůstávají počítače pořád také nástroji pro
řešení složitých úloh, což ostatně bylo jejich původní poslání.
Snem mnoha generací uživatelů a programátorů je přirozeně zadávat
počítačům pouze co mají řešit, bez nutnosti specifikovat, jak to
mají řešit. Tento styl programování se nazývá deklarativní a jeho
asi nejznámějším představitelem je programovací jazyk Prolog.
Ještě více se k deklarativnímu stylu programování blíží nový směr
tzv. programování s omezujícími podmínkami (anglicky constraint
programming), které je založeno na myšlence, že řešení problémů
většinou spočívá ve výběru optimální varianty z velkého množství
alternativních řešení. Principu omezujících podmínek vlastně
všichni dávno používáme při řešení běžných problémů jako je
plánování času (mám volno až po 18. hodině), hledání vhodné
kombinace oblečení (tahle kravata neladí s touto košilí) nebo
třeba hraní her (křížovky, šachy apod.).

Počátky v umělé inteligenci

Myšlenka využití omezujících podmínek se objevila někdy na
přelomu šedesátých a sedmdesátých let, kdy se v umělé inteligenci
řešily problémy typu analýzy trojrozměrné scény. David Waltz
tehdy navrhl postup, kterým byl počítač schopen z 2D obrázku
získat informace o tvarech a vzájemných vztazích trojrozměrných
objektů na scéně. Použil při tom techniky ohodnocení každé čáry
(= hrana objektu) na obrázku jejím typem (konvexní, resp. konkávní
hrana, okraj, rozhraní stínu), čímž celý problém redukoval na
nalezení konzistentního ohodnocení všech čar (viz obr. 2).
Protože všech možných ohodnocení je poměrně mnoho (u pouhých 10
čar je to 4 10 , tj. kolem milionu) a ani nejrychlejší počítače je
nezvládnou všechny prozkoumat v rozumném čase, bylo potřeba
navrhnout techniky, které počet kombinací výrazně omezí. Tak se
zrodily omezující podmínky, jejichž úkolem je redukovat počet
variant při řešení náročných kombinatorických problémů.

Těžké problémy

Principu omezení počtu možných variant jen na ty přijatelné,
a teprve z nich vybírat optimální řešení, se používá při řešení
řady problémů zvláště v oblasti plánování a rozvrhování.
Představte si jednoduchý problém naplánovat nakládku a vykládku
deseti lodí v pěti přístavištích. Najít optimální plán můžeme
například prozkoumáním všech alternativ, kterých je kolem deseti
milionů (přesně 5 10 ). Na počítači zvládajícím za sekundu projít
10 tisíc možností by to trvalo něco přes čtvrt hodiny. Teď si ale
představte, že vám obchod kvete a vy už máte lodí dvacet
a přístavišť deset (říkáte, že se to nemůže Čechovi stát -- pak se
podívejte na Bahamy). Stejný počítač by nyní o trochu větší
problém řešil přes 300 milionů let a zřejmě by nepomohlo ani
zakoupení akcelerační karty. Již při prvním pohledu na otázku se
samozřejmě zjistí, že řadu možností nemá cenu vůbec zkoumat,
protože např. v dané chvíli nemohou být dvě lodě ve stejném
kotvišti, některá kotviště jsou pro některé lodi malá apod.
Formulací takových přirozených omezujících podmínek se problém
výrazně zredukuje a lze ho řešit na běžných pracovních stanicích
pro stovky lodí a desítky přístavů.

Uživatelská rozhraní

Použití omezujících podmínek dnes stojí i za řadou grafických
uživatelských rozhraní. Všichni jsme si zvykli, že v grafických
editorech můžeme snadno tažením ukazatele vytvářet útvary jako
jsou čtverce, kružnice, hvězdy a spol., jejichž kreslení "od
ruky" by bylo přinejmenším zdržující. Málokdo si ale uvědomuje,
že počítač musí sám dopočítat tvar objektu, a to z poměrně malého
množství informací od uživatele (zpravidla jsou to dva body:
počátek a současná poloha ukazatele). Programování takových
editorů je mnohem jednodušší při použití omezujících podmínek,
které přirozeně a jednoznačně popíší tvar objektu (viz obr. 3).

Praktické aplikace

Omezující podmínky nejsou jen hříčkou univerzitních profesorů,
ale, jak ukázaly předchozí řádky, těží z nich řada praktických
aplikací. Mezi oblastmi použití samozřejmě dominují složité
plánovací, rozvrhovací a optimalizační problémy.
Plánovací software založený na omezujících podmínkách využívají
velké evropské letecké společnosti jako British Airways, Swissair
nebo SAS, kde tyto aplikace pomáhají plánovat lety a přiřazení
posádek. Podobné využití najdeme i ve francouzských (SNCF)
a italských železničních společnostech (a co ČD?), pro plánování
používají principu omezujících podmínek industriální kolosy
Michelin a Dassault, těžební společnosti (Saga Petroleum)
i mezinárodní překladiště (Hong Kong International Terminals).
Systémy založené na omezujících podmínkách najdete v dnes
populární oblasti genetiky a klonování, kde se využívají při
analýze DNA (složit strukturu DNA je jako skládat velkou puzzle).
Často také stojí za intuitivními grafickými uživatelskými
rozhraními, výzkum sponzoruje například Apple Computer.
Oblastí použití omezujících podmínek je tedy celá řada. Za jejich
praktickým nasazením většinou stojí snaha minimalizovat náklady
vytvořením optimálního plánu, a tím se bránit rostoucí
konkurenci. Jak ukazuje příklad úspěšných British Airways, tak to
zabírá.