Előadó: Dr. Várterész Magdolna
2.2. Állapottér-reprezentált problémák megoldását kereső módszerek
Komponensek:
| -adatbázis | ||
| Az állapottérgráf tárban tárolt része. Megoldáskeresésnél nem lesz az egész gráf a tárban, csupán valamilyen, a keresés szempontjából fontos része. | ||
| -műveletek | ||
| Segítségükkel módosítjuk az adatbázist. Ilyen műveletek például: | ||
| a) állapottér-reprezentációs operátorokból származtatott műveletek | ||
|
b) technikai műveletek (pl. visszalépés) |
||
| -vezérlő | ||
|
A vezérlő irányítja a keresést. Megmondja, hogy a megoldáskeresés során az adatbázis mely részén mikor, melyik művelet hajtódjon végre. Operátorból származtatott művelet választása előtt vizsgálja az operátor-alkalmazási előfeltételeket. Figyeli a terminálási feltételek segítségével, hogy befejeződhet-e a keresés (sikeresen, avagy sikertelenül). Ha a terminálási feltételek nem teljesülnek, akkor tovább kell keresni. |
||
| Ha ezek nem teljesülnek: még nem találtuk meg a megoldást. Ő fogja figyelni is. | ||
Osztályozásuk:
| I. nem-módosítható megoldáskeresők: |
egy állapotváltozást vissza lehet-e vonni, |
| vagy sem. Ha utólag nem tudjuk magunkat
módosítani: nem-módosítható megoldáskeresés (ez a hagyományos programozásra jellemző). Mesterséges intelligenciában inkább módosítható megoldáskeresőket alkalmaznak. |
|
| II. módosítható megoldáskeresők: | a vezérlő által kiválasztott művelet hatása |
| visszavonható | |
|
a) visszalépéses (backtracking) |
|
|
b) keresőgráffal |
|
| III. irányítatlan (szisztematikus): | a vezérlő mi alapján választ: |
|
- véletlenszerűen |
|
|
- valamilyen általános szisztéma alapján
|
|
| IV. heurisztikus: | Heurisztikus keresésnél a generálás irányításánál |
|
helyet hagyunk a tárgyköri ismereteknek is, azokat is felhasználjuk. |
|
Keresés iránya:
| 1. előrehaladó(adatvezérelt): | kezdőállapotból célállapotba |
| 2. visszafelé haladó (célvezérelt): | visszafelé haladva rekonstruálunk |
| 3. kevert: | mindkét irányból elindul, s valahol találkozik |
Linkek:
