KSVI MFF UK Praha

Jin´ e programov´ an´ı Tomáˇs Holan [email protected] KSVI MFF UK Praha

Abstrakt V prvn´ım roˇcn´ıku studia informatiky na MFF UK Praha vˇsichni studenti absolvuj´ı u ´vodn´ı kurs programov´ an´ı. V tomto kursu se sezn´ am´ı se z´ akladn´ımi pojmy, algoritmy, datov´ ymi strukturami, technikami a se zp˚ usobem, jak analyzovat u ´lohu shora. Posledn´ı pˇredn´ aˇska tohoto kursu potom b´ yv´ a vˇenov´ ana tomu, jak ˇreˇsit u ´lohy, které jsou pro takov´ y zp˚ usob programov´ an´ı pˇr´ıliˇs tˇeˇzké. Tento text shrnuje obsah této posledn´ı pˇredn´ aˇsky. Postupnˇe jsou pˇredkl´ ad´ any problémy, které jsou pro obvykl´ y postup pˇr´ıliˇs sloˇzité a jsou demonstrov´ any alternativn´ı zp˚ usoby jejich ˇreˇsen´ı.

1

,,Klasick´ e” programov´ an´ı

Jako klasické programov´ an´ı chápeme takové zp˚ usoby programován´ı, jaké jsou vyuˇcov´ any v z´ akladn´ıch kursech na vysok´ ych ˇskolách a jaké dobˇre vystihuje origin´ aln´ı n´ azev knihy [1]: ,,Algorithms + Data Structures = Programs”. Tento zp˚ usob je charakteristick´ y snahou pochopit problém, rozdˇelit jeho ˇreˇsen´ı na menˇs´ı ˇc´ asti podle postupu ˇreˇsen´ı nebo podle r˚ uzn´ ych pˇr´ıpad˚ u hodnot vstupn´ıch dat a tyto ˇcásti potom ˇreˇsit pomoc´ı urˇcité standardn´ı v´ ybavy algoritm˚ u (vyhled´ av´ an´ı, tˇr´ıdˇen´ı...), meta-algoritm˚ u (rekurse, dynamické programov´ an´ı) a datov´ ych struktur. Nˇekteré u ´lohy jsou ovˇsem na tento postup pˇr´ıliˇs obt´ıˇzné, veliké, neuchopitelné. V n´ asleduj´ıc´ıch kapitol´ ach si ukáˇzeme nˇekolik takov´ ych u ´loh spolu s návody, jak je ˇreˇsit ,,jinak”.

2

Probl´ em na u ´ vod: Vodovodn´ı baterie

P´ akov´ a vodovodn´ı baterie obsahuje dvˇe hladké keramické destiˇcky. Prvn´ı destiˇcka je pevn´ a a jsou v n´ı tˇri otvory napojené na pˇr´ıtok studené vody, pˇr´ıtok teplé vody a odtok. Druh´ a destiˇcka je pohyblivá a je v n´ı prohlubeˇ n. Zved´ an´ım p´ aky se pohyblivá destiˇcka posouvá nad pevnou destiˇckou a jej´ımi otvory, takˇze voda m˚ uˇze prohlubn´ı protékat z otvor˚ u napojen´ ych na pˇr´ıtok studené a teplé vody do otvoru napojeného na odtok. Vˇetˇs´ı zvednut´ı páky pˇritom zp˚ usobuje vˇetˇs´ı posuut´ı a t´ım vˇetˇs´ı pr˚ utok vody. Ot´ aˇcen´ım p´ aky se mˇen´ı smˇer, kter´ ym se bude pohyblivá destiˇcka posouvat a t´ım lze ovlivˇ novat, zda a jakou mˇerou bude prohlubeˇ n pˇri posunu destiˇcky

Obr´ azek 1. P´ akov´ a vodovodn´ı baterie

zasahovat nad oba pˇr´ıtoky a nad odtok a tedy jaká bude v´ ysledná teplota tekouc´ı vody. Pˇrirozen´ y poˇzadavek na pákovou baterii je, aby nastavená teplota vody, z˚ ustala zachov´ ana bez ohledu na to, jak moc vody protéká. Tedy aby pomˇer ploch ˇc´ ast´ı otvor˚ u pˇripojen´ ych na pˇr´ıtoky, zakryt´ ych prohlubn´ı v pohyblivé destiˇcce, i pˇri r˚ uzné u ´rovni posunut´ı prohlubnˇe z˚ ustával stejn´ y. Probl´ em: Jaký tvar by mˇely m´ıt otvory a prohlubeˇ n? Tento problém uv´ ad´ıme jako pˇr´ıklad problému, na kter´ y nevystaˇc´ıme s ,,klasick´ ym” programov´ an´ım. Jeho ˇreˇsen´ı zat´ım odloˇz´ıme.

3

´ Uloha 1: Nakreslen´ı grafu

Zad´ an´ı: Napiˇste program, který nakresl´ı zadaný graf. Graf je neorientovaný, bude zad´ an jako seznam vrchol˚ u a hran, hrany budou kresleny jako u ´seˇcky a nakreslen´ı m´ a být hezké. V zad´ an´ı se uv´ ad´ı, ˇze hrany budou kresleny jako u ´seˇcky, jde tedy pouze o urˇcen´ı polohy jednotliv´ ych vrchol˚ u. Zad´ an´ı je pomˇernˇe neurˇcité, nen´ı tˇeˇzké pˇredstavit si nakreslen´ı grafu, které hezké nen´ı — kde se budou hrany zbyteˇcnˇe kˇr´ıˇzit, budou procházet vrcholy, nˇekteré vrcholy budou pˇr´ıliˇs bl´ızko u sebe — a naopak urˇcitá nakreslen´ı urˇcit´ ych graf˚ u, kter´ a hezk´ a budou. Krom tˇechto extrém˚ u vˇsak z˚ ustává urˇcitá neurˇcitá oblast. Zkusme tuto u ´lohu, i pˇres jej´ı nepˇresné zadán´ı, ˇreˇsit obvykl´ ym postupem. N´ apad 1.: Pˇrednˇe si m˚ uˇzeme vˇsimnout, ˇze pokud graf nen´ı souvisl´ y, m˚ uˇzeme ˇreˇsen´ı u ´lohy rozdˇelit na ˇreˇsen´ı stejné u ´lohy pro kaˇzdou komponentu souvislosti. Rozdˇelit graf na komponenty souvislosti je u ´loha, na kterou známe algoritmus. Dále tedy pˇredpokl´ adejme, ˇze pracujeme jiˇz jen se souvisl´ ym grafem. N´ apad 2.: Zjistˇeme, jaké jsou stupnˇe jednotliv´ ych vrchol˚ u. Pokud maj´ı vˇsechny vrcholy stupeˇ n dva, m˚ uˇzeme vrcholy grafu uspoˇrádat a nakreslit na kruˇznici. N´ apad 3.: Pokud maj´ı vˇsechny vrcholy stupeˇ n dva kromˇe dvou, které maj´ı stupeˇ n jedna, m˚ uˇzeme vrcholy grafu uspoˇrádat a nakreslit na pˇr´ımku.

N´ apad 4.: Pokud graf neobsahuje cyklus, m˚ uˇzeme zvolit jeden vrchol za koˇren a nakreslit graf jako strom. Takov´ ych a podobn´ ych nápad˚ u ˇreˇs´ıc´ıch jednotlivé d´ılˇc´ı pˇr´ıpady bychom mohli shrom´ aˇzdit vˇetˇs´ı poˇcet, st´ ale vˇsak budou z˚ ustávat grafy, které nakreslit neum´ıme. Zkusme proto tuto u ´lohu ˇreˇsit jinak. Rada 1.: M´ ate-li u ´ lohu, kterou nechcete nebo neum´ıte ˇ reˇ sit. . . . . .ˇ reˇ ste jinou u ´ lohu!

Pˇredstavme si, ˇze vrcholy grafu odpov´ıdaj´ı bod˚ um, které se odpuzuj´ı silou klesaj´ıc´ı se ˇctvercem vzd´ alenosti. Naopak hrany p˚ usob´ı jako guma nebo pruˇziny a pˇritahuj´ı pˇr´ısluˇsné vrcholy silou rostouc´ı se ˇctvercem vzdálenosti. Program, kter´ y m´ a hledat nakreslen´ı grafu (souvislé komponenty, tento krok z klasického ˇreˇsen´ı si ponech´ ame) bude pracovat tak, ˇze na zaˇcátku body rozm´ıst´ı n´ ahodnˇe a potom opakovanˇe v kaˇzdém kroku vˇzdy pro jeden bod vypoˇcte vektory pˇritaˇzliv´ ych a odpudiv´ ych sil a polohu bodu uprav´ı ve smˇeru daném souˇctem tˇechto sil. Polohy bod˚ u, ve kter´ ych se tento pohyb ustál´ı, nebo které se alespoˇ n uˇz nebudou pˇr´ıliˇs mˇenit, pouˇzijeme jako v´ ysledné polohy vrchol˚ u grafu.

Obr´ azek 2. Zaˇc´ atek, pr˚ ubˇeh a konec v´ ypoˇctu

4

´ Uloha 2: H´ ad´ an´ı obr´ azku

Tato u ´loha je umˇel´ a, slouˇz´ı jen k tomu, abychom mohli pˇredvést dalˇs´ı techniku ˇreˇsen´ı u ´loh. Pozdˇeji uvid´ıme, ˇze stejnou technikou lze ˇreˇsit i u ´lohy opravdovˇejˇs´ı. M´ ame napsat program, kter´ y uhádne obrázek uloˇzen´ y v jiné ˇcásti programu (a zadan´ y uˇzivatelem pˇri startu programu). Takov´ yto typ u ´loh je pomˇernˇe ˇcast´ y — nev´ıme pˇresnˇe, co m´ ame dˇelat a jediné, co se dozv´ıdáme je, ˇze to, co dˇeláme,

Obr´ azek 3. Nalezen´ a nakreslen´ı tˇr´ı- a ˇctyˇr-rozmˇerné krychle

nen´ı spr´ avnˇe. Pokud se n´ am ale dostává informace, jak moc to nen´ı správnˇe, m´ ame nap˚ ul vyhr´ ano. M˚ uˇzeme totiˇz pouˇz´ıt druhou radu: Rada 2.: M´ ate-li u ´ lohu, kterou nechcete nebo neum´ıte ˇ reˇ sit. . . . . . zapojte pˇ rirozen´ y v´ ybˇ er!

Technika, kterou chceme pouˇz´ıt, se naz´ yvá genetický algoritmus a lze ji vysvˇetlit opravdu jednoduˇse — máme-li hledat ˇreˇsen´ı a máme k disposici ohodnocovac´ı funkci, kter´ a kaˇzd´ y pˇredloˇzen´ y pokus o ˇreˇsen´ı ohodnot´ı, potom budeme postupovat tak, ˇze si vytvoˇr´ıme urˇcitou mnoˇzinu ˇreˇsen´ı, neboli populaci, ze zaˇc´ atku vytvoˇrenou n´ ahodnˇe. Kaˇzd´ y prvek populace necháme ohodnotit ohodnocovac´ı funkc´ı a potom ze souˇcasné populace vytvoˇr´ıme populaci novou, novou generaci. Pˇritom prvky nové generace budou nˇekteré prvky staré populace, v´ ybˇer se prov´ ad´ı n´ ahodnˇe, ale s pˇrihlédnut´ım k ohodnocen´ı jednotliv´ ych prvk˚ u, takˇze ti jedinci populace, kteˇr´ı maj´ı lepˇs´ı ohodnocen´ı, maj´ı vyˇsˇs´ı pravdˇepodobnost, ˇze se objev´ı i v dalˇs´ı generaci — a dále také nˇekteré nové prvky vzniklé pomoc´ı operac´ı kˇr´ıˇzen´ı a mutace. Kˇr´ıˇzen´ı znamen´ a, ˇze nového jedince sloˇz´ıme ze dvou jedinc˚ u staré populace — a opˇet s pˇrihlédnut´ım k ohodnocen´ı, takˇze u ´spˇeˇsnˇejˇs´ı jedinci maj´ı vˇetˇs´ı ˇsanci vyvést potomky. Mutace oznaˇcuje n´ ahodnˇe vniklou chybu, s urˇcitou pravdˇepodobnost´ı pozmˇen´ıme nˇekter´ y u ´daj nebo u ´daje v popisu jedince. K ˇcemu je mutace dobrá uvid´ıme za chv´ıli. Ze st´ avaj´ıc´ı populace tedy vzniká populace nová, z n´ı zase nová a pˇri vytváˇren´ı nov´ ych populac´ı maj´ı vˇzdy vˇetˇsi ˇsanci pˇreˇz´ıt jedinci nebo jejich ˇcásti (kˇr´ıˇzen´ı), kteˇr´ı dosahovali lepˇs´ıho ohodnocen´ı. Postupnˇe by se tedy v populaci mˇeli vyskytovat jedinci, kteˇr´ı se budou v´ıce a v´ıce pˇribliˇzovat hledanému ˇreˇsen´ı. N´ aˇs program, kter´ y ˇreˇs´ı u ´lohu hádán´ı obrázku, pouˇz´ıvá zjednoduˇsenou versi genetického algoritmu — krok vypadá tak, ˇze z populace jen odstran´ıme prvek

