2.2. Módosítható megoldáskereső rendszerek

2.2.1. A visszalépéses megoldáskeresés algoritmusa

Legyen . Az alap visszalépéses megoldáskereső

  • adatbázisa egy a startcsúcsból induló, az ún. aktuális csúcsba vezető utat, az aktuális utat tartalmazza, az út csúcsait és a csúccsal kapcsolatban lévő éleket nyilvántartó csomópontokból épül fel. Egy csomópont az alábbi információkat tartalmazza:

    • egy állapotot;

    • arra a csomópontra mutatót, mely a szülő állapotot (azt az állapotot, melyre operátort alkalmazva előállt ) tartalmazza;

    • azt az operátort, melyet a szülő állapotra alkalmazva előállt ;

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

  • műveletei

    • az operátorokból származtatott műveletek: egy operátorra épülő művelet

      • alkalmazási előfeltétele: az aktuális csomópont állapotára alkalmazható , de a keresés során erre az állapotra (ezen az úton) még nem alkalmaztuk.

      • hatása: az aktuális csomópont állapotára alkalmazzuk az operátort, az előálló állapotból új aktuális csomópontot készítünk az adatbázisban

    • a visszalépés

      • alkalmazási előfeltétele: van (aktuális) csomópont az aktuális úton.

      • hatása:

  • vezérlője eldönti, hogy az adatbázisra mikor melyik műveletet kell végrehajtani, ha még nem teljesülnek a megállási feltételek.


               procedure Alap-Backtrack-1(A, kezdő, C,O)
  Állapot[aktuális-csomópont] ← kezdő
  Szülő[aktuális-csomópont] ← Nil
  Operátor[aktuális-csomópont] ← ∗
  Kipróbált[aktuális-csomópont] ← ∅
  while Igaz do
    if aktuális-csomópont = Nil then
      break
    end 
               if
    if Állapot[aktuális-csomópont] ∈ C then
      break
    end 
               if
    O′ ← {o | o ∈ O ∧ Előfeltétel(Állapot[aktuális-csomópont], o) ∧ o ∉ Kipróbált[aktuális-csomópont]}
    if 
               not O′ = ∅ then
      operátor ← Választ(O′)
      Kipróbált[aktuális-csomópont] ← Kipróbált[aktuális-csomópont]∪{operátor}
      Állapot[új] ← Alkalmaz(Állapot[aktuális-csomópont], operátor)
      Szülő[új] ← aktuális-csomópont
      Operátor[új] ← operátor
      Kipróbált[új] ← ∅
      aktuális-csomópont ← új
    else
      aktuális-csomópont ← Szülő[aktuális-csomópont]
    end 
               if
  end 
               while
  if 
               notaktuális-csomópont = Nil then
    Megoldás-Kiír(aktuális-csomópont )
  else
    print „Nincs megoldás”
  end 
               if

               end 
               procedure

            

               procedure Alap-Backtrack-2(A, kezdő, C,O)
  Állapot[aktuális-csomópont] ← kezdő
  Szülő[aktuális-csomópont] ← Nil
  Operátor[aktuális-csomópont] ← ∗
  Alkalmazható[aktuális-csomópont] ← {o | o ∈ O ∧ Előfeltétel(Állapot[aktuális-csomópont], o)}
  while Igaz do
    if aktuális-csomópont = Nil then
      break
    end 
               if
    if Állapot[aktuális-csomópont] ∈ C then
      break
    end 
               if
    if 
               not Alkalmazható[aktuális-csomópont] = ∅ then
      operátor ← Választ(Alkalmazható[aktuális-csomópont])
      Alkalmazható[aktuális-csomópont] ← Alkalmazható[aktuális-csomópont] \ {operátor}
      Állapot[új] ← Alkalmaz(Állapot[aktuális-csomópont], operátor)
      Szülő[új] ← aktuális-csomópont
      Operátor[új] ← operátor
      Alkalmazható[új] ← {o | o ∈ O ∧ Előfeltétel(Állapot[új], o)}
      aktuális-csomópont ← új
    else
      aktuális-csomópont ← Szülő[aktuális-csomópont]
    end 
               if
  end 
               while
  if 
               not aktuális-csomópont = Nil then
    Megoldás-Kiír(aktuális-csomópont )
  else
    print „Nincs megoldás”
  end 
               if

               end 
               procedure

            

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

  • heurisztikusan: Becsüljük meg a heurisztikával, hogy az egyes csúcsok milyen távol vannak a hozzájuk legközelebbi terminális csúcstó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.. 


Az alap visszalépéses megoldáskeresők értékelése

  • Teljesség: Ha a reprezentációs gráf köröket nem tartalmazó véges gráf, akkor az alap visszalépéses megoldáskereső véges sok keresőlépés megtétele után befejezi a keresést,

    • ha van megoldás, előállít egy lehetséges megoldást,

    • ha nincs megoldás, azt felismeri.

  • Tárigény: Kis méretű az adatbázis.

