Chapter 2. Megoldást kereső rendszerek

Az állapottérgráfban keressük a megoldást: a start csúcsból valamely terminális csúcsba vezető utat. Az állapottérgráfot implicit módon — az állapottér-reprezentáció megadásával — adjuk meg a megoldást kereső rendszereknek. Ezek a keresés során addig és úgy építik a gráfot, amíg megoldást nem találnak, vagy amíg valamilyen ok miatt kudarcot nem vallanak a kereséssel.

A megoldást kereső rendszerek felépítése:

A megoldáskereső vezérlője az alábbi séma szerint működik:


         procedure Kereső(A, kezdő, C, O)
  adatbázis ← Inicializál(kezdő)
  while Igaz do
    if Megoldás-Talál(adatbázis) then
      break
    end 
         if
    if Nem-Folytat(adatbázis) then
      break
    end 
         if
    művelet ← Választ(adatbázis,műveletek)
    adatbázis ← Alkalmaz(adatbázis,művelet)
  end 
         while
  if Megoldás-Talál(adatbázis) then
    Megoldás-Kiír(adatbázis)
  else
    print „Sikertelen keresés”
  end 
         if

         end 
         procedure

      

A megoldást kereső rendszerek különböző szempontok alapján osztályozhatók:

A megoldáskereső rendszerek értékelési szempontjai:

2.1. Nemmódosítható megoldáskereső rendszerek

A MI módszereit nem használó, ún. hagyományos feladatmegoldási módoknál alkalmazzák. A MI problémák megoldása során nem tudjuk, hogy a reprezentációs gráf megfelelő — a megoldást is tartalmazó — részét építjük-e, ezért ritkán alkalmazunk nemmódosítható keresést az MI területén.

Legyen . Egy nemmódosítható megoldáskereső rendszer

  • adatbázisa az állapottérgráf egyetlen csúcsa, az ún. aktuális csúcs;

  • műveletei az állapottér-reprezentációs operátorok;

  • vezérlője:

    
                            procedure Nemmódosítható-Kereső(A, kezdő, C, O)
      aktuális ← kezdő
      while Igaz do
        if aktuális ∈ C then
          break
        end 
                            if
        O′ ← {o | o ∈ O ∧ Előfeltétel(aktuális, o)}
        if 
                            not O′ = ∅ then
          operátor ← Választ(O′)
          aktuális ← Alkalmaz(aktuális, operátor)
        else
          break
        end 
                            if
      end 
                            while
      if aktuális ∈ C then
        print aktuális
      else
        print „Sikertelen keresés”
      end 
                            if
    
                            end 
                            procedure
    
                         

Csak olyan probléma megoldásánál alkalmazhatjuk, ahol egy a célfeltételeknek eleget tevő állapotot kell előállítani!

Ugyanazon probléma megoldásának keresése esetén a választás módjában lehet lényeges eltérés. Választhatunk:

  • irányítatlanul, szisztematikusan

    • előre rögzített operátorsorrend alapján

    • véletlenszerűen: próba-hiba módszer

  • heurisztikusan: hegymászó módszer

    Becsüljük meg a ún. heurisztikus függvénnyel, hogy az egyes állapotokból legkevesebb hány operátor alkalmazásával érhetünk célállapotba:

    Equation 2.. 


    egyébként .

    Ha az állapot az aktuális, becsüljük meg segítségével, hogy milyen „távol” van a hozzá legközelebbi céltól: .

    Legyen

    Equation 2.. 


    Azt az -beli t fogjuk alkalmazni -ra, amelyik a becslésünk szerint a legközelebb visz valamelyik terminálishoz:

    Equation 2.. 



            procedure Hegymászó-Algoritmus(A, kezdő, C, O )
  aktuális ← kezdő
  while Igaz do
    if aktuális ∈ C then
      break
    end 
            if
    O′ ← {o | o ∈ O ∧ Előfeltétel(aktuális, o) ∧ h(Alkalmaz(aktuális, o)) ≤ h(aktuális)}
    if 
            not O′ = ∅ then
      operátor ← Választ({o | o ∈ O′ ∧ ∀o′(o′ ∈ O′ ⊃ h(Alkalmaz(aktuális, o)) ≤ h(Alkalmaz(aktuális, o′)))})
      aktuális ← Alkalmaz(aktuális, operátor)
    else
      break
    end 
            if
  end 
            while
  if aktuális ∈ C then
    print aktuális
  else
    print „Sikertelen keresés”
  end 
            if

            end 
            procedure

         

A nemmódosítható megoldáskereső rendszerek értékelése:

  • Teljesség: Nem teljesek.

    • Próba-hiba módszer: Ha olyan kört nem tartalmazó véges állapottérgráfokban keresünk, melyekben minden csúcsból vezet valamelyik terminális csúcsba irányított út, akkor előállít egy célállapotot.

    • A hegymászó módszer esetén a heurisztika pontosságától függ, hogy a megoldást megtaláljuk-e vagy sem.

  • Tárigény: Rendkívül kis adatbázissal dolgozik.