SZZ » temata » 24-reseni_uloh » stavovy_priestor
Historie: • stavovy_priestor
Starší verzeSpráva médií
Poslední úpravyIndex

OBSAH WEBU

ČTĚTE!

Toto je starší verze dokumentu!

Obsah

Metódy riešenia úloh založené na prehľadávaní stavového priestoru:

  • Stavový priestor je definovaný dvojicou (S,0):
  • S - množina všetkých stavov úlohy
    • O - množina všetkých operátorov, ktorými sa stavy dajú meniť
  • Úloha je definovaná dvojicou (s0, G):
    • s0 - počiatočný stav
    • G - množina cieľových stavov
  • Riešenie úlohy - postupnosť operátorov
  • Príklady úloh: úloha 2 džbánov, hlavolam 8, úloha N dám, úloha najkratšej cesty, úloha obchodného cestujúceho
  • Hodnotiace kritériá:
    1. úplnosť - nájde metóda riešenie (ak existuje)?
    2. časová náročnosť
    3. pamäťová náročnosť
    4. optimálnosť - nájde metóda najlepšie riešenie?
  • 2 skupiny - neinformované a informované metódy

Neinformované (slepé) metódy:

  • Nemajú k dispozícii žiadnu informáciu o cieľovom stave a nemajú žiadne prostriedky ako aktuálne stavy vyhodnotiť.

Metóda slepého prehľadávania do šírky (BFS):

  1. Zostroj frontu OPEN (bude obsahovať všetky uzly určené k expanzii) a umiestni do nej počiatočný uzol.
  2. Ak je fronta OPEN prázdna, úloha nemá riešenie a ukončí sa prehľadávanie ako neúspešné. Inak pokračuj.
  3. Vyber z čela fronty OPEN prvý uzel.
  4. Ak je vybraný uzol cieľový, ukonči prehľadávanie ako úspešné a vráť cestu od koreňového uzlu k cieľovému (vracia se postupnosť stavov, alebo operátorov). Inak pokračuj.
  5. Vybraný uzol expanduj, všetkých jeho bezprostredných naslednovníkov umiestni do fronty OPEN a vráť sa na bod 2.

  • Ak je počet bezprostredných nasledovníkov každého uzlu konečný, je algoritmus BFS úplny a optimálny.
  • Časová aj pamäťová náročnosť je exponenciálna.
  • Modifikácia 1 - v bode 5 uložíme do fronty OPEN všetkých nasledovníkov, ktorý v nej ešte nie sú

  • Modifikácia 2 - v bode 5 uložíme do fronty OPEN len tých nasledovníkov, ktorí ešte vo fronte nie sú a ktorí nie sú predkami generovaného uzlu

  • Modifikácia 3 - použitie zoznamu CLOSED
    1. Zostroj dva prázdne zoznamy, frontu OPEN (bude obsahovat všetky uzly určené na expanziu) a CLOSED (bude obsahovať zoznam expandovaných uzlov). Do fronty OPEN umiestni počiatočný uzol.
    2. Ak je fronta OPEN prázdna, úloha nemá riešenie a ukonči sa prehľedávanie ako neúspešné. Inak pokračuj.
    3. Vyber z čela fronty OPEN prvý uzol a umiestni ho do zoznamu CLOSED.
    4. Ak je vybraný uzol cieľový, ukonči prehľadávanie ako úspešné a vráť cestu od koreňového uzlu k cieľovému (vrací se postupnosť stavov). Inak pokračuj.
    5. Vybraný uzol expanduj a jeho bezprostredných následníkov, ktorí nie sú ani vo fronte OPEN, ani v zozname CLOSED, umiestni do fronty OPEN a vráť sa na bod 2.

  • porovnávanie generovaných uzlov je ale výpočetne náročné