2.2.2. Visszalépéses megoldáskeresés köröket is tartalmazó gráfokban

  • Visszalépéses megoldáskeresés körfigyeléssel: Ha van megoldás, akkor van körmentes megoldás is. A vezérlő a visszalépést választja, ha az aktuális csúcs szerepelt már az aktuális úton.

  • Visszalépéses megoldáskeresés úthosszkorláttal: Úthosszkorlátot vezetünk be, mely megakadályozza, hogy a köröket „végtelen sokszor” járjuk be. A vezérlő a visszalépést választja, ha az aktuális út hossza eléri, vagy meghaladja az úthosszkorlátot.


               procedure Körfigyeléses-Backtrack(A, kezdő, C,O)
  Állapot[aktuális-csomópont] ← kezdő
  Szülő[aktuális-csomópont] ← Nil
  Operátor[aktuális-csomópont] ← ∗
  Alkalmazható[aktuális-csomópont] ← {o | o ∈ O ∧ Előfeltétel(Állapot[aktuális-csomópont], o)}
  while Igaz do
    if aktuális-csomópont = Nil then
      break
    end 
               if
    if Állapot[aktuális-csomópont] ∈ C then
      break
    end 
               if
    if VoltMár(Állapot[aktuális-csomópont ]) then
      aktuális-csomópont ← Szülő[aktuális-csomópont]
    end 
               if
    if 
               not Alkalmazható[aktuális-csomópont] = ∅ then
      operátor ← Választ(Alkalmazható[aktuális-csomópont])
      Alkalmazható[aktuális-csomópont] ← Alkalmazható[aktuális-csomópont] \ {operátor}
      Állapot[új] ← Alkalmaz(Állapot[aktuális-csomópont], operátor)
      Szülő[új] ← aktuális-csomópont
      Operátor[új] ← operátor
      Alkalmazható[új] ← {o | o ∈ O ∧ Előfeltétel(Állapot[új], o)}
      aktuális-csomópont ← új
    else
      aktuális-csomópont ← Szülő[aktuális-csomópont]
    end 
               if
  end 
               while
  if 
               not aktuális-csomópont = Nil then
    Megoldás-Kiír(aktuális-csomópont )
  else
    print „Nincs megoldás”
  end 
               if

               end 
               procedure

            

               procedure Úthosszkorlátos-Backtrack(A, kezdő, C,O, korlát )
  Állapot[aktuális-csomópont] ← kezdő
  Szülő[aktuális-csomópont] ← Nil
  Mélység[aktuális-csomópont] ← 0
  Operátor[aktuális-csomópont] ← ∗
  Alkalmazható[aktuális-csomópont] ← {o | o ∈ O ∧ Előfeltétel(Állapot[aktuális-csomópont], o)}
  while Igaz do
    if aktuális-csomópont = Nil then
      break
    end 
               if
    if Állapot[aktuális-csomópont] ∈ C then
      break
    end 
               if
    if Mélység[aktuális-csomópont] = korlát then
      aktuális-csomópont ← Szülő[aktuális-csomópont]
    end 
               if
    if 
               not Alkalmazható[aktuális-csomópont] = ∅ then
      operátor ← Választ(Alkalmazható[aktuális-csomópont])
      Alkalmazható[aktuális-csomópont] ← Alkalmazható[aktuális-csomópont] \ {operátor}
      Állapot[új] ← Alkalmaz(Állapot[aktuális-csomópont], operátor)
      Szülő[új] ← aktuális-csomópont
      Mélység[új] ← Mélység[aktuális-csomópont] + 1
      Operátor[új] ← operátor
      Alkalmazható[új] ← {o | o ∈ O ∧ Előfeltétel(Állapot[új], o)}
      aktuális-csomópont ← új
    else
      aktuális-csomópont ← Szülő[aktuális-csomópont]
    end 
               if
  end 
               while
  if 
               not aktuális-csomópont = Nil then
    Megoldás-Kiír(aktuális-csomópont )
  else
    print „Sikertelen keresés”
  end 
               if

               end 
               procedure

            

Értékelés

  • Teljesség:

    • A körfigyeléses backtrack ha a reprezentációs gráf véges, akkor véges sok keresőlépés megtétele után befejezi a keresést, és

      • ha van megoldás, előállít egy körmentes megoldást,

      • ha nincs megoldás, azt felismeri.

    • Az úthosszkorlátos backtrack tetszőleges reprezentációs gráf esetén véges sok keresőlépés megtétele után befejezi a keresést,

      • ha van az úthosszkorlátnál nem hosszabb megoldás, előállít egy ilyen megoldást.

      • Ha keresés nem egy megoldás megtalálásával ér véget, akkor az úthosszkorlátnál csak hosszabb megoldás lehet a reprezentációs gráfban. (Vagy nincs megoldás, vagy az úthosszkorlát túl kicsi.)

  • Időigény:

    • A körfigyeléses backtrack időigényes (főleg hosszú körök esetén).

  • Tárigény:

    • Az úthosszkorlátos backtrack adatbázisa legfeljebb úthosszkorlátnyi elemet tartalmaz. A megtalált megoldás nem feltétlen körmentes.

2.2.3. Ág és korlát algoritmus

A backtrack alkalmas optimális (legrövidebb) megoldás keresésére is.

  • Egy induló úthosszkorlátnál nem hosszabb megoldást keresünk.

  • Ha találunk ilyet, tároljuk, majd ennek hosszát új úthosszkorlátnak választva folytatjuk a keresést.

Úthosszkorlát helyett költségkorlátot, csomópont mélysége helyett pedig az addig tartó út költségét is használhatjuk az algoritmusban. Ekkor legkisebb költségű megoldás előállítása lehet a cél.


               procedure Ág-és-Korlát(A, kezdő, C,O, korlát )
  talált ← Hamis
  Állapot[aktuális-csomópont] ← kezdő
  Szülő[aktuális-csomópont] ← Nil
  Mélység[aktuális-csomópont] ← 0
  Operátor[aktuális-csomópont] ← ∗
  Alkalmazható[aktuális-csomópont] ← {o | o ∈ O ∧ Előfeltétel(Állapot[aktuális-csomópont], o)}
  while Igaz do
    if aktuális-csomópont = Nil then
      break
    end 
               if
    if Állapot[aktuális-csomópont] ∈ C then
      talált ← Igaz
      Megoldás-Feljegyez(aktuális-csomópont )
      korlát ← Mélység[aktuális-csomópont]
    end 
               if
    if Mélység[aktuális-csomópont] = korlát then
      aktuális-csomópont ← Szülő[aktuális-csomópont]
    end 
               if
    if 
               not Alkalmazható[aktuális-csomópont] = ∅ then
      operátor ← Választ(Alkalmazható[aktuális-csomópont])
      Alkalmazható[aktuális-csomópont] ← Alkalmazható[aktuális-csomópont] \ {operátor}
      Állapot[új] ← Alkalmaz(Állapot[aktuális-csomópont], operátor)
      Szülő[új] ← aktuális-csomópont
      Mélység[új] ← Mélység[aktuális-csomópont] + 1
      Operátor[új] ← operátor
      Alkalmazható[új] ← {o | o ∈ O ∧ Előfeltétel(Állapot[új], o)}
      aktuális-csomópont ← új
    else
      aktuális-csomópont ← Szülő[aktuális-csomópont]
    end 
               if
  end 
               while
  if talált then
    Megoldás-Kiír
  else
    print „Sikertelen keresés”
  end 
               if

               end 
               procedure

            

Értékelés

  • Optimalitás: Az ág és korlát algoritmus tetszőleges reprezentációs gráf esetén véges sok keresőlépés megtétele után befejezi a keresést,

    • ha van az induló úthosszkorlátnál nem hosszabb megoldás, a legrövidebb megoldást állítja elő,

    • ha a keresés nem megoldás megtalálásával ér véget, akkor az induló úthosszkorlátnál csak hosszabb megoldás lehet a reprezentációs gráfban. (Vagy nincs megoldás, vagy az induló úthosszkorlát túl kicsi.)

  • Tárigény:

    • Az ág és korlát adatbázisa legfeljebb kétszer az induló úthosszkorlátnyi csomópontot tartalmaz.

2.2.4. Keresőfával keresők

Legyen . A keresőfával kereső rendszerek

  • adatbázisa a reprezentációs gráf már bejárt részét feszítő fa, az ún. keresőfa. A keresőfa csúcsait és a velük kapcsolatban lévő éleket (explicit vagy implicit módon) nyilvántartó csomópontok az alábbi információkat tartalmazzák:

    • egy állapotot;

    • arra a csomópontra mutatót, mely a szülő állapotot tartalmazza;

    • azt az operátort, melyet a szülő állapotra alkalmazva előállt ;

    • :

      • zárt, ha utódait tartamazó csomópontokat a keresés során már előállítottuk;

      • nyílt, egyébként.

  • művelete a kiterjesztés: a keresőfát annak egy nyílt csúcsán (egy nyílt csomóponton) keresztül kibővíti.

    • alkalmazási előfeltétele, hogy a keresőfában legyen nyílt csomópont.

    • hatása:

      • alkalmazzuk az összes alkalmazható operátort a nyílt csomópont állapotára,

      • az előálló állapotok közül

        • amelyek még nem szerepeltek a keresőfa egyetlen csomópontjában sem, azokból a keresőfába felfűzött új nyílt csomópont készül,

        • amelyek már szerepeltek a keresőfa valamely csomópontjában, azok sorsa keresőfüggő.

      • a kiterjesztett csomópont zárttá válik.

  • vezérlő megmondja, hogy melyik nyílt csomópont legyen a következő lépésben kiterjesztve.

    • Ha a kiválasztott nyílt csomópont állapota teljesíti a célfeltételeket, a keresőfában a szülőre mutatók mentén elő tudunk állítani egy megoldást is.

    • Nincs megoldás, ha egyetlenegy nyílt csomópont sincs a keresőfában.


               procedure Keresőfával-Kereső(A, kezdő, C,O)
  Állapot[csomópont] ← kezdő
  Szülő[csomópont] ← Nil
  Operátor[csomópont] ← ∗
  nyíltak ← {csomópont}; zártak ← ∅
  while Igaz do
    if nyíltak = ∅ then
      break
    end 
               if
    csomópont ← Választ(nyíltak)
    if Állapot[csomópont] ∈ C then
      break
    end 
               if
    Kiterjeszt(csomópont, nyíltak, zártak)
  end 
               while
  if 
               not nyíltak = ∅ then
    Megoldás-Kiír(csomópont )
  else
    print „Nincs megoldás”
  end 
               if

               end 
               procedure

            

Ugyanazon probléma megoldásának keresése esetén lényeges eltérés lehet

  1. a választás módjában. A vezérlő választhat

    • irányítatlanul, szisztematikusan

      • a csomópontok keresőgráfbeli mélysége alapján: szélességi és mélységi keresők;

      • a csomópontok állapotait előállító költség alapján: optimális kereső;

    • heurisztikusan:

      • best-first algoritmus;

      • A algoritmusok.

  2. abban, hogy mi történik, ha a keresőgráf egy csúcsához a keresés során újabb odavezető utat tár fel a vezérlő.

  3. a célfeltételek vizsgálatának időpontjában.

2.2.5. Szélességi és mélységi keresők

1. Egy csomópont előállításakor követjük, hogy a csomópontban nyilvántartott csúcs a keresőfában milyen „mélyen” van:

Equation 2.. 


Kiterjesztésre

  • a szélességi kereső vezérlője a legkisebb mélységi számú

  • a mélységi kereső vezérlője a legnagyobb mélységi számú

nyílt csomópontot választja ki.

2. Ha a vezérlő a keresőgráf egy csúcsához a keresés során újabb odavezető utat tár fel, ezt nem tárolja, „elfelejti”.

3. A célfeltételek teljesítésének vizsgálatát előre hozhatjuk az állapot előállítását követő időpontra.


               procedure Kiterjeszt(A, kezdő, C,O, csomópont, nyíltak, zártak)
  for 
               all o ∈ O do
    if Előfeltétel(Állapot[csomópont ], o) then
      állapot ← Alkalmaz(Állapot[csomópont],o)
      ny ← Keres(nyíltak, állapot)
      z ← Keres(zártak, állapot)
      if ny = Nil and z = Nil then
        Állapot[új-csomópont] ← állapot
        Szülő[új-csomópont] ← csomópont
        Operátor[új-csomópont] ← o
        Mélység[új-csomópont] ← Mélység[csomópont] + 1
        nyíltak ← nyíltak ∪ {új-csomópont}
      end 
               if
    end 
               if
  end 
               for
  nyíltak ← nyíltak \ {csomópont}
  zártak ← zártak ∪ {csomópont}
end 
               procedure

            

               procedure Szélességi-Kereső(A, kezdő, C,O)
  Állapot[új-csomópont] ← kezdő
  Szülő[új-csomópont] ← Nil
  Operátor[új-csomópont] ← ∗
  Mélység[új-csomópont] ← 0
  nyíltak ← {új-csomópont}
  zártak ← ∅
  while Igaz do
    if nyíltak = ∅ then
      break
    end 
               if
    csomópont ← Választ({cs | cs ∈ nyíltak ∧ ∀cs′(cs′ ∈ nyíltak ⊃ Mélység[cs] ≤ Mélység[cs′])})
    if Állapot[csomópont] ∈ C then
      break
    end 
               if
    Kiterjeszt(A, kezdő, C, O, csomópont, nyíltak, zártak)
  end 
               while
  if 
               not nyíltak = ∅ then
    Megoldás-Kiír(csomópont )
  else
    print „Nincs megoldás”
  end 
               if

               end 
               procedure

            

               procedure Mélységi-Kereső(A, kezdő, C, O)
  Állapot[új-csomópont] ← kezdő
  Szülő[új-csomópont] ← Nil
  Operátor[új-csomópont] ← ∗
  Mélység[új-csomópont] ← 0
  nyíltak ← {új-csomópont}
  zártak ← ∅
  while Igaz do
    if nyíltak = ∅ then
      break
    end 
               if
    csomópont ← Választ({cs | cs ∈ nyíltak ∧ ∀cs′(cs′ ∈ nyíltak ⊃ Mélység[cs] ≥ Mélység[cs′])})
    if Állapot[csomópont] ∈ C then
      break
    end 
               if
    Kiterjeszt(A, kezdő, C, O, csomópont, nyíltak, zártak)
  end 
               while
  if 
               not nyíltak = ∅ then
    Megoldás-Kiír(csomópont)
  else
    print „Nincs megoldás”
  end 
               if

               end 
               procedure

            

A nyílt csomópontokat gyakran

  • a szélességi kereső sorban,

  • a mélységi kereső veremben

tartja nyilván, melyből mélységi szám szerint ezek épp megfelelő sorrendben kerülnek ki.

