Metódy riešenia úloh v UI
Prednáša Róbert Mráz
Prednáška pre zameranie Umelá inteligencia, letný semester 1996/97
Rozsah 3/1
Zoznam odporúčanej literatúry
Nils J. Nilsson: Problem-Solving Methods in Artificial Intelligence
McGraw-Hill, 1971
Nils J. Nilsson: Principles of Artificial Intelligence
Springer-Verlag, 1982
J. Pearl: Heuristics: Intelligent Search Strategies for Computer Problem Solving
J. Kelemen a kolektív: Základy umelej inteligencie
Alfa, 1992
P. H. Winston: Artificial Intelligence (Second/Third Edition)
1984/1992?, Addison-Wesley
S. Russel, P. Norvig: Artificial Intelligence, a Modern Approach
Prentice-Hall, 1995
1. prednáška
Základné pojmy:
typy riešených problémov, hľadanie (pokusy / omyly), stavový priestor (SP), problém v SP,
riešenie problému v SP, cesta riešenia v SP, priestor redukcií (PR), problém v PR,
riešenie problému v PR, AND/OR grafy, graf riešenia v PR,
problémy (triviálne, riešiteľné, neriešiteľné, ostatné),
reprezentácia problému pre vyhľadávanie (stavy, operátory, cieľové stavy),
príklady problémov a ich reprezentácie (obchodný cestujúci, 8-puzzle, distribučný problém, opica a banán),
expandovanie vrchola, otvorené (open) a zatvorené (closed) vrcholy.
Slepé metódy prehľadávania:
univerzálny algoritmus prehľadávania pre stromy, prehľadávanie do šírky
(breadth first BF), prehľadávanie do hĺbky s obmedzením (depth first DF), iterované vnáranie
(iterative deepening ID), modifikácie pre grafy a ohodnotené grafy,
výhody / nevýhody a porovnanie slepých prehľadávaní.
Domáca úloha
Naprogramujte v Scheme Univerálny slepý prehľadávací algoritmus.
Reprezentujte problém krčahov s vodou (vater jug problem) a problém hľadania cesty v meste
ako stavové priestory.
2. prednáška
Informované metódy riešenia problémov:
kvantitatívne heuristiky, prípustnosť heuristiky,
Hill Climbing HC, Best First BF, Beam Search BS, usporiadané prehľadávanie A*, heuristická zložka h~ ohodnocujúcej funkcie (jej význam, prípustnosť, výpočtová zložitosť, príklady), zložka prejdenej cesty g~ (jej význam a potreba), modifikácie algoritmov pri nedostatku času / pamäte (fázové hľadanie, redukovanie následovníkov, postupné generovanie následovníkov, obojsmerné hľadanie), miery úspešnosti algoritmov (priebojnosť, foktor vetvenia).
Domáca úloha
Naprogramujte v Scheme usporiadané prehľadávanie pre riešenie problému s džbánmi na vodu.
3. prednáška
Vlastnosti algoritmu A*:
úplnosť algoritmu, prípustnosť algoritmu, dominancia algoritmu nad iným algoritmom, optimalita algoritmu
v triede algoritmov, t-ohraničenosť grafu, Lema1 (o existencii opt. stavu v open),
Lema2 (nutná podmienka expandovania stavu),
Lema3 (postačujúca podmienka expandovania stavu),
Veta (o prípustnosti A*), predpoklad konzistencie heuristiky, viac informovanosť heuristiky,
Lema4 (o zložke prejdenej cesty vyhodnocujúcej funkcie),
Lema5 (o nutnej podmienke uzavretia vrchola), Veta (o optimalite A*).
Abstrakcie problémov a generovanie heuristík:
absolútna chyba heuristiky, abstrakcia problému, heuristika generovaná abstrakciou, Lema (o kompozícii abstrakcií), Lema (o existencii abstrakcie podľa heuristiky), príklady heuristík generovaných abstrakciou (8-puzzle (zle položené dlaždičky, manhatanská vzdialenosť),
"Fool's disk" (suma cez priemer, suma do kríža)), Veta (o predpokladanej cene najlacnejšej cesty),
model abstrakcie zlučovaním stavov, miera abstrakcie pre model zlučovaním stavov,
Veta (o priemernej cene hrán v abstrahovanom probléme), Veta (o predpokladanej cene najkratšej
cesty v abstrahovanom probléme), Veta (kvantitatívny vzťah kvality heuristiky a miery abstrakcie).
Domáca úloha
Naprogramujte všeobecný algoritmus A*, zadefinujte heuristiku pre "Fool's disk" problém, ktorá bude
vychádzať z abstrakcie tohto problému na problém definovaný pre priemer disku.