Előadó: Dr. Várterész Magdolna

---

2.2.1. Nem módosítható megoldáskeresők

Ezen megoldáskeresőknek kisebb a jelentőségük, ritkábban is használják őket. Előnyük viszont az, hogy egyszerűbbek. Csak olyan feladat megoldásánál alkalmazzuk, ahol nem a megoldás a lényeg (azaz a kezdőállapotból a célállapotba vezető operátorsorozat), hanem csupán az, hogy eldöntsük: a feladatnak egyáltalán létezik-e megoldása, vagy egy célfeltételnek eleget tevő állapot előállítása.

Komponensek:

	adatbázis:	aktuális állapot
	műveletek:	állapottér-reprezentációs operátorok
		Az adatbázisra egy művelet alkalmazható: ha az aktuális állapotban teljesülnek a műveletet meghatározó operátor alkalmazási előfeltételei. A művelet hatása az adatbázisra: az aktuális állapotban alkalmazzuk a műveletet meghatározó operátort, és az előállt új állapot lesz az új aktuális állapot.
	vezérlő:	1.	aktuális állapot ¬ kezdőállapot
			(inicializáljuk az adatbázist. Az aktuális állapot legyen először a kezdőállapot)
			Célállapotot kell előállítani, nem egy operátorsorozatot (hiszen ez már plusz információ lenne).
		2.	tesztelés. Az aktuális állapot egyenlő célállapot-e?
			Ha igen:	sikeresen befejezhetjük a keresést,
				előállítottunk egy célállapotot
			Ha nem:	erre az aktuális állapotra van-e alkalmazható művelet?
				a) ha van:	a vezérlő választ egyet, és alkalmazza.
					Vissza a 2. pontra (tesztelés).
				b) ha nincs:	be kell fejezni a munkát, sikertelen a keresés.
					Lehet, hogy nincs megoldás, vagy a megoldáskereső rossz irányba ment; de erről nem tudunk többet mondani!

 

A szükséges eljárások:

procedure alk (var all: alltip; o: op);	művelet alkalmazása
	az adatbázison
procedure valaszt (all: alltip; var o: op; var v: boolean);	művelet választása
procedure sikertelen;	felhasználó tájékoztatása
	a keresés sikertelen befejezéséről
procedure sikeres (a: alltip);	megoldás visszaadása

 

 

 

 

 

Ezek alapján a vezérlő:

begin
	aktall := k; van := true;
	while van and (not celfelt(aktall)) do
	begin
		valaszt(aktall, operator, van);
		if van then alk(aktall,operator);
	end;
	if van then sikeres(aktall) else sikertelen;
end.

 

 

 

 

 

 

Ugyanazon feladat esetén a választás módjában lehet lényeges eltérés:

a) irányítatlanul, szisztematikusan ("próba-hiba" módszer)

Pld.: sorrend, s ezeket végignézzük, hogy melyiket tudjuk alkalmazni. A feladattal kapcsolatos tudásunk nincs benne megfogalmazva. Véletlenszerűen választunk: ez a próba-hiba módszer.

Ezt könnyű implementálni, kicsi az adatbázis, viszont általános esetben nem garantál semmit.
Milyen feladatosztály esetén van reményünk a megoldásra? Csak olyan esetben, ha minden csúcsból elérhető valamelyik cél. Kört nem tartalmazhat, ui. nincs rá garancia (végtelenszer ismételheti). Hurok még lehet benne.

b) heurisztikusan ("hegymászó" módszer)

Akkor beszélünk heurisztikus megoldáskeresésről, ha megpróbáljuk felhasználni a tudásunkat, tapasztalatunkat. A heurisztika valamilyen mennyiségi, minőségi heurisztika lesz.

A heurisztikától függ majd, hogy a megoldást megtaláljuk-e vagy sem. Jó heurisztika esetén lesz majd reményünk a megoldás megtalálására.

h(n)	a csúcs hány élnyire van a legközelebbi terminálishoz
	(azaz hány operátor alkalmazására van szükség). Ha ezt tudnánk,
	akkor ez egy felhasználható tudás lenne. Ezt próbáljuk meg becsülni.
h(aktall)	h(o1(aktall))	alkalmazzuk az összes lehetséges operátort,
	h(o2(aktall))	s utána megnézzük, hogy közelebb kerültünk-e
	...	valamilyen célhoz (vagy legalábbis nem távolabb).
	h(on(aktall))	Azt fogjuk alkalmazni, amelyik a legközelebbi
		célhoz visz közelebb.

 

Ez az ún. hegymászó-módszer. "A csúcshoz közelítünk." Távolodni nem szabad a céltól.

---

Vissza a lap tetejére