2.2.5.1. A szélességi kereső értékelése

  • Teljesség: A vezérlő,

    • ha van megoldás, tetszőleges reprezentációs gráfban véges sok keresőlépés után előállít egy megoldást,

    • ha nincs az adott reprezentációban megoldás, akkor (véges gráf esetén) azt a nyílt csomópontok elfogyásával felismeri.

  • Optimalitás: Ha van megoldás, tetszőleges reprezentációs gráfban a vezérlő a legrövidebb megoldást állítja elő.

  • Tárigény: Nagy az adatbázis. Legyen a reprezentációs fa minden csúcsának gyermeke, és hosszúságú a legrövidebb megoldás. Ekkor a keresőgráf csomópontjainak száma a keresés végére (a legrosszabb esetben):

    Equation 2.. 


2.2.5.2. A mélységi kereső értékelése

  • Teljesség: A vezérlő véges reprezentációs gráfban,

    • ha van megoldás, véges sok keresőlépés után előállít egy megoldást,

    • ha nincs a problémának az adott reprezentációban megoldása, akkor azt a nyílt csomópontok elfogyásával felismeri.

2.2.6. Optimális kereső

1. Minden csomópontnál számon tartjuk az odavezető keresőfabeli út költségét:

Equation 2.. 


jelölje a startcsúcsból -be jutás optimális költségét. Ekkor

Equation 2.. 


Kiterjesztésre az optimális kereső vezérlője a legkisebb költségű nyílt csomópontot választja ki.

2. Ha a vezérlő a keresőgráf egy csúcsához a keresés során újabb odavezető utat tár fel, azaz az csomópont kiterjesztéskor előállt állapot szerepel már a keresőgráf csomópontjában

  • nyíltként: és ha az

    Equation 2.. 


    ekkor az új kisebb költségű utat tároljuk, a régit „elfelejtjük”.

  • zártként: az csomópontot már kiterjesztése előtt kiterjesztette a vezérlő, azaz volt, így

    Equation 2.. 


    Az -hez feltárt új út költségesebb.

3. A célfeltételek vizsgálatát nem hozhatjuk előre.


               procedure Kiterjeszt(A, kezdő, C, O, költség, csomópont, nyíltak, zártak)
  for 
               all o ∈ O do
    if Előfeltétel(Állapot[csomópont ], o) then
      állapot ← Alkalmaz(Állapot[csomópont],o)
      ny ← Keres(nyíltak, állapot)
      z ← Keres(zártak, állapot)
      if ny = Nil and z = Nil then
        Állapot[új-csomópont] ← állapot
        Szülő[új-csomópont] ← csomópont
        Operátor[új-csomópont] ← o
        Útköltség[új-csomópont] ← Útköltség[csomópont] + költség(o,Állapot[csomópont])
        nyíltak ← nyíltak ∪ {új-csomópont}
      else 
               if 
               not ny = Nil then
        új-út-költség ← Útköltség[csomópont] + költség(o,Állapot[csomópont])
        if új-út-költség ≤ Útköltség[ny] then
          Szülő[ny] ← csomópont
          Operátor[ny] ← o
          Útköltség[ny] ← új-út-költség
        end 
               if
      end 
               if
    end 
               if
  end 
               for
  nyíltak ← nyíltak \ {csomópont}
  zártak ← zártak ∪ {csomópont}
end 
               procedure

            

               procedure Optimális-Kereső(A, kezdő, C, O, költség)
  Állapot[új-csomópont] ← kezdő
  Szülő[új-csomópont] ← Nil
  Operátor[új-csomópont] ← ∗
  Útköltség[új-csomópont] ← 0
  nyíltak ← {új-csomópont}
  zártak ← ∅
  while Igaz do
    if nyíltak = ∅ then
      break
    end 
               if
    csomópont ← Választ({cs | cs ∈ nyíltak ∧ ∀cs′(cs′ ∈ nyíltak ⊃ Útköltség[cs] ≤ Útköltség[cs′])})
    if Állapot[csomópont] ∈ C then
      break
    end 
               if
    Kiterjeszt(A, kezdő, C, O, költség, csomópont, nyíltak, zártak)
  end 
               while
  if 
               not nyíltak = ∅ then
    Megoldás-Kiír(csomópont)
  else
    print „Nincs megoldás”
  end 
               if

               end 
               procedure

            

2.2.6.1. Az optimális kereső értékelése

  • Teljesség: A vezérlő,

    • ha van megoldás, tetszőleges reprezentációs gráfban véges sok keresőlépés után előállít egy megoldást,

    • ha nincs a problémának az adott reprezentációban megoldása, akkor véges gráf esetén azt a nyílt csomópontok elfogyásával felismeri.

  • Optimalitás: Ha van megoldás, tetszőleges reprezentációs gráfban a vezérlő véges sok keresőlépés után az optimális megoldást állítja elő.

2.2.7. Best-first algoritmus

