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.