4. Tétel: Függvények leírása, ábrázolása; Megoldás kereső algoritmusok

Függvények, görbék, felületek leírása és számítógépes ábrázolása.

Függvények leírása és számítógépes ábrázolása

info

Függvény segítségével jeleníthető meg egy ábra: minden x-hez tartozik egy y érték. A grafikon elméleti, ezt csak közelíthetjük, mivel a gyakorlatban behelyettesítünk, és az adott értékeket ábrázoljuk, majd ezeket összekötjük. A gyakorlati függvény tehát szakaszokból áll. A behelyettesített értékek számától, sűrűségétől függ, hogy hány ponton lesz törött a vonal. Számítógép annyi értéket helyettesít, hogy legalább 1 px-t ugorjon (ami függ a képernyő felbontásától is), így görbének látszik, viszont mindig töröttvonal marad.

Polinomiális függvények

$an×xn+an-1×xn-1+...+a1×x1+a0×x0$ Polinom: x polinomját valamilyen hatványon megszorozzuk (n:fokszám, a:együtthatók, x:változó), konstans függvény: 0-adfokú polinom. f(x)=ax+b 1.fokú polinom, ahol a:meredekség, b:hol metszi f(x)-et (vagy y tengelyt) (mivel a értéke nem tud elég nagy lenni, ezért függőlegest nem tudunk ábrázolni. Elképzeléshez kitalálni függvényt:

• ha 2 pont van megadva, éppen egyértelmű
• 1 ponttal aluldeterminált
• több, mint 2 pont esetén ha 1 egyenesre esnek, könnyű helyzet, ha nem, akkor egyik ponton sem megy át, hanem minden pontot közelít a legkisebb eltéréssel.

$f(x)=ax2+bx+c$ 2.fokú polinom

Elképzeléshez függvényt találni:

• próbálkozás különböző a, b és c értékekkel
• kideríteni hol a csúcspont
• megadott minimum 3 ponttal egyenletrendszer megoldása

Hullám ábrázolása esetén is célszerűbb polinomiális függvény használata szögfüggvény helyett, mert az x-hez tartozó f(x) értékek keresése szögfüggvény esetén időigényes, lassú, és apró változtatástól is összeomlik.

$f(x)=ax3+bx2+cx+d$ 3.fokú polinom

Megtalálása próbálkozással vagy minimum 4 pont megadásával (4 ismeretlen miatt). Ábrázolható 2 parabolával is, de úgy törés lesz a csatlakozási ponton.

Implicit függvények

Ha nincs egyértelmű hozzárendelés, tehát x-hez több y érték tartozik, pl egy kör, vagy egy függőleges esetén

• Eddig: $x→f(x)$ , ahol $R→R$
• Implicit esetben: $x,y → F(x,y)$, ahol $R×R→R$
  • $F(x,y) = 0$

Minden eddigi függvény átalakítható ilyenné:

• explicit: $y= 3x2+5x+1 \space\space\space\space\space\space\space\space\space\space\space y=f(x)$
• implicit: $0=3x2+5x+1-y \space\space\space\space 0=f(x)-y$
• tehát pl:
  • $x2+y2=9$
  • $x2+y2-9=0$
  • $F(x,y)=0$

Vektor alapján ábrázolok függvényt

Ezek a paraméteres vektorfüggvények, vagy paraméterekkel megadott vektor görbék. Mozgó helyvektor végpontjai rajzolják a görbét, tehát idő függvényében vektort írunk le.

Értelmezési tartomány: idő.

$r(t): [a,b]→V2$ , ahol V2 a szabad vektorok halmaza, a t paraméter valós érték, [a,b] intervallum az ábrázolás idejének kezdő és végpontja közötti intervallum, a függvény értéke pedig a vektor.

2 függvényként is lehet kezelni:

• Van $(x,y)$ koordinátám
• $x(t)$ és $y(t)$ is függvénye a t-nek
• $x(t): [a,b]→ R$, $y(t): [a,b]→ R$

A vektorfüggvény tehát koordináta függvények együttese. Minden t (azaz [a,b] intervallumon értelmezett idő) értékre x és y koordinátákat ad.

Ez a módszer egyesíti az eddigiek előnyeit:

• könnyű kirajzolás (pl $y=f(x)$ esetén)
• a görbe maga alá is görbülhet, bármilyen alakú lehet ( $F(x,y)=0$ esetén)

Görbék leírása és számítógépes ábrázolása

Implicit típusú görbék

Behelyettesítés esetén bonyolult egyenletet kapunk (Pl $4x5-5x3y7+sin(x)+cos(y2)-7=0$)

Ábrázolás módja: (0,0) behelyettesítése, pontonkénti (pixelenkénti) kiértékelés: ha az eredmény rajta van a vonalon, akkor 0-val egyenlő, egyébként nincs rajta.

Minden pixelt be kell helyettesíteni. Lassú kiértékelés, és nem egyértelmű, akár a szoftver is elbizonytalanodhat, ezért ritkán használjuk computer grafikában.

Tulajdonságai:

• az $(x0,y0)$ koordinátájú pont akkor és csakis akkor illeszkedik a görbére, ha $F(x0,y0)=0$
• ha $F(x0,y0)>0$, akkor az görbe fölött helyezkedik el (fel és jobbra)
• ha $F(x0,y0)<0$, akkor az görbe alatt helyezkedik el (le és balra)

Értékek behelyettesítése a távolságot is mutatja (minél nagyobb az érték, annál távolabb van a pont)

Polinommal megadott görbe

elsőfokú polinom:

• $3x-4y-7 = 0$, egyenes → elsőrendű görbe

másodfokú polinom:

• $x2+y2-9=0$, kör→ másodrendű görbe
• $x2-y=0$, parabola → másodrendű görbe

n-edfokú polinom:

• $xn-3yn+...=0$ → n-edrendű görbe

Csak polinommal megadott lehet valahanyadrendű görbe vagy algebrai görbe (mivel a függvény is algebrai, nem analitikus. Pl. $sin(x)$ analitikus lenne)

Egy n-edrendű és egy m-edrendű görbének legfeljebb $n×m$ darab látható metszéspontja lehet (ezen mindkét görbe átmegy)

Vektorral megadott görbe

Mozgó helyvektor végpontjai rajzolják a görbét, tehát idő függvényében vektort írunk le. (Továbbiak: Függvények, 3.pont) Ezek a legáltalánosabban használt görberajzoló függvények.

Térbeli görbe rajzolására alkalmatlanok az implicit és az explicit függvények.

Csak vektorfüggvénnyel rajzolhatóak.

$r(t): [a,b]→V3$, ahol $V3$ a térbeli vektorok halmaza

$x(t): [a,b]→ R$, $y(t): [a,b]→ R$, $z(t): [a,b]→ R$

Felületek leírása és számítógépes ábrázolása

Explicit

• előállítás $z=f(x,y)$
• minden $(x,y)$ pontra ad egy z értéket. $R×R→R $
• $x,y$ síkon megkeresem a pontot, majd $z$ irányába tolom.
  1. összes x-et behelyettesítem, y=0
  2. összes y-t behelyettesítem, x=0
  3. a többi pontot is behelyettesítem, kiszámolom

Dróthálós megjelenítés:

• Minden pontot ábrázolni kell, mert a köztes pontokat nem határozzák meg a szélsők.
• Így a felületi görbéket ábrázolom, nem magát a felületet

Előny: könnyű ábrázolás

Hátrány: maga alá görbülő felületet nem tud ábrázolni

Implicit

• $F(x,y,z) = 0$
• Egy $(x,y)$ értékhez több $z$ érték társul, tehát egymás alá görbül a felület.
• A pont 3 koordinátája egy nagy egyenletben egyesül. Azok a pontok vannak a felületen, ahol kiértékelés során 0-t kapunk.

Előnye: maga alá görbülő felületet is tud ábrázolni

Hátránya: pontonkénti kiértékelés

Ha adott az $F(x,y,z)$ n-edfokú polinom, akkor az $F(x,y,z)=0$ egyenletet kielégítő pontok összességét n-edrendű (vagy algebrai) felületnek nevezzük.

• Pl:
  • $n=1: ax+by+cz+d=0$ egy sík
  • $n=2: ax2+by2+cz2+dxy+exz+fyz+gx+hy+jz+k = 0$, ahol dxy,exz és fyz is másodfokú tagok, teház ha nincs x2,y2,z2, akkor is másodfokú.

Metszéspontok: felület+görbe, felület+felület.

Egy n-edrendű felületnek és egy m-edrendű görbének $n×m$ látható metszéspontja lehet. Tehát egy felület egyenletének fokszámát eldönthetem úgy, hogy egyenessel metszem, és a metszéspontok száma megadja a felület egyenletének fokszámát. Egy n-edrendű és egy m-edrendű felület metszésvonala egy $m×n$-edrendű görbe.

Paraméteres megadás

• $r: [a,b]×[c,d]$ (a két időintervallum Descartes szorzata)→V3
• $x: [a,b]×[c,d] →R$, $y: [a,b]×[c,d] →R$, $z: [a,b]×[c,d] →R$
• Míg a görbék ábrázolása során pontokat kötök össze, itt paraméter vonalakkal rácsozom be
• Lépései ([a,b] intervallumot az u tengelyen, [c,d] intervallumot a v tengelyen ábrázolva):
  1. u értéke fix, a v értéke pedig c-ről d-re egységenként nő. (1. paraméter állandó, 2. változó) Eredményei pontok, amelyeket összekötve görbét kapok
  2. új, de szintén fix u érték, míg a-ból b-be nem érünk (az intervallumokon minél kisebb a lépték, annál simább a felület, annál pontosabb a végeredmény)
  3. az első 2 lépést a v értékein is megismételni

Előnyök, hátrányok (implicit vs paraméteres):

	IMPLICIT	PARAMÉTERES
MEGJELENÍTÉS	-	+
KOORDINÁTA	+, behelyettesítés után	-, 3 egyenletből álló
ILLESZKEDÉSE	0 eredmény rajta van	2 ismeretlenes
A FELÜLETRE	nem 0, nincs	egyenletrendszer

Előfordul, hogy az egyik implicit, a másik paraméteres formában jó.

Felület érzékeltetése: rácsvonalakkal, színezéssel, szintvonalakkal

---

Problémák reprezentálása állapottéren.

A mesterséges intelligencia problémáinak megoldása a probléma meg-fogalmazásával kezdődik: a problémát leírjuk, reprezentáljuk. Az egyik legelterjedtebb reprezentációs technika az állapottér-reprezentáció(state space representation).

Állapottér reprezentáció:

• A mesterséges intelligencia problémáinak megoldása a probléma megfogalmazásával kezdődik.
• A problémát leírjuk, reprezentáljuk.
• Az egyik legelterjedtebb reprezentációs technika az állapottér- reprezentáció.
• Legyen adott egy probléma, amit jelöljünk p-vel.
• Megkeressük p világának legalább egy, de véges sok – a probléma megoldása során fontosnak vélt – meghatározóját.
• (pl. objektum, pozíció, méret, hőmérséklet, szín, stb)
• Tegyük fel, hogy m ilyen jellemzőt találtunk.
• Minden egyes jellemző p világát különböző értékekkel jellemzi.
• (pl. szín: fekete/fehér; hőmérséklet: [−20◦, 40◦], stb)

Állapot:

• Ha a megadott jellemzők épp rendre a h1, . . . , hm értékekkel rendelkeznek azt mondjuk, hogy p világa a (h1, . . . , hm) érték m-essel leírt állapotban (state) van.

Állapottér:

• A világunk állapotainak halmaza.
• A kezdeti állapot és az állapottér-átmenet függvény együttesen definiálják a probléma állapotterét, az állapotok halmazát.

Kényszerfeltétel:

• Jelölje az i-edik jellemző által felvehető értékek halmazát Hi (i = 1,..,m)
• Ekkor p állapotai elemei a H1x…xHm halmaznak.
• Azokat a feltételeket, amelyek meghatározzák, hogy ebből a halmazból mely m-esek állapotok, kényszerfeltételeknek nevezzük.
• Az állapottér tehát az értékhalmazok Descartes-szorzatárnak a kényszerfeltételekkel kijelölt részhalmaza:

Kezdőállapot:

• Az A állapottér azon állapotát, amit a probléma világa jellemzőinek kezdőértékei határoznak meg, kezdőállapotnak nevezzük és kezdő-vel jelöljük.

Célállapot:

• A kezdőállapotból kiindulva a probléma világának sorban előálló állapotait rendre meg szeretnénk változtatni, míg végül valamely számunkra megfelelő úgynevezett célállapotba jutunk.
• Jelölje C ⊆ A a célállapotok halmazát.
• Célállapotok megadása történhet:
  • Felsorolással
  • Célfeltételek megadásával

Operátorok:

• Hogy célállapotba juthassunk, meg kell tudnunk változtatni bizonyos állapotokat.
• Az állapotváltozásokat leíró leképezéseket operátoroknak nevezzük.
• Nem minden operátor alkalmazható feltétlenül minden állapotra, ezért meg szoktuk adni az operátorok értelmezési tartományát az operátoralkalmazási előfeltételek segítségével.

Állapottér-reprezentáltuk:

• Legyen p egy probléma.
• Azt mondjuk, hogy p problémát állapottér-reprezentáltuk, ha megadtuk az:
  • 〈A,kezdő,C,O〉 négyest
  • Ahol, A nem üres halmaz és a probléma állapottere
  • Kezdő eleme A halmaznak és ő a kezdőállapot
  • A célállapotok halmazát, ahol C eleme A halmaznak
  • Az opetárotok nem üres véges halmazát.
    • Jelölése: 〈A,kezdő,C,O〉.

A megoldás keresése visszalépéssel.

• Még kevesebb memóriát használ a mélységi keresőtől
• Mélységi keresés egy változata
• Összes követő helyett, egyidejűleg egy követőt generál
• Minden kifejtett csomópontra emlékszik, melyik követője jön legközelebb
• Tárigénye O(m) az O(bm) helyett.
• Követő csomópont generálása az aktuális állapot módosításával, anélkül, hogy az állapotot átmásolnánk.
• Rossz választás esetén elakadhat.
• Nem optimális, nem teljes.
• Nem optimális:
  • Ha a megoldás a jobb részfában van, előbb ő végignézi a bal részfát fölöslegesen
• Nem teljes:
  • Ha a bal oldali részfa korlátlanul mély lenne, és nem tartalmazna megoldást, a keresés soha nem állna meg.

Szisztematikus és heurisztikus gráfkereső eljárások: a szélességi, a mélységi és az A algoritmusok.

Gráfkereső:

• Akkor hasznos, mikor feltételezzük, hogy az állapottér reprezentáció köröket tartalmaz.
• Minden állapot legfeljebb egyszer szerepelhet, kerül kifejtésre.
• Csak olyan állapotokat fejtünk ki, amiket eddig nem fejtettünk.
• Előfordulhat, hogy a peremben több azonos állapot szerepel, de ez nem okoz problémát.

Szélességi kereső:

• Egyszerű keresési stratégia
• Először a gyökércsomópontot fejtjük ki.
• Következő lépésben az összes gyökércsomópontból generált csomópontot, majd azok következőit.
• Minden adott mélységű csomópontot hamarabb fejt ki, mielőtt bármelyik egy szinttel lejjebbi csomópontot kifejtene.
• Feldolgozás FIFO (first in first out)
• Az összes újonnan generált követőt a sor végére teszi, tehát a legsekélyebb csomópontokat hamarabb fej ki, mint a mélyebben fekvőket.
• A keresés teljes, ha a legsekélyebb célcsomópont valamilyen véges d mélységben fekszik, akkor a keresés eljut hozzá az összes nála sekélyebben fekvő csomópontot kifejtve.
• Optimális, ha az útköltség a csomópont mélységének nem csökkenő függvénye.
• Tárigény az idő igénnyel azonos, tárigény problémát jelent
• A gyökércsomópont, b csomópontot generál, második szint $b^{2}$ stb

Mélységi kereső:

• Mindig a fa aktuális peremében a legmélyebben fekvő csomópontot fejti ki.
• A keresés azonnal a fa legmélyebben fekvő szintjére jut el, ahol a csomópontoknak már nincsenek következőik.
• LIFO, (last is first out)
• Szerény tárigényű, csak egyetlen a gyökércsomópontból a levélcsomópontig vezető utat kell tárolni kiegészítve az út minden egyes csomópontja melletti kifejtetlen csomópontokat.
• Egy már kifejtett csomópont elhagyható a listából, ha az összes leszármazottja meg lett vizsgálva.
• Tárigénye bm+1, b elágazási tényező, m a maximális mélység.

A* algoritmus:

• A teljes becsült útköltség minimalizálása
• A csomópontokat úgy értékeli ki, hogy összekombinálja
• 2 dolgot tárolunk költség (ez a kiindulópont), út + heurisztika
• $f(n) = g(n) + h(n)$
• $f(n)$ a legolcsóbb, az n csomóponton keresztül vezető megoldás becsült költsége.
• Ha a legolcsóbb megoldást keressük, érdemes először a legkisebb $g(n) + h(n)$ értékkel rendelkező csomópontot kifejteni
• Ha a h függvény eleget tesz bizonyos feltételeknek a keresés teljes és optimális.

Kétszemélyes játékok és reprezentálásuk.

Osztályozás:

• Diszkrét játékok
  • A játszma állásból állásba vivő lépések sorozata
• Véges játékok
  • Az állásokban véges sok lehetséges lépése van minden játékosnak.
  • A játszmák véges sok lépés után véget érnek.
• Teljes információjú játékok
  • A játékosok a játékkal kapcsolatos összes információval rendelkeznek a játék folyamán.
• Determinisztikus játékok
  • Nincs szerepe a véletlennek.
• Zérusösszegű játékok
  • A játékosok nyereségének és veszteségének összege 0.

A játékok reprezentációja:

• $A,B$ két játékos
• H a játékállások halmaza
  • Kezdőállás:
    • a0, ami eleme H halmaznak.
• Játékot kezdi:
  • J0 eleme {A,B}, felváltva lépnek
• Játék menete:
  • L a lépések halmaza
    • { L | L : H -> H } (minden lépés a játékállások halmazán belüli értékek képez)
• Játék vége:
  • Játék véget ér az a állásban, ha végállás(a)
• Játékot nyeri:
  • Nyer : ${a | végállás(a)} -> {jön_{a}, volt_{a}}$
    • Valaki nyer, ha az adott állás végállás.
    • $jön_{a}$ lenne az a állásban soron következő játékos
    • $jön_{a}$ nem egyenlő $volt_{a}$-val.
• Játék állapottér reprezentációja:
  • 〈A,kezdő,C,O〉négyes, ahol
  • A = {(a,J) | a eleme H, J eleme {A,B}; J következik lépni}
  • Kezdő = (a0,J0)
  • C = {(a,J) | végállás(a), J nyer, ha nyer(a) = jöna}
  • O = { ol | ol(a,J) = (L(a),I,J eleme {A,B}, I= J}

Játékfa:

• Páros szinteken lévő állásokban a kezdőjátékos, páratlan szinteken lévőkben pedig ellenefele léphet.
• Egy állást annyi különböző csúcs szemléltet, ahány különböző módon a játék során a kezdőállásból eljuthatunk hozzá.
• Véges hosszúak az utak, mivel véges játékokkal foglalkozunk.
• Ha a játék során a játékosok kezdő állapotból valamely v eleme V állapotba érnek, azaz kezdő -> V (van olyan operátor, amely kezdőből a végállapotba visz), azt mondjuk, hogy lejátszották a játszmát.

A nyerő stratégia.

A J játékos stratégiáját a J nyerő stratégiájának nevezzük, ha (az ellenfél stratégia-választásától függetlenül) minden a stratégia alkalmazása mellett lejátszható játszmában J nyer.

Lépésajánló algoritmusok.

Három féle van:

• Minmax
• Negamax
• Alfa-béta nyesés

Minmax:

• Az optimális döntést az aktuális állapotból számolja ki, felhasználva egy egyszerű rekurzív formulát, amit az egyes követő állapotok minmax értékeinek kiszámítására a definiáló egyenletekből közvetlenül származatunk.
• A rekurzió egészen a fa leveléig folytatódik.
• A minmax értékeket a fa mentén visszafelé terjesztjük ki
• Minden csúcsban ahol nem a támogatott játékos lép min-t, ahol a támogatott max-ot választunk.

Negamax:

• Egyszerűbb rekurzív függvényt készítünk.
• Nem a támogatott játékos szerint értékeli az egyes lépéseket, hanem mindig a soron következő játékos szerint.
• Maximum keresést végzünk a közbenső csúcsoknál, negálva a közvetlenül elérhető állapotok jóságértékét.

Alfa-béta nyesés:

• Lehetséges a korrekt minmax kiszámítása anélkül, hogy minden csomópontra rá kelljen nézni.
• Ugyanazt a döntést adja vissza mint a minmax, a döntésre hatással nem lévő ágakat lenyesi.

További információk