1. A keresőfa minden csomópontjánál nyilvántartjuk, hogy a csomópontbeli állapot a heurisztikus függvény szerint milyen „távol” van a hozzá legközelebbi céltól. Kiterjesztésre a best-first vezérlője a legkisebb heurisztikájú nyílt csomópontot választja ki (legjobb irányban haladó keresés).

2. Ha a vezérlő a keresőgráf egy csúcsához a keresés során újabb odavezető utat tár fel, ezt nem tárolja, „elfelejti”.

3. A célfeltételek vizsgálatát előre hozhatjuk.


               procedure Kiterjeszt(A, kezdő, C, O h, csomópont, nyíltak, zártak)
  for 
               all o ∈ O do
    if Előfeltétel(Állapot[csomópont ], o) then
      állapot ← Alkalmaz(Állapot[csomópont],o)
      ny ← Keres(nyíltak, állapot)
      z ← Keres(zártak, állapot)
      if ny = Nil and z = Nil then
        Állapot[új-csomópont] ← állapot
        Szülő[új-csomópont] ← csomópont
        Operátor[új-csomópont] ← o
        Heurisztika[új-csomópont] ← h(állapot)
        nyíltak ← nyíltak ∪ {új-csomópont}
      end 
               if
    end 
               if
  end 
               for
  nyíltak ← nyíltak \ {csomópont}
  zártak ← zártak ∪ {csomópont}
end 
               procedure

            

               procedure Best-First( A, kezdő, C, O, h)
  Állapot[új-csomópont] ← kezdő
  Szülő[új-csomópont] ← Nil
  Operátor[új-csomópont] ← ∗
  Heurisztika[új-csomópont] ← h(kezdő)
  nyíltak ← {új-csomópont}
  zártak ← ∅
  while Igaz do
    if nyíltak = ∅ then
      break
    end 
               if
    csomópont ←Választ({cs | cs ∈ nyíltak ∧ ∀cs′(cs′ ∈ nyíltak ⊃ Heurisztika[cs] ≤ Heurisztika[cs′])})
    if Állapot[csomópont] ∈ C then
      break
    end 
               if
    Kiterjeszt(A, kezdő, C, O, h, csomópont, nyíltak, zártak)
  end 
               while
  if 
               not nyíltak = ∅ then
    Megoldás-Kiír(csomópont )
  else
    print „Nincs megoldás”
  end 
               if

               end 
               procedure

            

2.2.7.1. A best-first algoritmus értékelése

  • Teljesség: A vezérlő tetszőleges véges reprezentációs gráfban,

    • ha van megoldás, véges sok keresőlépés után előállít egy megoldást,

    • ha nincs a problémának az adott reprezentációban megoldása, akkor azt a nyílt csomópontok elfogyásával felismeri.

  • Tárigény: Perfekt heurisztika esetén, ha a reprezentációs fa minden csúcsának gyermeke van, és hosszú a legrövidebb megoldás, a keresőgráf csomópontjainak száma a keresés végére:

    Equation 2.. 


2.2.8. Az A algoritmus

1. A keresőgráf minden csomópontjában megbecsüljük a rajta keresztülhaladó megoldás költségét. Ez egyrészt a csomópontig vezető nyilvántartott út költsége, amihez hozzászámítjuk a célig hátralevő út becsült költségét:

Equation 2.. 


azaz

Equation 2.. 


ha Ha -mel jelöljük az csúcson keresztül célba jutás optimális költségét, akkor minden csúcsra

Equation 2.. 


Kiterjesztésre az A algoritmus vezérlője a legkisebb összköltségű nyílt csomópontot választja ki.

2. Ha a vezérlő a keresőgráf egy csúcsához a keresés során újabb odavezető utat tár fel, azaz az csomópont kiterjesztéskor előállt állapot szerepel már a keresőgráf csomópontjában, és az

Equation 2.. 


ekkor az új kisebb költségű utat tároljuk, a régit „elfelejtjük”.

  • Ha nyílt volt, más teendő nincs.

  • Ha zárt volt, a keresőfa -ből induló részének csomópontjaiban az -et frissíteni kell, ami problémát okoz:

    • külön eljárást írunk a frissítésre;

    • az A algoritmussal frissíttetjük a részgráfot;

    • megelőzzük a probléma kialakulását.

3. A célfeltételek vizsgálatát nem hozhatjuk előre.


               procedure Kiterjeszt(A, kezdő, C, O, költség, h, csomópont, nyíltak, zártak)
  for 
               all o ∈ O do
    if Előfeltétel(Állapot[csomópont ], o) then
      állapot ← Alkalmaz(Állapot[csomópont],o)
      ny ← Keres(nyíltak, állapot)
      z ← Keres(zártak, állapot)
      if ny = Nil and z = Nil then
        Állapot[új-csomópont] ← állapot
        Szülő[új-csomópont] ← csomópont
        Operátor[új-csomópont] ← o
        Útköltség[új-csomópont] ← Útköltség[csomópont] + költség(o,Állapot[csomópont])
        Heurisztika[új-csomópont] ← h(állapot)
        nyíltak ← nyíltak ∪ {új-csomópont}
      else
        új-út-költség ← Útköltség[csomópont] + költség(o,Állapot[csomópont])
        if 
               not ny = Nil then
          if új-út-költség ≤ Útköltség[ny] then
            Szülő[ny] ← csomópont
            Operátor[ny] ← o
            Útköltség[ny] ← új-út-költség
          end 
               if
        else
          if új-út-költség ≤ Útköltség[z] then
            Szülő[z] ← csomópont
            Operátor[z] ← o
            Útköltség[z] ← új-út-költség
            zártak ← zártak \ {z}
            nyíltak ← nyíltak ∪ {z}
          end 
               if
        end 
               if
      end 
               if
    end 
               if
  end 
               for
  nyíltak ← nyíltak \ {csomópont}
  zártak ← zártak ∪ {csomópont}
