uvod do umelej inteligencie zima 1996 h. 4

riesenie problemov v priestore stavov

poznatky o probleme - stavovy priestor

• zaciatocny stav (sucasny svet)
• test dosiahnutia ciela
• mnozina akcii (ktore modifikuju stavy na nove stavy)

vyzadovany vystup - riesenie

• postupnost akcii, ktore vedu zo zaciatocneho stavu do stavu, ktory splna cielove kriteria (cesta v grafe)
• navod co robit v kazdom dosiahnutelnom stave (sach,...)

stavovy graf

• uzly su stavy
• hrany su akcie transformujuce stavy
  

Problem 8 - puzzle

• stav - usporiadanie dlazdiciek
• konecny stav - (1 2 3 4 5 6 7 8 -)
• operatory - posuvy prazdneho miesta (aplikovatelnost)

charakter problemu

• eliminovat nadbytocnu informaciu (opinca a banan)
• reprezentovat stavy ako abstrakcie skutocneho sveta, obsahujuce len zakladne a relevantne vlastnosti (chceme sa dostat k najmensiemu priestoru, v ktorom je problem riesitelny)
• stavy by mali byt definovane, aby sa dali lahko definovat akcie
• akcie musia transformovat stav na iny stav v tom istom stavovom priestore
• semantika stavov a akcii definuje problem

stavove grafy

• slepe prehladavania - pozname len graf, o probleme nevieme nic (hlbka, sirka, iterovane vnaranie)
• heuristicke prehladavania kvantitativne heuristiky, ohodnotenie hran:
  odhad vzdialenosti do ciela (zo startu cez vrchol) f = g + h (pocet nespravnych kachliciek, manhattan)
  pouzivame nase poznatky o probleme na usmernenie hladania riesenia
  (best first, hill climbing, lucove vyhladavanie, usporiadane prehladavanie - a*)
• extenzionalne reprezentovane - vsetky stavy
• implicitne reprezentovane - poznam aktualny stav, akcie a nove stavy, ktore dostanem aplikovanim akcii na akt. stav

hladanie: (otvoreny - zoznam vrcholov, ktore treba preskumat, uzavrety - preskumane vrcholy)

1. daj zaciatocny stav do zoznamu otvoreny
2. ak je otvoreny prazdny, tak neuspech
3. ak je v otvoreny ciel tak vrat cestu k nemu
4. vyber stav z otvoreny, vloz stav do uzavrety, zarad do otvoreny tych nasledovnikov tohto stavu, ktore nie su v uzavretych,
5. chod na 2
   

strategia - sposob vkladania/vyberania vrcholov do/z otvoreny

idealna strategia

- viem ktory naslednik lezi na ceste medzi zaciatocnym a koncovym stavom

poziadavky na prehladavacie strategie

• uplnost - ak existuje potom najde
• ukoncenie - skonci, ak existuje konecne riesenie, aj ked je stavovy graf nekonecny
• pripustnost riesenia (viac rieseni - najde optimalne)
• pamatove naroky - problem
• casova zlozitost - maly rozdiel pri slepych prehladavaniach
• najhorsi pripad - prehlada cely graf

pr. strom hlbky d, kazdy vrchol ma b naslednikov

• do hlbky O(d*b)
• do sirky O(b^d)

heuristicke hladania (eliminovanie redundantnych ciest)

- odhad usporiadania vrcholov v zozname otvoreny

a* - f = g + h odhady g, h

priestor redukcii

• problem
• trivialny problem
• redukcia problemu na podproblemy

riesenie v priestore redukcii - riesitelny podgraf

symbolicke integrovanie, hanojske veze

hranie hier

informovane hry, tic-tac-toe

ohodnotenie pozicii - (prehra, vyhra, remiza) (max, min, 0)

realne hry - odhad ohodnotenie (dlzka cesty ku koncu)

• staticke ohodnotenie - koncove v grafe (hlboko)
• dynamicke (na zaklade ohodnoteni nasledovnikov)
• minimax - and/or grafy, min resp. max naslednikov
• alfa-beta orezavanie - ak zistim ze isty tah je katastrofalny,
  nepotrebujem poznat uplnu situaciu
  

pa

napiste schemovsku funkciu, ktora generuje krizovku.
jej vstupom je dvojrozmerne pole (zoznam zoznamov), ktoreho prvky su:

• nil - ak policko je cierne
• t - ak je prazdne a treba mu dat pismenko

slova musia byt vybrate zo slovnika, ktory budete mat k dispozicii - muozete ho akymkolvek spuosobom predspracovat, ale musi obsahovat vsetky puovodne slova. (musi obsahovat vsetky slova kratsie ako 6 pismen)