Probléma

Probléma: (Bakos Idegen Szavak Szótára szerint):

megoldásra váró elméleti vagy gyakorlati kérdés; tudományos kérdés, kutatási feladat;
rejtvény, talány, titok;
felvetett dolog vagy terv.

Rejtvény és titok

Nehéz, fenyegető helyzet

A probléma fogalmának tudományos elemzése

A különböző szaktudományok, mint a kognitív tudomány, (meta)matematika és számítógéptudomány, a filozófia, a „probléma” fogalmának filozófiai és szaktudományos elemzésére vállalkoznak és kísérletet tesznek a fogalom minél pontosabb és egyúttal minél hasznosabb definiálására.

Értelmezés a rendszerelmélet keretei közt

Az algoritmusok elsődleges alkalmazása az, hogy problémákat oldunk meg velük. Gyakran kerülünk a köznapi életben is olyan helyzetbe, amikor valaminek bizonyos okokból úgy kellene lennie, ahogy éppen nincsen. Például vendégek jönnek vacsorára, és el kell készíteni a fogásokat; egy hidat kellene felhúzni egy folyón át, minimális kockázattal kell kikerülni egy atomháborúval fenyegető politikai helyzetből stb. Az ilyen szituációkat nevezzük problémáknak.

Hasznos, ha ez utóbbi fogalom és ezáltal az algoritmus fogalmának rendszerelméleti értelmezését adjuk.

A rendszer és az állapot fogalmát alapfogalomként fogjuk használni. Általában rendszer a valóság bármely olyan, általunk többé-kevésbé egyértelműen elhatárolt darabja, amely diszkrét vagy folytonosnak képzelt módon adott időpillanatban adott állapotban van.

Pontosabban: feltesszük, hogy a rendszer állapota leírható egy $f\left(t\right):\left(t\right)\rightarrow \mathbb {R} ^{n}$ állapotfüggvénynyel ( $n\in \mathbb {N}$ ), ekkor a t időpillanatban mért $f\left(t\right)$ függvényértéket a rendszer állapotának nevezzük. A rendszer diszkrét ha a függvényértéket állandó időközönként mérjük, azaz matematikailag kifejezve ha $t\in \mathbb {N}$ ; ha a függvényértékeket nagyon sűrűn mérjük (legalábbis képzeletben), az állapotfüggvény grafikonja folytonosan megrajzolt (gondoljunk egy EKG-ra), akkor a rendszert folytonosnak nevezzük. Az állapotfüggvény $D\left(f\right)$ értelmezési tartományát állapottérnek nevezzük.

Ha adott egy g(t):D(f)→Rⁿ célfüggvény, és célunk az, hogy adott időpillanattól kezdve a g értéke megegyezzen a t értékével, akkor beszélhetünk arról, hogy a rendszerben egy probléma áll fönnt. A továbbiakban csak olyan befolyásolható rendszerekkel fogunk foglalkozni, melyek állapotfüggvényének értékeit bármely időpillanatokban módosítani tudjuk.

Problémareprezentációs lehetőségek

Általában egy problémának többféle modelljét, reprezentációját adhatjuk. Ez a következő módokon is elképzelhető (s esetleg más módokon…):

#Állapottér-reprezentációval, diszkrét rendszer esetén ez általában helyettesíthető egy:
#Gráfreprezentációval);
#Dekompozíciós reprezentációval;
#Játékreprezentációval;
logikai vagy általánosabban formális nyelvi reprezentációval;
strukturált objektum-reprezentációval.
a megoldó algoritmusok megfogalmazása absztrakt automaták keretében (vezérlőfüggvényként) is lehetséges;

Ennek megfelelően az algoritmussal megoldható problémák megoldására szerkesztett algoritmusok is többféleképp osztályozhatóak:

A) Elsődleges stratégiák: A probléma reprezentációjától függetlenek, mindegyikben érvényesen megfogalmazhatóak;
B) Másodlagos stratégiák: Függhetnek a probléma reprezentációjától, de nem a realizációjától, vagyis a modellben előforduló (esetleg a stratégia által is generált) konkrét értékektől;
C) Heurisztikák: A konkrét értékektől is függhetnek.