Metóda rovnakých cien (UCS)

  • podobný algoritmus ako pri BFS, ale uvažuje skutočné ceny prechodov a skutočné ceny ciest
  1. Sestroj seznam OPEN (bude obsahovat všechny uzly určené k expanzi) a umísti do něj počáteční uzel včetně jeho (nulového) ohodnocení.
  2. Je-li seznam OPEN prázdný, pak úloha nemá řešení a ukonči proto prohledávání jako neúspěšné. Jinak pokračuj.
  3. Vyber ze seznamu OPEN uzel s nejnižším ohodnocením.
  4. Je-li vybraný uzel uzlem cílovým, ukonči prohledávání jako úspěšné a vrať cestu od kořenového uzlu k uzlu cílovému (vrací se posloupnost stavů, nebo operátorů). Jinak pokračuj.
  5. Vybraný uzel expanduj, všechny jeho bezprostřední následníky včetně jejich ohodnocení umísti do seznamu OPEN a vrať se na bod 2.
  • Ak je počet bezprostredných nasledovníkov každého uzlu konečný, je algoritmus BFS úplny a optimálny.
  • Časová aj pamäťová náročnosť je exponenciálna.
  • Modifikácie podobné ako pri BFS

Metóda slepého prehľadávania do hĺbky (DFS)

  1. Sestroj zásobník OPEN (bude obsahovat všechny uzly určené k expanzi) a umísti do něj počáteční uzel.
  2. Je-li zásobník OPEN prázdný, pak úloha nemá řešení a ukonči proto prohledávání jako neúspěšné. Jinak pokračuj.
  3. Vyber z vrcholu zásobníku OPEN první uzel.
  4. Je-li vybraný uzel uzlem cílovým, ukonči prohledávání jako úspěšné a vrať cestu od kořenového uzlu k uzlu cílovému (vrací se posloupnost stavů, nebo operátorů). Jinak pokračuj.
  5. Vybraný uzel expanduj, všechny jeho bezprostřední následníky umísti do zásobníku OPEN a vrať se na bod 2.

  • nie je ani úplny ani optimálny
  • časová náročnosť je exponenciálna
  • pamäťová náročnosť je lineárna
  • v základnej verzii je prakticky nepoužiteľný
  • Modifikácia:
    • 5. Vybraný uzel expanduj a umísti do zásobníku OPEN všechny jeho bezprostřední následníky, kteří v tomto zásobníku ještě nejsou a kteří nejsou ani předky generovaného uzlu.

  • zoznam CLOSED sa nepoužíva (stratila by sa tým výhoda lineárnej pamäťovej zložitosti)

Metóda obmedzeného prehľadávania do hĺbky (DLS)

  • Ak riešime úlohu, pri ktorej dokážeme odhadnúť hĺbku riešenia, môžeme problém s opakujúcimi sa uzlami riešiť obmedzením hĺbky prehľadávania.
  1. Sestroj zásobník OPEN a umísti do něj počáteční uzel s označením hloubky (0).
  2. Je-li zásobník OPEN prázdný, pak úloha nemá řešení a ukonči proto prohledávání jako neúspěšné. Jinak pokračuj.
  3. Vyber z vrcholu zásobníku OPEN první uzel.
  4. Je-li vybraný uzel uzlem cílovým, ukonči prohledávání jako úspěšné a vrať cestu od kořenového uzlu k uzlu cílovému (vrací se posloupnost stavů, nebo operátorů). Jinak pokračuj.
  5. Pokud je hloubka vybraného uzlu menší než zadaná maximální hloubka, tak tento uzel expanduj, všem jeho bezprostředním následníkům přiřaď hloubku o jedničku větší než je hloubka expandovaného uzlu a umísti je do zásobníku OPEN. Jinak pokračuj.
  6. Vrať se na bod 2.
  • nie je úplna ani optimálna
  • časová náročnosť je exponenciálna
  • pamäťová náročnosť je lineárna

Metóda postupného zanorovania do hĺbky (IDS)

  • použijeme ak nemáme dostatok pamäte na použitie metódy BFS
  • princíp je v opakovanom používaní metódy DLS s postupným zväčšévaním hĺbky zanorovania
  1. Nastav hloubku prohledávání na hodnotu 1.
  2. Použij metodu DLS. Skončí-li tato metoda úspěchem (nalezením cesty), skonči také úspěchem a vrať nalezenou cestu. Jinak pokračuj.
  3. Dosáhla-li hloubka prohledávání maximální hodnotu, skonči neúspěchem. Jinak inkrementuj hloubku prohledávání a vrať se na bod 2.
  • časová zložitosť je exponenciálna
  • pamäťová zložitosť je daná vzťahom O(bd)

