Obsah

Export page to Open Document format

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

Neinformované (slepé) metódy:

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.

Metóda rovnakých cien (UCS)

  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.

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.

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

  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.

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

  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.

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

  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.

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

Informované metódy:

  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.

Metóda A*