s nejhorˇs´ım hodnocen´ım a nahrad´ıme ho nov´ ym prvkem vytvoˇren´ ym zkˇr´ıˇzen´ım dvou nejlepˇs´ıch jedinc˚ u a pouˇzit´ım mutace. Tento zjednoduˇsen´ y zp˚ usob je snazˇs´ı naprogramovat (i kdyˇz ani stˇr´ıdán´ı cel´ ych populac´ı nen´ı tˇeˇzké naprogramovat) a nav´ıc máme zaruˇceno, ˇze nem˚ uˇzeme ztratit jiˇz nalezené ˇreˇsen´ı s vysok´ ym ohodnocen´ım (protoˇze ztrác´ıme vˇzdy jen nejhorˇs´ı ˇreˇsen´ı). Za toto zjednoduˇsen´ı plat´ıme ”ztrátou v´ ykonu”, protoˇze vlastnˇe v kaˇzdé nové generaci je jen jeden nov´ y prvek, zat´ımco u vytváˇren´ı celé nové populace by mohlo b´ yt nov´ ych jedinc˚ u v´ıce a t´ım by byla i vˇetˇs´ı ˇsance rychleji naj´ıt lepˇs´ı ˇreˇsen´ı. Pozn´ amka: Na druhou stranu, tato technika, kdy do nové generace bez náhodného v´ ybˇeru pˇren´ aˇs´ıme jednoho nebo v´ıce nejlepˇs´ıch jedinc˚ u se také pouˇz´ıvá, právˇe pro zabránˇen´ı tomu, aby n´ ahodn´ ym v´ ybˇerem ”vyhynula” nejlepˇs´ı ˇreˇsen´ı a celá populace se tak propadla na v´ yvojové kˇrivce zpátky. Ohodnocovac´ı funkce je jednoduchá, jedinec-obrázek je bod po bodu porovnán s (tajn´ ym) c´ılov´ ym obr´ azkem, za kaˇzd´ y uhádnut´ y bod je hodnocen´ı zv´ yˇseno, za kaˇzd´ y neuh´ adnut´ y bod je hodnocen´ı sn´ıˇzeno (coˇz je zbyteˇcné, mohlo by z˚ ustat stejné). Kˇr´ıˇzen´ı prob´ıh´ a tak, ˇze kaˇzd´ y bod obrázku nového jedince je náhodnˇe vybrán od jednoho nebo od druhého rodiˇce. Mutace potom znamen´ a náhodnou zmˇenu náhodnˇe vybraného bodu. Na pravdˇepodobnosti mutace záleˇz´ı, jak rychle (a zda v˚ ubec) genetick´ y algoritmus najde ˇreˇsen´ı. Kdyby mutace neexistovala (kdyby jej´ı pravdˇepodobnost byla rovna nule), nemohla by se v populaci objevit ˇzádná nová informace. V naˇsem pˇr´ıkladu by to znamenalo, ˇze pokud napˇr´ıklad vˇsechny prvky populace maj´ı bod v pravém horn´ım rohu obarven b´ıle, nikdy se nem˚ uˇze vyskytnout jedinec, kter´ y by tento bod mˇel ˇcern´ y. Pokud v´ ysledné ˇreˇsen´ı poˇzaduje na tomto m´ıstˇe ˇcen´ y bod, nikdy nebude nalezeno. Naopak pokud je pravdˇepodobnost mutace pˇr´ıliˇs vysoká, zmutovan´ı jedinci mutac´ı ztr´ acej´ı informaci, kterou z´ıskali od sv´ ych pˇredk˚ u. Kdyˇz v naˇsem programu nastav´ıme pravdˇepodobnost mutace na vyˇsˇs´ı ˇc´ıslo, uvid´ıme, ˇze novˇe vytvoˇren´ y jedinec je sv´ ym hodnocen´ım nejhorˇs´ı ze vˇsech, takˇze bude ihned zahozen a nahrazen novˇe vytvoˇren´ ym jedincem, kter´ y bude opˇet nejhorˇs´ı ze vˇsech. . . Nˇekdy se ovˇsem m˚ uˇze vyplatit pravdˇepodobnost mutace mˇenit v pr˚ ubˇehu v´ ypoˇctu, napˇr´ıklad na zaˇc´ atku nastavit pravdˇepodobnost vyˇsˇs´ı a po tom, co uˇz byla dosaˇzena urˇcit´ a kvalita ˇreˇsen´ı, mutaci sn´ıˇzit. Pokud se ale v´ yvoj pozastavil a nepˇrináˇs´ı nic nového, m˚ uˇzeme mutaci zase na chv´ıli zv´ yˇsit (této technice se ˇr´ıká ˇz´ıh´ an´ı, term´ın z metalurgie), coˇz m˚ uˇze pomoci populaci opustit nˇejaké lokáln´ı maximum; pˇredstavte si to jako hledán´ı nejvyˇsˇs´ıho bodu v krajinˇe tak, ˇze jdete stále do kopce; také se vám m˚ uˇze stát, ˇze uv´ıznete na nˇejakém malém kopeˇcku a dál to nejde, protoˇze mus´ıte j´ıt stále do kopce.

Genetické algoritmy tedy pˇredstavuj´ı metodu, jak hledat ˇreˇsen´ı, pokud dok´ aˇzeme kaˇzd´ y pokus o ˇreˇsen´ı popsat pomoc´ı dat (gen) a pokud máme k dispozici ohodnocovac´ı funkci. Jejich u ´spˇeˇsnost je r˚ uzná, záleˇz´ı zejména na tom, jak spojit´ y je vztah mezi genem a ohodnocen´ım.

..X.X.XX ......X. X.X.XXXX ....X... ..XX.XX. XXX.X.XX ..X.XXX. .....XXX -2.00

XXXX...X XX.X.XX. X...XXXX X.X.X... .X..XX.. .XX....X XX.X.X.. XX...... -4.00

XX.X..X. XX.X.XXX X..XXX.X .X...X.. .XXX..XX .XXXXX.. XX...... X.XX...X -10.00

..XX...X .....X.X X.X.XXX. X....XXX .X..X... XXX.XX.. XXX.XXXX XX...XX. -8.00

XX..X.XX ........ ........ .XXXX..X X...XX.. ...X.XX. X.XX.X.. XX.X..X. -4.00

XXXXXXX. XXX...XX .XXX.XXX .XXXX... XX..XX.X XX.X..XX .X.XXX.. .X..XX.. 10.00

XXXXX.XX .X...X.. X....... X.X..... XXXXX.XX .X.XX.XX .X..X... .XXX.X.. 4.00

.XX.XXX. .X.X..XX X......X ..XX.XXX X....... XXX...XX XXX.X.XX ..XXX.X. -8.00

...XXX.. X..X...X X..X.... XX..XXXX XXX.X... .X..XXX. XX.XX.X. .X.XXXX. 0.00

X.X..XX. .X...XXX ..X....X ..XX.XX. .X...XXX X.XX.X.X .X.X..XX X.X..... -6.00

XXXX.... XXXX.... XXXX.... XXXX.... ....XXXX ....XXXX ....XXXX ....XXXX