end 
               procedure

            

               procedure A-algoritmus(A, kezdő, C, O, költség, h)
  Állapot[új-csomópont] ← kezdő
  Szülő[új-csomópont] ← Nil
  Operátor[új-csomópont] ← ∗
  Útköltség[új-csomópont] ← 0
  Heurisztika[új-csomópont] ← h(kezdő)
  nyíltak ← {új-csomópont}
  zártak ← ∅
  while Igaz do
    if nyíltak = ∅ then
      break
    end 
               if
    csomópont ←Választ({cs | cs ∈ nyíltak ∧ ∀cs′(cs′ ∈ nyíltak ⊃ (Útköltség[cs]+Heurisztika[cs]) ≤ (Útköltség[cs′]+Heurisztika[cs′]))})
    if Állapot[csomópont] ∈ C then
      break
    end 
               if
    Kiterjeszt(A, kezdő, C, O, költség, h, csomópont, nyíltak, zártak)
  end 
               while
  if 
               not nyíltak = ∅ then
    Megoldás-Kiír(csomópont )
  else
    print „Nincs megoldás”
  end 
               if

               end 
               procedure

            

2.2.8.1. Az A algoritmus értékelése

  • Teljesség: A vezérlő,

    • ha van megoldás, tetszőleges reprezentációs gráfban véges sok keresőlépés után előállít egy megoldást,

    • ha nincs a problémának az adott reprezentációban megoldása, akkor (véges gráf esetén) azt a nyílt csomópontok elfogyásával felismeri.

  • Optimalitás: Nincs garancia az optimális megoldás előállítására. De ha minden esetén

    Equation 2.. 


    ahol az állapotból célba jutás optimális költsége, akkor az A algoritmus az optimális megoldást állítja elő, ha van megoldás. Ez az algoritmus.

Lemma:

Az algoritmus a működése során egy csomópontot legföljebb véges sokszor terjeszt ki.

Bizonyítás:

Egy csomópontot csak akkor terjeszthetünk ki, ha nyílt. A nyílt csomópontok közé legfeljebb annyiszor kerülhet, ahányszor egy minden addiginál olcsóbb utat találunk hozzá. Belátjuk, hogy véges sok ilyen út van. Jelölje az élek költségének pozitív alsó korlátját, vagyis minden esetén

Equation 2.. 


Tegyük föl, hogy a csúcsba először egy költségű úton jutunk el. Ez az út legfeljebb hosszú lehet. Az ennél olcsóbb -be vezető utak -nál biztosan rövidebbek. A korlátnál rövidebb -be vezető utak száma viszont véges.

Lemma:

Az algoritmus, hacsak közben nem fejezi be sikeresen a keresést, minden a nyíltak halmazba bekerülő csomópontot véges sok lépés után kiterjeszt.

Bizonyítás:

Legyen . Megmutatjuk, hogy kiválasztása előtt kiterjesztendő (nála kisebb összköltséggel rendelkező) csomópontok száma véges, és egy ilyen csak véges sokszor kerülhet vissza a nyílt csomópontok közé.

  • Először belátjuk, hogy egy csomópont összköltsége arányos a csomópont mélységével. Amikor egy csomópont bekerül a halmazba, akkor

    Equation 2.. 


    ahol az -ből -be vezető optimális költségű út hossza.

  • Most egy mélységi korlátot adunk meg. Legyen

    Equation 2.. 


  • Ennél a korlátnál mélyebben fekvő csomópontokra az összköltség nagyobb, mint . Ugyanis ha egy csomópontra , akkor

    Equation 2.. 


    Tehát , azaz az -nél nem nagyobb összköltséggel rendelkező csomópontok a mélységi korlátnál magasabban helyezkednek el.

  • Mivel az egyes csomópontokból kiinduló élek száma fölülről korlátos, így egy adott mélységi korlátnál magasabban fekvő csomópontok száma véges.

Tétel:

Az algoritmus véges reprezentációs gráfban véges sok lépés után befejezi a keresést.

Bizonyítás:

A korábbi lemma értelmében az algoritmus a véges sok lehetséges csomópont mindegyikét legfeljebb véges sokszor terjesztheti ki. Ez azt jelenti, hogy véges sok lépésen belül az összes csomópontot végleg ki is terjeszti, ha előbb nem áll le sikeresen a keresés. Az algoritmus tehát

  • vagy talál célállapotot tartalmazó csomópontot,

  • vagy pedig elfogynak a nyílt csomópontok,

