4.4. Problémaredukcióval reprezentált feladatok megoldáskereső módszerei

4.4.1. Visszalépéses megoldáskeresés ÉS/VAGY fák esetén

Legyen a probléma problémaredukciós reprezentációja. Egy visszalépéses megoldáskereső

  • adatbázisa a reprezentációs gráf egy a startcsúcsból induló hiperútját tartalmazza. Ezt az utat aktuális hiperútnak nevezzük. Az adatbázis az aktuális hiperút csúcsait és e csúcsokból kiinduló bizonyos hiperéleket (explicit vagy implicit módon) nyilvántartó csomópontokból épül fel.

    A keresés megkezdésekor az adatbázis egyetlen egy - a kezdőproblémát tartalmazó - csomópontból áll. Egy csomópont az alábbi információkat tartalmazza:

    • egy problémát;

    • arra a csomópontra mutatót, mely a szülő problémát (azt a problémát, melyre redukciós operátort alkalmazva előállt ) tartalmazza;

    • első részproblémáját ( első ÉS gyermekét) nyilvántartó csomópontra mutatót;

    • szülőjének -t követő részproblémáját ( következő ÉS testvérét) nyilvántartó csomópontra mutatót;

    • azt a redukciós operátort, mellyet -ra aktuálisan alkalmaztunk;

    • -ra a keresés során már alkalmazott (vagy még alkalmazható) redukciós operátorok halmazát.

  • A visszalépéses megoldáskeresők műveleteit egyrészt a redukciós operátorokból származtatjuk, továbbá alkalmazhatjuk a visszalépést.

    • Az redukciós operátorból nyert művelet

      • alkalmazási előfeltétele: a kiválasztott levél csomópontban található problémára alkalmazható , de még sikertelenül nem alkalmaztuk rá.

      • hatása:

    • A visszalépés

      • alkalmazási előfeltétele: van csomópont az adatbázisban.

      • hatása:

  • Az induló adatbázis létrehozása után kezdi el a vezérlő a keresést.

    • Ha elfogytak a csomópontok az adatbázisból az adott reprezentációban nincs megoldás.

    • Ha van nem egyszerű problémát tartalmazó levélcsomópont az adatbázisban, akkor a vezérlő választ egyet.

      • A kiválasztott problémára választ egy még sikertelenül ki nem próbált redukciós operátort, és alkalmazza.

      • Ha ilyen nincs, visszalép.

    • Ha a hiperút minden levél csomópontja egyszerű problémát tartalmaz előállt egy megoldás.

4.4.2. Keresőfával megoldáskeresés ÉS/VAGY fák esetén

Legyen a probléma problémaredukciós reprezentációja. A reprezentációs gráfot alakítsuk át olyan ÉS/VAGY gráffá, melyben minden csúcsból vagy csak VAGY élek, vagy csak egy ÉS élköteg indul ki.

Keresőfával megoldást keresés esetén az

  • adatbázis a reprezentációs gráf startcsúcsból induló felderített hiperútjai. Az adatbázis a hiperutak csúcsait és e csúcsokból kiinduló hiperéleket (explicit vagy implicit módon) nyilvántartó csomópontokból épül fel. A keresés megkezdésekor az adatbázis egyetlen egy - a kezdőproblémát tartalmazó - csomópontból áll. Egy csomópont az alábbi információkat tartalmazza:

    • egy problémát;

    • ha VAGY gyermek:

      • a szülő csomópontra mutatót;

      • azt a redukciós operátort, mellyel -t redukáljuk;

      • következő VAGY testvérét tartalmazó csúcsra mutatót;

      • első ÉS gyermekét nyilvántartó csomópontra mutatót;

    • ha ÉS gyermek

      • a szülő csomópontra mutatót;

      • következő ÉS testvérét nyilvántartó csomópontra mutatót;

      • első VAGY gyermekét nyilvántartó csomópontra mutatót;

    • címkét: megoldott / megoldhatatlan / folyamatban

  • művelete a kiterjesztés: a keresőfát annak egy folyamatban címkéjű levélcsomópontján keresztül kibővíti.

    • alkalmazási előfeltétele: a keresőfában van folyamatban címkéjű levélcsomópont.

    • hatása:

      • alkalmazzuk az összes alkalmazható redukciós operátort a folyamatban címkéjű levélcsomópont problémájára,

      • az előálló problémákat új csomópontokként felfűzzük a keresőfába megfelelő címkékkel:

        • megoldott, ha az előállt probléma egyszerű;

        • folyamatban, ha az előállt probléma nem egyszerű;

      • módosítjuk a keresőfa csúcsainak címkéit.

    • Ha a gyökér csomópont címkéje megoldott, előállt az adatbázisban egy megoldás.

    • Ha a gyökér csomópont címkéje megoldhatatlan, nincs a reprezentáció mellett a problémának megoldása.

    • Ha a gyökér csomópont címkéje folyamatban, a vezérlő megmondja, hogy melyik folyamatban címkéjű levélcsomópont legyen a következő lépésben kiterjesztve.