Esetleg úgy gondolhatnánk, hogy a heurisztika a legalacsonyabbrendű stratégia, ha egy problémával találkozunk, akkor először is elsődleges, azután ezt konkretizálva a másodlagos, végül heurisztikus stratégiát kell megfogalmaznunk. Ez azonban egyrészt nem is mindig lehetséges: sok problémára ismert heurisztika, de elsődleges stratégia nem; másrészt ha van valamilyen heurisztikánk, akkor az éppenséggel hatással lehet az elsődleges stratégia megválasztására is. Vagyis, ahogyan azt a problémamegoldások elméletének tanulmányozása során észben kell tartanunk, a helyzet sokszor bonyolultabb, mint azt előre gondolnánk.

Állapottér-reprezentáció

A probléma állapottér-reprezentációjának a következő főbb elemei vannak:

az állapottér: ez a rendszert leíró jellemzők, tulajdonságok ( A₁, A₂, …, A_n halmazok, $n\in \mathbb {N}$ ) értékeinek (a halmazok elemeinek) $T\subseteq A_{1}\times A_{2}\times ...\times A_{n},n\in \mathbb {N}$ direkt szorzata;
- T egy elemét állapotnak nevezzük;
műveletek: egy elemi állapotváltoztatás az állapottérben; ezeknek van
- előfeltétele (nem minden állapotban alkalmazhatóak);
- hatása (a rendszer átváltása egy más állapotra)
a rendszer kezdő állapota (vagy a problémamegoldás előfeltétele);
a rendszer célállapota (vagy a megoldás utófeltétele);
a probléma megoldása (műveletek sorozata).

Gráfreprezentáció

Az diszkrét rendszerek állapottér-reprezentációja nyomán (s talán más esetekben is, de ilyennel ritkán találkozni) mindig elkészíthetjük a probléma gráfreprezentációját.
A gráf tudvalevőleg elemek, a csúcsok egy V halmazának (vertex(angol)=csúcs), és az élek $E\subseteq V\times V$ halmazának G=(V,E) párosa (az E jelölés az angol edge=él szóból jön).

Mármost tekintsük az R rendszer lehetséges állapotainak V halmazát, ebből úgy készíthetünk gráfot, neve állapotgráf, hogy ha a V egy állapotából egy másikba elemi rendszerművelettel (állapotváltozással) lehetséges átlépni, akkor a két állapot párosát nevezzük ki élnek, és ezt az összes állapotpárosra végezzük el. Ha műveleteink invertálhatóak, akkor irányítatlan gráfreprezentációt is készíthetünk, de ezzel nem fogunk foglalkozni: általánosabb elképzelés az, ha a rendszer állapotgráfja irányított.

A probléma megoldása, ha a kiinduló állapotból az állapotgráf csúcsain lépegetve (minden lépés egy-egy műveletnek, elemi állapotváltoztatásnak felel meg) eljutunk egy célállapotig. Ennek megfelelően a megoldás kifejezést kétféle értelemben használjuk:

a célállapot;
az az út (pontosabban séta), mely a kezdőállapotból a célállapotba visz.

A gráfreprezentáció alapú problémamegoldó eljárások eme alapvető tényezőit a mesterséges intelligencia tudományában a gráf-keresőrendszer fogalmában foglalták össze, ami az algoritmus fogalmának egy speciális keretben történő értelmezése; bővebben lásd ott.

Dekompozíció

Egy probléma dekompozíciós reprezentációja valójában egyszerű fogalmat takar, előkelő elnevezésben; egyszerűen annyit jelent, hogy több részre bontjuk a problémát.

A redukció olyan problémamegoldási eljárás, melynek során a problémát, annak megoldástervét felbontjuk egy már megoldott problémára, illetve megoldástervére; továbbá arra a maradék problémára, amelynek megoldása a megoldottnak tekintett résszel együtt szükséges és elegendő az eredeti probléma megoldásához. Azaz a redukció „képlete”:

eredeti Probléma=Megoldható problémarész + Nehezen megoldható problémarész. azaz P=M+N.(

A dekompozíció azt jelenti, hogy nem két, hanem több részre bontjuk a problémát, azaz a problémát egy esetleg összetettebb, de strukturáltabb problémával reprezentáljuk.

Valamilyen M problémarészt általában a legtöbb probléma esetén találhatunk, sőt a Pólya-heurisztika szerint általában ez az első feladatunk. A gondot általában az okozza, hogy az N problémarészt általában még mindig túl nehéz megoldani, és olyan dekompozíciót több okból is nehéz találni, amely megfelelően osztaná fel a problémát. Ha könnyű a dekompozíció, az valószínűleg azt jelenti, hogy M kis súllyal vesz részt az eredeti P probléma felépülésében, és a probléma nehézségének nagy részét még mindig az N ismeretlen megoldású problémarész teszi ki. Azaz a dekompozíció maga is egy nehéz probléma, amire nem lehet általános receptet adni. Ha azonban véletlenül észrevesszük a dekompozíció lehetőségét, az nagyon gyümölcsöző eredménnyel szokott járni.

Játékreprezentáció

Általában a teljes információs kétszemélyes játék modelljét használjuk egy probléma játékreprezentációja során. Főleg olyankor lehet hasznos ez a reprezentációféleség, ha a rendszer, amelyben a problémát meg kell oldani, válaszol beavatkozásainkra valamilyen módon, és a lépések megtervezése során erre is tekintettel kell lennünk. Ez esetben a probléma megoldását nem algoritmusnak, hanem stratégiának szokás nevezni. Egy beavatkozásokra válaszoló rendszerben a probléma megoldása a rendszer (szokásosabb nevén „természet” elleni kétszemélyes játék egy kimenetele formájában írható le, tehát a megoldó algoritmus egy megoldó stratégiával írható le.

Egyébként a problémamegoldás játékkal való modellezése, azaz a játékelmélet mesterségesintelligencia-kutatásban (MI) való alkalmazása mellett a fordított irányú leírásnak is szerepe van, azaz amikor egy, a gyakorlatban fontos játéktípust az MI eszközeivel modellezünk (például gráfreprezentáción belül állapotgráffal), azaz a MI eredményei alkalmazhatóak a játékelméletben, és fordítva.

Maradjunk még az előző, levélfeladásos problémánál. Először is a feladat rögtön kétféleképp értelmezhető. Az-e a feladat, hogy egy konkrét postán (mondjuk a Rákóczi úton) adjunk fel egy konkrét levelet (mondjuk a nagymamának lett megírva), vagy pedig az a feladat, hogy életünk tetszőleges olyan helyzetében, amikor is levelet kell feladnunk, legyünk képesek azt egy postán (valamelyiken) feladni. A második értelmezés magában foglalja persze az elsőt: a második probléma egy általános probléma, problémaosztály, míg az első ennek egy speciális, konkretizált esete.

Az informatikában is jelen van ez a különbség: amikor egy programozó kap egy feladatot, általában egy problémaosztályt kell megoldania: mondjuk egy CDA fájlformátumból WAV formátumba alakító programot készítenie. Ezt a programot nem egy konkrét CDA fájl átkonvertálására tervezi, hanem az összes szóba jövő ilyen fájl konvertálására, bár természetesen amikor a program majd lefut, akkor egy konkrét CDA fájlt ír át WAV-ra.

Az egy konkrét probléma, hogy írjuk át kedvenc CD-számunkat WAV hanghullám formátumúra, míg egy problémaosztály, hogy általában hogy kell CDA-ból WAV-ba konvertálni. A matematikában általában nem az érdekes, hogy például a 2 és 3 számnak számoljuk ki a legnagyobb közös osztóját, hanem hogy két számnak általában hogy számolhatjuk ki. Így algoritmusnak mindig a problémaosztályok megoldására alkotott, általános eljárásokat, a terveket nevezzük, míg a konkrét esetekben ezek megvalósítása az algoritmus alkalmazása vagy végrehajtása.

Kapcsolódó szócikkek

Források

Bakos Ferenc: Idegen Szavak Szótára. Munkatársak: Fábián Pál, Zigány Judit. Hatodik (átnézett, függelékkel kiegészített) kiadás. Akadémiai Kiadó, Bp., 1983. ISBN 963-05-3178-X .
Gregorics Tibor Mesterséges Intelligencia c. könyve^{[pontosabban?]}