és befejeződik a keresés.

Lemma:

Ha van megoldás, az algoritmus adatbázisában a nyílt csomópontok között mindig van az optimális úton fekvő csúcs.

Bizonyítás:

Legyen optimális út.

  • 1. kiválasztás előtt: .

  • k. kiválasztás előtt: indukciós feltevésünk szerint . Legyen a legkisebb ilyen index.

  • k+1. kiválasztás előtt:

    • Ha nem -t terjesztjük ki, akkor nyílt marad.

    • Ha -t terjesztjük ki, akkor akár először állítottuk elő, akár már szerepelt a keresőfában: nyílt lesz.

Tétel:

Tetszőleges reprezentációs gráf esetén, ha van megoldás, az algoritmus véges sok lépésben megoldással fejezi be a keresést.

Lemma:

Az algoritmus által kiterjesztésre kiválasztott tetszőleges csomópontra

Equation 2.. 


Bizonyítás:

Ha a gráfban nincs megoldás, , egyébként az optimális megoldás költsége. A korábbi lemma szerint van kiterjesztése előtt a nyíltak között az optimális úton fekvő csomópont. Legyen az első ilyen. Ekkor . Az algoritmus az csúcsot választotta kiterjesztésre, tehát . De

Equation 2.. 


amiből következik.

A lemmát a következőképpen is megfogalmazhatjuk: Annak szükséges feltétele, hogy az algoritmus egy csomópontot kiterjesztésre kiválasszon:

Equation 2.. 


Tehát az

Equation 2.. 


csomópontok nem kerülnek soha kiterjesztésre, nem is kell őket a keresőfában őrizni. Nem ismerjük ugyanakkor az értéket. Becsüljük meg: legyen . Ekkor az

Equation 2.. 


csomópontokat a keresőfából elhagyhatjuk. Annak elegendő feltétele, hogy az algoritmus egy csomópontot kiterjesztésre kiválasszon:

Equation 2.. 


Definíció:

Legyen és két algoritmus. Azt mondjuk, hogy jobban informált, mint , ha célállapotot tartalmazó csomópontok kivételével bármely csomópontra

Equation 2.. 


teljesül, ahol és a és algoritmusok heurisztikus függvényei. (Más szóval: a algoritmus alulról pontosabban becsli a hátralévő út költségét bármely csúcsban.)

Tétel:

Ha jobban informált algoritmus -nál, akkor minden olyan csomópontot, amelyet kiterjeszt, kiterjeszt is.

Bizonyítás:

Legyen egy olyan nyílt csomópont, melyet éppen kiválaszt kiterjesztésre! Ekkor

Equation 2.. 


A keresőgráfjában az -ből -be vezető út tetszőleges csúcsára szintén teljesül az

Equation 2.. 


összefüggés. Mit csinál ezzel az csúccsal a algoritmus? Mivel

Equation 2.. 


azaz , ezért -t a algoritmus is kiterjeszti. Az tetszőleges volt, így a algoritmus az -ből -be vezető út minden csúcsát kiterjeszti, beleértve -et is.

2.2.9. A monoton algoritmus

Definíció:

Azt mondjuk, hogy egy heurisztikus függvény kielégíti a monoton megszorítás feltételét, ha értéke bármely él mentén legföljebb az illető él költségével csökken, azaz minden él esetén

Equation 2.. 


Tétel:

Ha egy heurisztikus függvény kielégíti a monoton megszorítás feltételét, akkor

Equation 2.. 


teljesül minden -re.

Bizonyítás:

A bizonyítás két részből áll:

  1. Ha az csúcsból nem vezet út terminálisba, akkor .

  2. Ha van ilyen út, akkor legyen optimális út. Ennek éleire

    Equation 2.. 


    teljesül. Az egyenlőtlenségeket összeadva

    Equation 2.. 


    adódik, ahol a bal oldal , mivel , lévén terminális csúcs. Így .

Definíció:

Monoton algoritmusnak nevezzük azt az algoritmust, amelynek heurisztikus függvénye monoton megszorításos.

Tétel:

Amikor a monoton algoritmus egy nyílt csomópontot kiterjesztésre kiválaszt, akkor -be már optimális utat talált, azaz .

Bizonyítás:

Tegyük föl indirekt módon, hogy amikor az csúcsot kiterjesztésre kiválasztja az algoritmus, . Legyen egy olyan nyílt csúcs, amely egy -ből -be vezető optimális úton van és amelyre teljesül. Az indirekt föltevés miatt és nem lehet ugyanaz a csúcs. Mivel azonban az algoritmus -et választotta helyett, ez azt jelenti, hogy . Ugyanakkor az -ből -be vezető optimális útvonalra felírható a következő összefüggés:

Equation 2.. 


A levezetésből azt kaptuk, hogy , ami ellentmond annak, hogy az csomópontot választjuk ki.