Obr´ azek 4. Populace na zaˇc´ atku v´ ypoˇctu

XXXX.... XXXX.... XXXX.... XXXX.... ....XXXX ....XXXX ....XXXX ....XXXX 64.00





XX.X.... XXXX.... XXXX.... XXXX.... ..XX.XXX ....XXXX ....XXXX ....XXXX 56.00

XXXX.... XXXX.... XXXX.... XXXX.... ....XX.X ....XXXX ....XXXX ....XXXX 62.00




XXXX.... XXXX.... XXXX.... XXXX.... ....XXXX ....XXXX ....XXXX ....XXXX

Obr´ azek 5. Populace na konci v´ ypoˇctu

5

´ Uloha 2’: Brouˇ cci

Genetick´ y algoritmus si uk´ aˇzeme jeˇstˇe na dalˇs´ıch pˇr´ıkladech. V tomto pˇr´ıkladu nem´ ame jasné zad´ an´ı, pokud bychom ho pˇrece chtˇeli zformulovat, znˇelo by asi takto:

Zad´ an´ı: Mˇejme d´ an svˇet, ve kterém ˇzij´ı brouˇcci. Brouˇcci se umˇej´ı pohybovat (otoˇcit se doprava nebo doleva nebo udˇelat krok), vid´ı (pˇred sebe a do stran) a jejich potravou jsou (ostatn´ı) brouˇcci. Najdˇete algoritmus, kterým se m´ a brouˇcek ˇr´ıdit, aby nezahynul hlady ani nebyl seˇzr´ an. Kdyˇz brouˇcek nem´ a ˇz´ adnou pamˇet’, lze jeho algoritmus popsat pomoc´ı funkce (CoJeV levo, CoJeV epredu, CoJeV pravo) → T ah Tuto funkci m˚ uˇzeme nahradit tabulkou. Populace brouˇck˚ u je v programu viditelná, brouˇcek je znázornˇen ˇsipkou otoˇcenou ve smˇeru pohledu brouˇcka, barva urˇcuje, kolik brouˇck˚ u jiˇz brouˇcek snˇedl. V´ yvoj neprob´ıh´ a po kolech, ale jednotliv´ı brouˇcci se stˇr´ıdaj´ı v taz´ıch a vˇzdy, kdyˇz poˇcet brouˇck˚ u klesne pod urˇcitou mez, jsou vytvoˇreni nov´ı brouˇcci z neju ´spˇeˇsnˇejˇs´ıch ˇclen˚ u populace (rodiˇce se nemusej´ı setkat). Pokaˇzdé, kdyˇz je vytv´ aˇren nov´ y brouˇcek, program vypisuje v´ ykon (poˇcet seˇzran´ ych brouˇck˚ u) a algoritmus jeho rodiˇce — nej´ uspˇeˇsnˇejˇs´ıho (ˇzij´ıc´ıho) brouˇcka.

Obr´ azek 6. Louka s brouˇcky

Pr´ avˇe zobrazen´ y algoritmus bychom slovy mohli popsat tˇreba takto: – je-li pˇred tebou brouˇcek a napravo nic, jdi dopˇredu (ˇzer) – jinak, je-li napravo brouˇcek, otoˇc se doprava, s v´ yjimkou pˇr´ıpadu, kdy je brouk i pˇred tebou i nalevo, v takovém pˇr´ıpadˇe nedˇelej nic – jinak se otoˇc doleva. Pozn´ amka: Je zaj´ımavé, v tomto i následuj´ıc´ım pˇr´ıkladu (ten se také t´ yká brouˇck˚ u), ˇze nej´ uspˇeˇsnˇejˇs´ı algoritmy nejsou vˇzdy takové, jaké bychom si moˇzná pˇredstavovali.

Napˇr´ıklad kdyˇz brouˇcek v´ı, ˇze napravo od nˇej je jin´ y brouˇcek, neuteˇce, ale otoˇc´ı se k nˇemu. Pˇritom je pravdˇepodobnost 1:4, ˇze ho tento jin´ y brouˇcek v n´ asleduj´ıc´ım tahu m˚ uˇze slupnout. Ale brouˇcek, jehoˇz algoritmus zde vid´ıme, tohoto rizika nedb´ a a otoˇc´ı se doprava. Zpochybnit nalezené algoritmy pˇr´ıliˇs nem˚ uˇzeme, protoˇze na rozd´ıl od naˇsich pˇredstav jsou opravdu provˇeˇreny bojem, takˇze mus´ıme hledat jiná vysvˇetlen´ı. Tˇreba n´ ahodu nebo to, ˇze ten brouˇcek napravo nemus´ı m´ıt tak dobr´ y algoritmus, takˇze riziko seˇzr´ an´ı nen´ı 1:4, ale menˇs´ı.

´ Uloha 2”: Brouˇ cci s pamˇ et´ı

6

Brouˇcci v minulém pˇr´ıkladu nemaj´ı ˇzádnou pamˇet, jejich algoritmy tedy pˇredstavuj´ı pˇr´ımoˇcaré rozhodov´ an´ı na základˇe toho, co vid´ı. Jak by se zmˇenilo chován´ı a hlavnˇe schopnosti brouˇck˚ u, kdyby si mohli pamatovat? Pamˇet’ brouˇck˚ um pˇrid´ ame tak, ˇze krom informace, co právˇe vid´ı, budou m´ıt informaci o tom, v jakém jsou stavu. Stav bude promˇenná z rozsahu jedna aˇz maxim´ aln´ı povolen´ y poˇcet stav˚ u. Algoritmus brouˇcka bude tedy opˇet moˇzné vyjádˇrit funkc´ı a tabulkou, pouze funkci pˇribude jeden parametr a tabulce dalˇs´ı rozmˇer a v´ ysledkem funkce a obsahem pol´ıˇcka v tabulce bude nejenom akce, kterou má brouˇcek provést, ale také u ´daj, do kterého stavu má pˇrej´ıt. Tedy napˇr´ıklad ”Jsi-li ve stavu ˇc´ıslo dva, nalevo je potrava, pˇred tebou zed’ a napravo nic, otoˇc se doleva a pˇrejdi do stavu ˇc´ıslo jedna!” Abychom mohli brouˇcky porovnat, nenecháme je ted’ spolu zápasit, protoˇze lze ˇcekat, ˇze pokud budou brouˇcci s pamˇet´ı jen trochu lepˇs´ı, z˚ ustanou nakonec v populaci jenom oni a my chceme mˇeˇrit, o kolik jsou lepˇs´ı. Budeme tedy schopnosti brouˇck˚ u mˇeˇrit tak, ˇze budou sb´ırat potravu v bludiˇsti, kaˇzd´ y sám za sebe, a budeme vyhodnocovat, kolik potravy se kterému brouˇckovi podaˇrilo nalézt. Kaˇzdé pol´ıˇcko bludiˇstˇe m˚ uˇze obsahovat potravu, nepr˚ uchodnou zed’ nebo nic — tedy pr´ azdn´ y prostor, kter´ ym lze proj´ıt. Abychom ovˇeˇrili vˇsestrannost algoritmu, kter´ y brouˇcek má, budeme kaˇzdého brouˇcka testovat na deseti bludiˇst´ıch, která se liˇs´ı mnoˇzstv´ım potravy, zd´ı a pr´ azdn´ ych pol´ıˇcek. Z kaˇzdého bludiˇstˇe urˇc´ıme, kolik procent potravy brouˇcek naˇsel a v´ ysledky (jako procenta nalezené potravy) za jednotlivá bludiˇstˇe budeme sˇc´ıtat. Bludiˇstˇe jsou vygenerov´ ana náhodnˇe, ale pro vˇsechny brouˇcky stejná. Vypadaj´ı takto: 21 * * *

*

*

* * *

* * * *

*

* *

* *

**

* *

128 * *** ** ** * ** ** * * ** **** * * **** ** * *** *** ** * ** * * *** ** *** * ** ** *** * ** * * * * * * * * * ** * ***** **** * ** ** ********* * ** * * * *** * * * *** * ** * ** * **** * *** *

259 ******************* ******************** ******************** ******************** ******************** ******************** ******************** ******************** ******************** ******************** ******************** ******************** ********************

27 * MM* * * MM M MM M * M* M MM* MMM * M * * * M* M M M *MM M* M M MM M* * M M M * M M M M* * M* M *MMM M MM M M M*M M M * M**M * * M M M

124 * MM MM**M*** ** ***** **MM * M** M * M**M*** ** M* ***M *M *M*M * *** ****M **** M M* * * *** * ** ** * M* M * ** **MM** MM**M* M * MMM * M * M *** *M M MMM M****M*M ***M* ***M******** **M*** ***MM *M MM * M ** ****M * MM** * M* **MM M** ** **

202 *M**M********MM***M **M****MM*M********* *****M***M*M*****M** M*MM*****M**M*M***MM *M*****M*******M*M** M***M**************M **********M*****M*** **M*M*M*M*M*M*MM**** **M*M**M*********MMM ***M***M****M*M****M ***M*****M******M*** **M**M***M****M***** **M*****************

23 M

MMMMMMM *MM M M M M M M M M M MMMM* MMMM *M MMMM M M MM * M MM MM* M * M M M MM * M MM MMM M *MM M **M MMM *M M M M * MM * M M M * * MM* M MM*M MM* M *M * M*M MM M M M M M * M M MMM*MMM MM

127 ***M******* MM ** M ****** * MM*** *M M* M*M *M** *M * M*MM** **M *******M* M**MM *MM *M*M***M*M* *MM* *** M*****MM MMMM* M**M**** ** *MM* *** M *** ****MM* M*M*M* ***M* MM* *MMM* *M *MM**MM***MMM M *M M*MM**M*M** M M *M ***M ** MMM *M M *M M****MM **M* *MMM **

162 MM M**M***MMM****MM* *MM***MMM*M MM**M*M* *M*M******MM*MM***MM ********M******M**MM ************MMM M**M ****M**MM******MMM*M MM**MM*M***MM******* M**M*MM M***M**M**** **M****M**M**MM M*** ******M**MM**MMMM*M* ****M**MMM*****MMM** M***M*MM*******M**** **MMMMMM**MM*****MM*

151 MM*M*M*****MMMM**M M M*M*****MM*MM***MMM **MMM******MM***MM M ****M*M*M*M**MM*MMMM M***M******M*****MMM **M***M**MM MMM***MM **M*MMM*M**M****MMM* MMM*M*M**********M** ******M***M********M *MM**M*MM****MM***M* **MMM**MMM*M****M*M* M*M****M*MM MMM***M* *******M*M*MM M*M*M*

Hvˇezdiˇcky oznaˇcuj´ı potravu, p´ısmena M pˇrekáˇzky a mezery voln´ y prostor, ˇc´ısla nad kaˇzd´ ym bludiˇstˇem udávaj´ı poˇcet hvˇezdiˇcek. Bludiˇstˇe je na toroidu, takˇze nejpravˇejˇs´ı sloupec soused´ı s nejlevˇejˇs´ım sloupcem a prvn´ı ˇrádek soused´ı s posledn´ım ˇr´ adkem. Souhrnné v´ ysledky brouˇcka pouˇzijeme jako ohodnocovac´ı funkci pro genetick´ y v´ ybˇer v populaci brouˇck˚ u. Uˇz jeden z prvn´ıch algoritm˚ u brouˇcka bez pamˇeti vypadá jinak, neˇz bychom moˇzn´ a oˇcek´ avali: stav: 0 vlevo: vlevo: * vlevo: M

pred: . * * M * M ^0 >0 ^0 ^0 ^0 ^0 <0 >0 <0 <0 ^0 <0 ^0 >0 ^0 ^0 ^0 ^0

M * >0 <0 <0 >0 >0 <0

M <0 <0 <0

Takhle divnˇe sb´ır´ a potravu v m´ıstech, kde nejsou ˇzádné pˇrekáˇzky:

Obr´ azek 7. Pr´ ace algoritmu v bludiˇsti ˇc.1

ale zase takhle dok´ aˇze mezi pˇrekáˇzkami uvnitˇr bludiˇstˇe ˇc´ıslo 6. naj´ıt 199 hvˇezdiˇcek z celkov´ ych 202:

Obr´ azek 8. Pr´ ace algoritmu v bludiˇsti ˇc.6

V´ ypoˇcet u brouˇck˚ u s pamˇet´ı vypadá podobnˇe, jen tabulka je tolikrát vˇetˇs´ı, kolik stav˚ u brouˇcek m˚ uˇze m´ıt, cesta brouˇcka je obarvena podle toho, v jakém stavu se brouˇcek nach´ az´ı. . . a trv´ a mnohem déle, neˇz genetick´ y algoritmus nalezne brouˇcka, kter´ y by dok´ azal danou pamˇet’ opravdu efektivnˇe vyuˇz´ıt. Naˇse zkoum´ an´ı skonˇcilo u dvou resp. tˇr´ı stav˚ u, protoˇze uˇz dva stavy staˇcily k tomu, aby brouˇcek s n´ asleduj´ıc´ım algoritmem dokázal sebrat vˇsechny dostupné hvˇezdiˇcky kromˇe dvou, pˇri tˇrech stavech potom vˇsechny hvˇezdiˇcky aˇz na jednu.

stav: 0 vlevo: vlevo: * vlevo: M stav: 1 vlevo: vlevo: * vlevo: M

pred: . * M ^1 ^0 ^1 ^0 <0 <1 ^1 >1 ^0 * M ^1 >0 <1 <1 <0 <1 ^1 <1 ^1

