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á.