OBSAH WEBU
ČTĚTE!
24d - Metódy založené na rozklade úloh na podproblémy
- 2 typy podproblémov :
- AND - problém je riešiteľný, keď sú všetky podproblémy riešiteľné
- OR - problém je riešiteľný, keď je aspoň jeden podproblém riešiteľný
AO algoritmus
- Sestroj prázdné seznamy OPEN a CLOSED. Do seznamu OPEN ulož počáteční uzel (problém).
- Vyjmi uzel zleva ze seznamu OPEN a označ jej jako uzel X.
- 3. bod:
- a) Je-li uzel (problém) X řešitelný, přenes informaci o jeho řešitelnosti jeho předchůdcům. Je-li řešitelný počáteční problém, ukonči řešení jako úspěšné - vytvoř a vrať relevantní část AND/OR grafu.
- b) Není-li uzel (problém) X řešitelný a nelze-li jej rozložit na podproblémy, přenes informaci o jeho neřešitelnosti jeho předchůdcům. Není-li řešitelný počáteční problém, ukonči řešení jako neúspěšné.
- c) Expanduj X (rozlož X na podproblémy) a všechny jeho následníky ulož do OPEN.
- Ulož X do CLOSED.
- Je-li seznam OPEN prázdný, ukonči řešení jako neúspěšné, jinak se vrať na bod 2.
AO* algoritmus
- informovaný algoritmus - ak vieme podproblémy ohodnotiť pomocou nejakej heuristickej funkcie
- Sestroj strukturu G pro reprezentaci AND/OR stromu a umísti do ní počáteční uzel s označením INIT s jeho ohodnocením. Urči hodnotu FUTILITY, která určuje maximální povolenou cenu řešení.
- Je-li uzel UNIT označen jako SOLVED, ukonči řešení jako úspěšné (řešení je dáno nejnadějnějším podstromem stromu G). Je-li hodnota uzlu INIT větší nebo rovna hodnotě FUTILITY, ukonči prohledávání jako neúspěšné. Jinak pokračuj.
- Procházej nejnadějnějším podstromem až narazíš na neexpandovaný uzel. Tento uzel označ NODE.
- Expanduj uzel NODE. Jestliže NODE nemá žádného následníka, přiřaď mu hodnotu FUTILITY (je ekvivalentní sdělení, že uzel není řešitelný) a přejdi na bod 7. Jinak pokračuj.
- Představují-li někteří bezprostřední následníci elementární úlohy, označ je jako SOLVED (tj. přiřaď jim nulové ohodnocení), u zbývajících ohodnocení odhadni (vypočítej).
- Připoj bezprostřední následníky uzlu NODE ke stromu G a přenes informace o jejich ohodnocení směrem nahoru k uzlu INIT takto:
- ohodnocení uzlů AND je rovno nenižšímu ohodnocení jeho bezprostředních následníků.
- ohodnocení uzlů OR je rovno nejvyššímu ohodnocení jeho bezprostředních následníků.
- V uzlech OR označ nejnadějnější podstromy (vždy hranu k nejlépe ohodnocenému bezprostřednímu následníku).
- Vrať se na bod 2.