^1 ^1 ^0 ^0 <0 ^1

* ^0 ^1 ^0 * ^1 <1 ^0

* M ^0 >1 >1 M ^0 <0 ^0

>1 <1 >1 <0 ^0 >0

M * >1 >1 >0 * >0 <0 <1

M >0 >0 >1 M <0 <1 >0

Obr´ azek 9. Algoritmus, kter´ y se dvˇema stavy najde vˇsechny hvˇezdiˇcky kromˇe dvou

7

Vsuvka: Historka o magnetofonu

Na u ´vod k dalˇs´ı radˇe uvedeme nejdˇr´ıve jednu historku. Pˇredstavme si, ˇze máme magnetofon s poˇc´ıtadlem zaznamenávaj´ıc´ım otáˇcky nav´ıjec´ıho kotouˇce.

Zad´ an´ı: Napiˇste program, který dok´ aˇze vz´ ajemnˇe pˇrev´ adˇet stav poˇcitadla magnetofonu a odehraný ˇcas. Historka z n´ azvu kapitoly spoˇc´ıvá v tom, ˇze jsme zmˇeˇrili pr˚ umˇer nav´ıjec´ıho kotouˇce, tlouˇst’ku p´ asky, vyjádˇrili délku nav´ıjené pásky. . . — a dostali cosi nepouˇzitelnˇe nepˇresného. T´ım tento pokus skonˇcil. Po ˇcase n´ as napadlo nestarat se o vˇeci, jako je nav´ıjec´ı kotouˇc nebo tlouˇst’ka p´ asky a prostˇe zkusit nˇejak aproximovat funkci urˇcuj´ıc´ı vztah mezi otáˇckami a ˇcasem. Line´ arn´ı ten vztah nen´ı, tak jsme zkusili kvadratickou funkci. Kvadratickou funkci m˚ uˇzeme vyjádˇrit jako y = Ax2 + Bx + C a potˇrebujeme tedy jednom urˇcit hodnoty A, B a C. K urˇcen´ı tˇechto hodnot a k urˇcen´ı celé kvadratické funkce staˇc´ı znát hodnotu funkce ve tˇrech bodech. Nulovému ˇcasu odpov´ıdaj´ı nulové otáˇcky, zjistili jsme jeˇstˇe stav poˇc´ıtadla po pˇrevinut´ı celé kazety (45 minut) a uprostˇred. Vypoˇctené koeficienty urˇcily funkci — která, na rozd´ıl od p˚ uvodn´ıho v´ ypoˇctu, dávala velice pˇresné v´ ysledky! A to pˇresto, ˇze tento v´ ypoˇcet nemˇel nic spoleˇcného s t´ım, co vztah mezi poˇc´ıtadlem a ˇcasem vytváˇr´ı, ˇzádná tlouˇst’ka pásky, ˇzádk´ y pr˚ umˇer nav´ıjec´ıho kotouˇce. . . Pomohlo pod´ıvat se na problém jako na ˇcernou skˇr´ınku, nemyslet na to, co je uvnitˇr a jen sledovat jeho chován´ı. Rada 3.: M´ ate-li u ´ lohu, kterou nechcete nebo neum´ıte ˇ reˇ sit. . . . . . zkuste se na ni pod´ıvat z odstupu!

8

´ Uloha 3: Rozpozn´ av´ an´ı znak˚ u

Pˇredpokl´ adejme, ˇze m´ ame d´ an rastrov´ y obrázek, tedy matici bod˚ u, kde u kaˇzdného bodu zn´ ame barvu nebo odst´ın ˇsedi a ˇze tento obrázek odpov´ıdá stránce textu v rozliˇsen´ı napˇr´ıklad 300 dpi, tedy 300 bod˚ u na palec. Pˇrevést tento obrázek zp´ atky na text je pˇredmˇetem u ´lohy naz´ yvané optické rozpoznáván´ı znak˚ u, zkrácenˇe OCR. Tato u ´loha m´ a nˇekolik ˇc´ ast´ı, je tˇreba nejprve urˇcit oblasti stránky obsahuj´ıc´ı text, na rozd´ıl od ˇc´ ast´ı tvoˇren´ ych obrázky, oddˇelit sloupce textu, oddˇelit jednotlivé ˇr´ adky, nalézt hranice mezi p´ısmeny — a nakonec rozpoznat jednotlivá p´ısmena. To je krok, kter´ y nás nyn´ı zaj´ımá. M´ ame tedy d´ an obr´ azek, pˇri daném rozliˇsen´ı a pˇri velikosti p´ısmene jeden palec to znamen´ a velikost 300x300 bod˚ u, jehoˇz jednotlivé body, pro jednoduchost jsou pouze ˇcerné nebo b´ılé. Naˇs´ım u ´kolem je pro dan´ y obrázek urˇcit, jak´ y znak je na nˇem zobrazen.

K ˇreˇsen´ı této u ´lohy se pouˇz´ıvaj´ı r˚ uzné metody. M˚ uˇzeme napˇr´ıklad ”obcházet” ˇcerné body kolem dokola a zjiˇst’ovat, kolikrát mˇen´ıme smˇer zatáˇcen´ı doprava a doleva. Nebo m˚ uˇzeme zjiˇst’ovat, zda obrázek-p´ısmeno obsahuje ”d´ıru”, skupinu b´ıl´ ych bod˚ u ohraniˇcenou ˇcern´ ymi body. Na okamˇzik by nás také mohlo napadnout, ˇze by staˇcilo si pamatovat pro kaˇzd´ y obrázek, jakému p´ısmenu odpov´ıdá, ale mˇeli bychom si rychle uvˇedomit, ˇze pˇri velikosti obrázku 300x300 bod˚ u existuje 2( 300x300) r˚ uzn´ ych ˇcernob´ıl´ ych obrázk˚ u, coˇz je poˇcet pˇresahuj´ıc´ı jakékoliv rozumné meze. ˇ sen´ı, které si uk´ Reˇ aˇzeme bude opˇet pˇredcházet jedna rada. Rada 4.: M´ ate-li u ´ lohu, kterou nechcete nebo neum´ıte ˇ reˇ sit. . . . . . omezte se na ˇ reˇ sen´ı v urˇ cit´ em tvaru!

Naˇse, ponˇekud naivn´ı, ˇreˇsen´ı bude zaloˇzeno na u ´vaze, ˇze je-li p´ısmen 26, je to ménˇe neˇz 25 a tedy pro rozliˇsen´ı jednotliv´ ych p´ısmen si staˇc´ı z celého rastru vˇs´ımat pouze pˇeti bod˚ u. Algoritmus rozpozn´ an´ı potom bude triviáln´ı, barvy onˇech pˇeti bod˚ u mohou tvoˇrit celkem 32 kombinac´ı a nahlédnut´ım do tabulky pro kaˇzdou kombinaci zjist´ıme, o jaké p´ısmeno se jedná. Zb´ yv´ a n´ am jin´ au ´loha, jak naj´ıt správn´ ych pˇet bod˚ u. Neˇreˇs´ıme tedy uˇz u ´lohu rozpoznáván´ı znak˚ u, ˇreˇs´ıme u ´lohu, jak nalézt pˇetici bod˚ u na obdéln´ıku dan´ ych rozmˇer˚ u, která má tu vlastnost, ˇze pro kaˇzdé z dvaceti ˇsesti p´ısmen d´ av´ a jinou kombinaci ˇcerné a b´ılé barvy. Zp˚ usob, jak takovou pˇetici nalézt uˇz známe — hledáme vlastnˇe deset ˇc´ısel x1 , y1 , x2 , y2 . . . x5 , y5 , pro která plat´ı F (x1 , y1 , x2 , y2 . . . x5 , y5 ) = 0 , kde funkce F je funkce, která pro jakoukoliv pˇetici bod˚ u, neboli desetici sv´ ych parametr˚ u, spoˇcte poˇcet chyb–koliz´ı, pˇr´ıpad˚ u, kdy dvˇe r˚ uzná p´ısmena dala stejnou kombinaci barev. Funkci F je snadné spoˇc´ıtat i naprogramovat a protoˇze v n´ı máme ohodnocovac´ı funkci, m˚ uˇzeme naˇse body naj´ıt pomoc´ı genetického algoritmu. Pozn´ amka: Genetick´ y algoritmus nen´ı jediná moˇznost a nijak to neznamená, ˇze u ´lohu rozpozn´ av´ an´ı znak˚ u ˇreˇs´ıme pomoc´ı genetického algoritmu! Genetick´ y algoritmus pouˇzijeme pouze jednou, v dobˇe tvorby naˇseho rozpoznávac´ıho programu programu, aby n´ am nalezl vhodné koeficienty; ostatnˇe kdybychom mˇeli dost trpˇelivosti, dok´ azali bychom je zˇrejmˇe naj´ıt i prost´ ym mechanick´ ym prohledán´ım vˇsech pˇetic bod˚ u. V naˇsem pˇr´ıpadˇe nalezené body maj´ı souˇradnice (37,18), (51,40), (48,18), (49,78), (39,50) pro p´ısmena v rastru 90 × 101, nalezená tabulka pˇrevádˇej´ıc´ı ˇc´ısla sestaven´ a z barev bod˚ u na kód znaku obsahuje hodnoty (9, 19, 12, 1, 25, 22, 24,

Obr´ azek 10. Program a nalezené body

11, 4, 16, 0, 18, 21, 13, 14, 8, 3, 10, 0, 7, 20, 6, 26, 5, 15, 2, 17, 0, 23, 0, 0, 0, 0), kde znaky jsou ˇc´ısov´ any od 1 poˇc´ınaje znakem ,,A”. Tedy, ˇcteme-li tabulku od zaˇc´ atku, vid´ıme, ˇze kombinace 00000 odpov´ıdá znaku ˇc´ıslo 9, tj. ,,I”, kombinace 00001 znaku ˇc´ıslo 19, tj. ,,S”, kombinace 00010 znaku ˇc´ıslo 12, tj. ,,L” a tak dále. Tato u ´loha je samozˇrejmˇe zjednoduˇsená, pˇredpokládáme jen jeden typ p´ısma, nepˇredpokl´ ad´ ame chyby, hledán´ı bezkolizn´ı pˇetice také m˚ uˇze trvat dlouho. . . ale nic n´ am nebr´ an´ı m´ısto pˇetice hledat tˇreba desetici bod˚ u a napˇr´ıklad si do ohodnocovac´ı funkce pˇredepsat, ˇze poˇc´ıtá kolize i pˇri zmˇenˇe jedné hodnoty — tj. ˇze poˇzadujeme, aby se kombinace v bodech liˇsila ne alespoˇ n v jedné, ale tˇreba ve tˇrech hodnot´ ach. T´ım z´ısk´ ame odolnost v˚ uˇci chybˇe — i kdyˇz nˇekde bude m´ısto ˇcerné b´ıl´ a nebo m´ısto b´ılé ˇcerná, naˇse body budou stále správnˇe urˇcovat p´ısmeno. Zrovna tak nemus´ıme vyhodnocovat na dvaceti ˇsesti p´ısmenech, ale m˚ uˇzeme m´ıt testovac´ı data, kde budou p´ısmena r˚ uzn´ ych znakov´ ych sad nebo r˚ uznˇe zmrzaˇcen´ a, zaˇsumˇen´ a atd. Pokud algoritmus nebude konvergovat, m˚ uˇzeme zvyˇsovat poˇcet bod˚ u.

9

´ Uloha 4: Obchodov´ an´ı s akciemi

Ukaˇzme si jeˇstˇe jeden pˇr´ıklad na hledán´ı ˇreˇsen´ı v urˇcitém tvaru. Bude se t´ ykat obchodov´ an´ı s akciemi. Technicky nen´ı na obchodován´ı s akciemi nic tˇeˇzkého.