Metóda spätného vracania (Backtracking)

  • namiesto expanzie uzlu sa generuje len jeho bezprostredný nasledovník a až v prípade neúspechu sa generuje ďalší uzol
  1. Sestroj zásobník OPEN (bude obsahovat uzly určené k expanzi) a umísti do něj počáteční uzel.
  2. Je-li zásobník OPEN prázdný, pak úloha nemá řešení a ukonči proto prohledávání jako neúspěšné. Jinak pokračuj.
  3. Jde-li na uzel na vršku zásobníku aplikovat první/další operátor, tak tento operátor aplikuj a pokračuj bodem 4, v opačném případě odstraň testovaný uzel z vrcholu zásobníku a vrať se na bod 2.
  4. Je-li nový vygenerovaný uzel, tj. uzel vzniklý aplikací operátoru na uzel na vršku zásobníku, uzlem cílovým, ukonči prohledávání jako úspěšné a vrať cestu od kořenového uzlu k uzlu cílovému (vrací se posloupnost stavů, nebo operátorů). Jinak ulož nový uzel na vršek zásobníku a vrať se na bod 2.

  • nie je úplna ani optimálna
  • časová náročnosť je exponenciálna
  • extrémne nízka pamäťová náročnosť - v zásobníku OPEN sú len uzly aktuálnej cesty
  • Modifikácia:
    • úprava bodu 4 - nový uzol sa do zásobníka OPEN neukladá ak sa v ňom už nachádza

Metóda obojsmerného prehľadávania (BS)

  • v úlohách, ktoré používajú inverzné operátory môžme prehľadávať statový priestor oboma smermi metódou BFS
  • od počiatočného stavu k cieľovému a zároveň od cieľového k počiatočnému
  • ak sa v každom smere prehľadáva polovičná hĺbka, klesá pamäťová zložitosť
  • časová zložitosť je exponenciálna

Informované metódy:

  • majú k dispozícii a používajú nejakú informáciu o cieľovom stave a majú prostriedky ako aktuálne stavy vyhodnotiť
  1. Sestroj seznam OPEN (bude obsahovat všechny uzly určené k expanzi) a umísti do něj počáteční uzel včetně jeho ohodnocení.
  2. Je-li seznam OPEN prázdný, pak úloha nemá řešení a ukonči proto prohledávání jako neúspěšné. Jinak pokračuj.
  3. Vyber ze seznamu OPEN uzel s nejlepším (nejnižším) ohodnocením.
  4. Je-li vybraný uzel uzlem cílovým, ukonči prohledávání jako úspěšné a vrať cestu od kořenového uzlu k uzlu cílovému (vrací se posloupnost stavů, nebo operátorů). Jinak pokračuj.
  5. Vybraný uzel expanduj, všechny jeho bezprostřední následníky, kteří nejsou jeho předky, umísti do seznamu OPEN, a to včetně jejich ohodnocení. Z uzlů, které se v seznamu OPEN vyskytují vícekrát, ponech pouze uzel s nejlepším ohodnocením, ostatní ze seznamu OPEN vyškrtni, a vrať se na bod 2.
  • rozdiel je v ohodnocovacej funkcii - cena cesty + heuristická funkcia (odhad ceny cesty z uzlu n do cieľového uzlu) (f(n) = g(n) + h(n))
  • ceny všetkých prechodov sú kladné
  • heuristická funkcia - čím je presnejšia, tým menšiu časť stavového priestoru potrebujeme prehľadávať
  • ohodnocuje uzly len heuristickou funkciou - na expanziu vybera uzol s najnizsou
  • dobrá heuristická funkcia môže výrazne zredukovať časovú zložitosť
  • nie je ani úplny ani optimálny
  • časová náročnosť je exponenciálna
  • pamäťová náročnosť je lineárna

Metóda A*

  • najznámejšia a najpoužívanejšia na prehľadávanie stavového priestoru
  • na ohodnotenie uzlov sa používa vzťah f(n) = g(n) + h(n)
  • heuristická funkcia musí byť spodný odhad
  • je úplná
  • pre prípustné heuristické funkcie je optimálna
  • expanduje len uzly pre ktoré platí f(sx) ⇐ f0, f0 je cena optimálnej cesty
  • časová aj pamäťová zložitosť záleží od použitej heuristiky

temata/24-reseni_uloh/stavovy_priestor.1301518098.txt.gz · Poslední úprava: 2011/03/30 22:48 autor: jasho
Starší verze
Zpětné odkazyNahoru
Recent changes RSS feed Debian Powered by PHP Valid XHTML 1.0 Valid CSS Driven by DokuWiki