Z´ ajemce o n´ akup nebo prodej cenn´ ych pap´ır˚ u sdˇel´ı sv˚ uj poˇzadavek makléˇri a ten je koup´ı ˇci prod´ a pˇr´ıpadnˇe nekoup´ı ˇci neprodá, podle toho, zda na burse bude dostateˇcn´ a nab´ıdka nebo poptávka v námi poˇzadované cenˇe - kursu. Tˇeˇzké je zjistit, jak obchodovat tak, aby obchody pˇrináˇsely zisk (zejména proto, protoˇze akciov´ y trh je uzavˇrená nádoba a kolik jeden vydˇelá, tolik ostatn´ı ztrat´ı). Moˇzn´ a jsme uˇz nˇekde slyˇseli ”Akcie klesaj´ı, mus´ım je prodat!” a jindy zase ”Akcie klesaj´ı, je ˇcas nakupovat”, ze stejn´ ych podm´ınek r˚ uzné závˇery. A moˇzná bychom chtˇeli zn´ at ,,ta spr´ avná” pravidla. Zad´ an´ı: Napiˇste program, který nalezne pravidla pˇrin´ aˇsej´ıc´ı pˇri obchodov´ an´ı s akciemi nejvˇetˇs´ı zhodnocen´ı. Vstupn´ı informace pravidel jsou kurs a objem obchodov´ an´ı dnes a ve tˇrech okamˇzic´ıch v minulosti – pˇred 2, 20 a 100 obchodn´ımi dny. Pravidla budeme hledat geneticky (rada ˇc´ıslo 2). Prvkem populace bude obchodn´ık, kter´ y m´ a urˇcitou soustavu pravidel, jak obchodovat. Ohodnocen´ı této soustavy pravidel-gen˚ u probˇehne tak, ˇze obchodn´ıkovi dáme urˇcité mnoˇzstv´ı penˇez, nech´ ame ho, podle jeho pravidel, obchodovat na skuteˇcn´ ych u ´daj´ıch z praˇzské bursy a uvid´ıme, jak se mu podaˇr´ı danou v´ ychoz´ı ˇcástku zhodnotit. Omez´ıme se na pravidla v urˇcitém tvaru (rada ˇc´ıslo 4 a zadán´ı u ´lohy). Mohli bychom ohodnocovat samostatná pravidla, ale m´ısto toho bude m´ıt kaˇzd´ y obchodn´ık pravidel v´ıce a kaˇzdému pravidlu pˇriˇrad´ıme urˇcitou váhu. Mohli bychom vyb´ırat pravidlo s nejvˇetˇs´ı váhou ale t´ım bychom ztráceli v´ yhodu toho, ˇze m´ ame v´ıce pravidel. M´ısto toho vyhodnot´ıme vˇsechna pravidla a u tˇech, kter´ a maj´ı splnˇené pˇredpoklady, pˇripoˇcteme jejich váhu k váze akce, kterou doporuˇcuj´ı. Tedy jakési hlasován´ı, kde r˚ uzná pravidla maj´ı r˚ uznˇe siln´ y hlas, ale i na tom, kdo m´ a hlas nejslabˇs´ı, m˚ uˇze nˇekdy záviset v´ ysledné rozhodnut´ı. Rada 5.: M´ ate-li u ´ lohu, kterou nechcete nebo neum´ıte ˇ reˇ sit. . . . . . a potˇ rebujete-li vyb´ırat mezi v´ıce moˇ znostmi. . . . . . pˇ rihl´ ednˇ ete k r˚ uzn´ ym hledisk˚ um. . . . . . pˇ riˇ rad’te jim v´ ahy. . . . . . a nechte je hlasovat! (Spr´ avn´ e v´ ahy m˚ uˇ zete naj´ıt geneticky.)

Pro kaˇzdou z akc´ı a pro kaˇzd´ y den v minulosti, se kter´ ym m˚ uˇzeme srovnávat, m´ ame dvˇe podm´ınky, jednu pro objem a jednu pro kurs, pˇriˇc´ıtaj´ıc´ı svou váhu k v´ aze této akce, pokud pomˇer kursu resp. objemu tehdy a dnes pˇrekroˇcil dan´ y pr´ ah. Pro pr´ ah vˇetˇs´ı neˇz 1.00, napˇr´ıklad 1.10 to pˇritom znamená, ˇze pomˇer je vˇetˇs´ı neˇz hodnota prahu, pro práh menˇs´ı neˇz 1.00, napˇr´ıklad 0.95 to znamená, ˇze pomˇer je menˇs´ı neˇz hodnota prahu. T´ım se zbavujeme nutnosti udávat znaménko nerovnosti.

Typ pravidla potom bude: type TGen = record Hodnota: real; case integer of 20: (A2:array[ TAkce ] of { nakup, prodej, drzet } array[ 1..MaxDozadu ] of record prahK, vahaK, prahO, vahaO: real; end); 21: (DNK: array[1..DelkaGenu] of real) end; V deklaraci je vidˇet, ˇze se zároveˇ n na celou genetickou informaci m˚ uˇzeme d´ıvat jako na pole hodnot typu real, coˇz nám usnadn´ı kˇr´ıˇzen´ı a mutaci. Napˇr´ıklad z u ´daj˚ u o obchodován´ı s akciemi Komerˇcn´ı banky za obdob´ı od 5.4.1994 do 19.6.2002 byla nalezena pravidla zhodnocuj´ıc´ı poˇcáteˇcn´ı vklad v´ıce neˇz sedmin´ asobnˇe. Pozor: Nen´ı zaj´ımavé, ˇze pouˇzijeme-li data za osm let obchodov´ an´ı s jedn´ım druhem akci´ı, dok´ aˇzeme naj´ıt mnoˇzinu n´ akup˚ u a prodej˚ u, kter´ a poˇc´ ateˇcn´ı investici nˇekolikr´ at zn´ asob´ı. Zaj´ımavé je, ˇze dok´ aˇzeme naj´ıt pravidla, pˇri jejichˇz dodrˇzen´ı lze poˇc´ ateˇcn´ı investici takto zhodnotit! Pozor 2: Pˇrenositelnost takto nauˇcených pravidel na jiný cenný pap´ır nebo i na stejný cenný pap´ır v jiném ˇcase. . . je velice ˇspatn´ a.

10

´ Uloha 5: Vodovodn´ı baterie

Uˇz v´ıme, jak hledat odpovˇed’ na otázku poloˇzenou v u ´vodu. Gen bude tvoˇren dvˇema maticemi (obrázky, bitov´ ymi mapami) popisuj´ıc´ım´ı ˇ a barva znamená nic, ˇcervená pˇr´ıtok teplé, modrá pˇr´ıtok stuobˇe destiˇcky. Sed´ dené, ˇzlut´ a odtok, ˇcern´ a prohlubeˇ n. (Pokud vid´ıte obrázek bez barev.. ˇcernou pozn´ ate, ˇsed´ a je ten odst´ın ˇsedé, kter´ y je v levé i pravé polovinˇe obrázku, modrá a ˇcerven´ a se vyskytuj´ı pouze v levé polovinˇe obrázku a to symetricky, a ˇzlutá je ta zb´ yvaj´ıc´ı barva v levé polovinˇe obrázku.) Hledat budeme geneticky, vyhodnocovac´ı funkce hodnot´ı odchylku vypoˇcten´ ych pr˚ utok˚ u od kˇrivky poˇzadovan´ ych pr˚ utok˚ u pˇri r˚ uzn´ ych pootoˇcen´ıch a posunech. Jak je vidˇet, do ohodnocovac´ı funkce jsme ,,zapomnˇeli” pˇridat podm´ınku, ˇze otvory maj´ı b´ yt souvislé. . . tuto u ´pravu ponecháváme ˇctenáˇri.

Obr´ azek 11. V´ ysledné tvary

Obr´ azek 12. V´ ysledné pr˚ utoky

11

Z´ avˇ er

Uvedli jsme nˇekolik technik, jak postupovat pˇri ˇreˇsen´ı u ´loh pˇr´ıliˇs obt´ıˇzn´ ych pro standardn´ı zp˚ usoby ˇreˇsen´ı. Jednotlivé techniky jsou presentovány na ˇreˇsen´ı sedmi u ´loh. Tento text, obr´ azky a zdrojové texty lze naj´ıt na adrese http://ksvi.mff.cuni.cz/~holan/jinak

Reference 1. Niklaus Wirth: Algoritmy a ˇstrukt´ ury u ´dajov, ALFA, Bratislava 1988

KSVI MFF UK Praha

Recommend Documents