G RÁF SZIMULÁCIÓ AZ OKTATÁSBAN

BUDAPESTI M SZAKI F ISKOLA Neumann János Informatikai Kar Informatikai Automatizált Rendszerek Szakirány Humánfejlesztési- és Módszertani Intézet Mérnök Tanári Képzés

GRÁF SZIMULÁCIÓ AZ OKTATÁSBAN

Név: B ED K DÁVID Konzulens: DR. HASSAN ELSAYED Dátum: 2005. október 24.

BUDAPESTI M

Gráf szimuláció az oktatásban

SZAKI F ISKOLA

TARTALOMJEGYZÉK TARTALOMJEGYZÉK ..................................................................................................................................... 2 1 – CÉL MEGHATÁROZÁS ............................................................................................................................ 4 2 – MEGVALÓSÍTÁSI TERV ......................................................................................................................... 5 2.1 HELYZET ÉS PROBLÉMAELEMEZÉS ............................................................................................................ 5 2.2 FONTOSABB RÉSZFELADATOK BEMUTATÁSA ........................................................................................... 5 2.3 ALKALMAZOTT MÓDSZEREK ..................................................................................................................... 5 2.4 ÉRTÉKELÉSI PONTOK KIJELÖLÉSE, ÉRTÉKELÉSI KRITÉRIUMOK MEGADÁSA ........................................... 5 2.5 PROJEKT DOKUMENTÁCIÓ FELÉPÍTÉSE...................................................................................................... 6 2.6 AZ EREDMÉNYEK HASZNOSÍTHATÓSÁGA, TERJESZTHET SÉGE ............................................................. 6 3 – IRODALOMKUTATÁS ............................................................................................................................. 7 3.1 JÁTÉKOK A TÖRTÉNELEMBEN .................................................................................................................... 7 3.2 A JÁTÉK, A SZIMULÁCIÓ ÉS AZ ESETTANULMÁNY AZ OKTATÁSBAN ..................................................... 8 3.3 LEHET SÉGEK ÉS KORLÁTOK A HAZAI JÁTÉKKULTÚRA KITERJESZTÉSÉBEN ....................................... 11 3.4 A SZÁMÍTÓGÉP, MINT OKTATÁSI ESZKÖZ ............................................................................................... 12 3.5 LABVIEW, MINT A SZÁMÍTÓGÉPES SZIMULÁCIÓ ESZKÖZE .................................................................... 14 4 – GRAPHS AND SPANNING TREES .................................................................................................... 17 4.1 - A PROGRAMRÓL ÁLTALÁBAN ............................................................................................................... 17 4.2 GRÁF, MINT MATEMATIKAI FOGALOM ................................................................................................... 17 4.2.1 Néhány alapfogalom ....................................................................................................................17 4.2.2 - Gráfok ........................................................................................................................................... 18 4.2.3 - Gráfok ábrázolása .....................................................................................................................18 4.2.4 - Minimális költségtérítés feszít fa ........................................................................................20 4.2.5 - Legrövidebb út ............................................................................................................................21 4.3- FELHASZNÁLÓI KÉZIKÖNYV................................................................................................................... 25 4.31 - Új gráf létrehozása ...................................................................................................................... 25 4.3.2 - Gráf megnyitása ........................................................................................................................28 4.3.3 - Globális beállítási lehet ségek ................................................................................................28 4.3.4 - Lokális beállítások .....................................................................................................................31 4.3.5 - Új gráf pont felvétele .................................................................................................................31 4.3.6 - Új él felvétele a gráfba ..............................................................................................................34 4.3.7 - Gráf pontok és élek módosítása illetve törlése .................................................................... 35 4.3.8 - Gráf tulajdonságainak utólagos beállítási lehet sége ...................................................... 36 4.3.9 - Az aktuális súly illetve gráf pont adat beállítása ............................................................... 36 4.3.10 - Gráf mentése .............................................................................................................................37 4.3.11 - Kapcsolatmátrix generálása..................................................................................................37 4.3.12 - Legrövidebb út meghatározása Dijkstra algoritmusa alapján .................................... 39 4.3.13 – Szerkesztés gyorsítása ........................................................................................................... 41 4.3.14 – Tömegesen felvett élek és gráf pontok módosítása és törlése ....................................... 46 4.3.15 – Útkeresés egyszer bb formája.............................................................................................47 4.4 - FEJLESZT I DOKUMENTÁCIÓ .................................................................................................................50 4.4.1 - A programról............................................................................................................................... 50 4.4.2 - A TObject3D osztály .................................................................................................................. 51 4.4.3 - A TGraph osztály........................................................................................................................54 4.4.4 – A TypeUnit további részei ....................................................................................................... 64 5 – TÁRGYSZÓ JEGYZÉK .............................................................................................................................66 6 – SZAKIRODALOM ÉS FORRÁSJEGYZÉK ........................................................................................67

2/67

BUDAPESTI M


SZAKI F ISKOLA

6.1 – F ORRÁSJEGYZÉK .....................................................................................................................................67 6.2 – LINK GY JTEMÉNY ................................................................................................................................. 67

3/67

BUDAPESTI M


SZAKI F ISKOLA

1 – CÉL MEGHATÁROZÁS A tanításra, avagy oktatásra nézve véleményem szerint nem létezik olyan módszer, melyet elsajátítva bármit képesek vagyunk a lehet legjobban átadni a hallgatóság számára. Nem lehet azonos módszerekkel irodalmat tanítani, és matematikát. El sem tudnánk képzelni történelem órát térképek, vagy számítástechnikát gépek nélkül. Ezek a dolgok kézenfekv ek, hisz elmondani, hogy merre van a Havas-alföld körülményes, megmutatva a térképen azonban nemcsak egyszer bb, de szemléletesebb is egy földrajzóra során. Ellenben mi keresni valója van egy számítógépes programnak egy matematika, rajz, a vagy mesterséges intelligencia órán? Bár megfelel en magas szinten ez a kérdés fel sem merül, hiszen léteznek olyan összetett matematikai problémák, melyeket ma már csak számítógépek tudnak véges id n belül megoldani, de vajon segítheti-e az oktatást az, hogyha adott elméleti problémákat a gyakorlatban is szemügyre veszünk? Természetesen igen. Ugyanúgy, mint ahogy könnyíti, egyszer vé és ugyanakkor változatossá teszi a tanulást egy térkép jelenléte történelem órán, a matematika órán is van helye egy számítógépnek. A „Gráf szimuláció az oktatásban” cím projekt célja bemutatni és igazolni a fentebb leírtakat, valamint megvalósítani egy szimulációs programot a matematika területér l. A szimulációs programok általában rendelkeznek az „önálló tanulás” eszközeivel is. A témakör elméleti alapjait megismerteti a felhasználóval, példákat mutat be, majd ellen rzés céljából feladatokat oldat meg, melyek értékeléséb l is tanulni lehet. A program magas szint nyelven fog elkészülni, Microsoft Windows operációs rendszer alá.

4/67

BUDAPESTI M


SZAKI F ISKOLA

2 – MEGVALÓSÍTÁSI TERV 2.1 Helyzet és problémaelemezés Külföldön, f leg az Amerikai Egyesült Államokban és Nyugat-Európában már az 1960-as, 1970-es években elkezd dött a szimulációs és játék programok ipari készítése, és elterjedése az oktatásban és képzésben. Magyarország csak az utóbbi id ben ismerte fel ennek el nyeit, és alkalmazta a gyakorlatban. Ehhez a szemlélethez társulva a „Gráf szimuláció az oktatásban” projekt elkészít egy szimulációs programot.

2.2 Fontosabb részfeladatok bemutatása Mindenek el tt teszünk egy történelmi kitér t arra nézve, hogy a játékok fejl dése mi módon kapcsolódik össze a szimulációs programok kialakulásáig, majd az irodalomkutatás kereteiben megvizsgáljuk, hogy miért alkalmazzák világszerte az oktatásban és a képzésben a szimulációs módszereket. Rátérünk arra is, hogy mi lehet az oka annak, hogy Magyarországon késve jelentkezett ez a technika, és megoldási javaslatokat is teszünk. Megemlítjük a LabView nev programozási nyelvet, mely szorosan köt dik a szimulációs programok készítéséhez, valamint teszünk kitér t arra nézve, hogy a számítógép mi módon kapcsolódik a nevelés folyamatába. Természetesen a legfontosabb részfeladatok közé tartozik a szimulációs program megvalósítása, implementálása magas szint programozási nyelven. A program a matematika tárgykörére épülve a gráfokkal fog foglalkozni (a program elnevezése Graphs and Spanning Trees lesz). A „Gráf szimuláció az oktatásban” projekt tartalmazni fogja a program felhasználói és fejleszt i kézikönyvét, valamint kitér az alkalmazás alkalmazhatóságára, el nyeire, illetve hátrányaira. Végül, összefoglaló gyanánt a fejlesztés során összegy jtött tapasztalataimat megfogalmazva ötleteket ad arra nézve, hogy hogyan készítsünk magunk olyan szimulációs programokat, melyek a magyarországi oktatás és képzés folyamatába beilleszkednek.

2.3 Alkalmazott módszerek A szimulációs program magas szint programozási nyelven lesz elkészítve. A gráfokkal foglalkozó Graphs and Spanning Trees nev alkalmazás Borland Delphi 7 rendszerben készül.

2.4 Értékelési pontok kijelölése, értékelési kritériumok megadása Az elkészült program használhatóságát szakirányú konzulensek segítségével a Budapesti M szaki F iskola hallgatósága fogja tesztelni. A

5/67

BUDAPESTI M


SZAKI F ISKOLA

tesztelés elkezdéséhez a program funkcióinak jelent s részét implementálni szükséges, így ez a projekt közepe tájékán lesz esedékes el ször. Amennyiben a hallgatóság felhasználóbarát módon képes az elkészült programot kezelni, valamint segít számukra az érintett témát könnyebben megtanulni, elsajátítani, a projekt eléri célját.

2.5 Projekt dokumentáció felépítése A dokumentáció a cél meghatározásával kezd dik, jelen megvalósítási tervvel és irodalomkutatással folytatódik. Mindezek után egy nulladik szint rendszerterv keretében a programok elméleti hátterével, valamint a programok által kit zött konkrét célok megfogalmazásával folytatódik, majd bemutatásra kerül a két program felhasználói és fejleszt i kézikönyve. A dokumentáció legvégén a fejlesztés során összegy jtött tapasztalatok fogalmazódnak meg.

2.6 Az eredmények hasznosíthatósága, terjeszthet sége A projekt els dleges célja, hogy az elkészült program segítse a hallgatóságot a megvalósított problémakör megértésében. Az alkalmazások ingyenesen elérhet ek lesznek az Interneten, amennyiben e cél megvalósul.

6/67

BUDAPESTI M


SZAKI F ISKOLA

3 – IRODALOMKUTATÁS 3.1 Játékok a történelemben A szimuláció és a játékok szoros kapcsolatban állnak egymással, ezt majd a kés bbiekben látni fogjuk. El tte azonban tekintsük át a játékok fejl désének fontosabb lépéseit történelmünkben. Játékokat azért készített az ember, hogy kikapcsolódjon, szórakozzon. Legalábbis így gondoljuk legtöbben, azonban az sem véletlen, hogy a legtöbb táblás játék valamelyest a harcászati stratégiához köt dik. Valamelyest szimulálja a harcmez eseményeit, és a gy ztes stratégia általában a harcmez n is gy zelemre vezet. Természetesen nagy általánosságokban beszélve. Az egyik legrégebbi fent maradt játéktáblát El-Mahasznában találták (Fels Egyiptom). Kora 75oo-8ooo évre tehet . A tábla 3x6 mez s, agyagból készült, és 11 kúp alakú figura tartozik hozzá. Egy másik híres lelet az Ur városából (Dél-Mezopotámia) származik. Ez agyagból készült kb. 46oo évvel ezel tt (FORRÁSJEGYZÉK: 3-I). Sokak szerint a legrégebbi táblás játék a még ma is játszott „gó”. Az els írásos feljegyzés Konfuciustól származik i.e. 5oo-ból. A gó harci játék, a tábla a lakatlan világot jelképezi, amelyet minden oldalról tenger vesz körül (FORRÁSJEGYZÉK: 3-II). A harci játékok sorából nem felejthetjük ki a sakkot sem. A sakk se valószín leg egy indiai hadijáték (csaturanga), mely a VI. században keletkezett, írásos emlékek már a VII. századból vannak róla. A csaturangát négyzet alakú, 64 egyforma szín mez n játszották. A csatura (négy) és az anga (tagozat) szavak összetétele az akkori négy fegyvernemre (gyalogság, lovasság, harci szekerek és elefántok) utal (FORRÁSJEGYZÉK: 3-III). A sakkban két játékos vezeti a küzdelmet két egyenl er vel küzd hadsereg között. Az eredmény kimenetele a két fél tudásától, stratégiai felkészültségét l függ. Megjegyzend azonban, hogy ma már nem csupán az emberek tudnak sakkozni, hanem a „gépek” is, s t mi több, jobb eredményességgel. A legkézenfekv bb megoldás arra nézve, hogy sakkprogramot készítsünk, hogy eltároljuk a történelem eddig feljegyzett híres sakk játszmáit, és mikor az emberi játékos lép, és egy helyzet el áll, a gép „nem tesz mást”, mint a memóriájában keres egy olyan játszmát, ahol azonos helyzetek mellett a gép színe nyert. Egy fokkal összetettebb megoldás, hogy a gép már az els lépés után képes végigjátszani a partit sok száz lépésre el re, minden lehet séget megvizsgálva. Ha a „végigjátszása” végén az ember nyer, az adott utat nem választja. Ilyen memóriával, kombinációs képességgel mi nem rendelkezünk, így a legjobb sakkozó is nehezen képes felvenni a versenyt a gépekkel szemben (általában sakk gépek másik sakk gépekkel játszanak). Kelet-Európába a 900-as évek körül jutott el a sakk bizánci közvetítéssel, az els írásos emlék Nyugat-Európából (Spanyolország) 1008-ból származik. 7/67

BUDAPESTI M


SZAKI F ISKOLA

A hadijátékokat a XIX. században két csoportba sorolták. Az egyiket bonyolult és merev szabályok, valóságos helyzetek jellemezték (rigid), melyben a háborús helyzetek váratlan fordulatait a dobókocka határozta meg. Ennek a típusnak a játszásához számos térkép és táblázatra volt szükség, és tényleges értéke abban ált, hogy tanította a stratégiákat a játékban résztvev kkel. A másik csoportja a hadijátékoknak a taktikára helyezte a f hangsúlyt. A „rigid” játékok egyik els képvisel je 1778-ból származik (Kriegspiel), melyhez számos térképet rajzoltak. Az ilyen játékok elterjedése azonban csak az 1870-es évekt l jellemz . Az els mai értelemben vett katonai játékot Poroszországban készítették. Ma már szinte minden hadseregben használnak a kiképzés részeként ehhez hasonló módszereket. A számítógépek elterjedésével a hosszú el készületeket igényl „rigid” típusú játékok kerültek el térbe (a hosszú el készületekben segít a számítógép). Az 1960-as években az Egyesült Államok a számítógépek segítségét is felhasználta a vietnámi háborúban (FORRÁSJEGYZÉK: 3-IV). Mindezek után elmondható, hogy a fenti „játékok” már nem a szórakozást szolgálják els sorban. Valós helyzetekben kipróbálják azokat a dolgokat, melyeket a „játékban” sikerrel alkalmaztak. Az ilyen típusú játékokat szimulációs eszközöknek hívjuk. Ez hát a történelmi kapcsolat a játék, és a szimuláció között.

3.2 A játék, a szimuláció és az esettanulmány az oktatásban A legkülönfélébb tudományterületek vezet tudósainak és kutatóinak egybehangzó véleménye az, hogy az egyes nemzetek, csoportok kiemelkedését a nemzetek fejl déséért vívott harcban nagyban befolyásolni fogja az, hogy az emberek mennyire lesznek képesek szembenézni szokatlan problémákkal, mennyire lesznek képesek figyelembe venni a különböz néz pontok által nyújtott megoldási lehet ségeket. Az ilyen néz pontok felismerésében segíthetnek minket többek között a játékok és a szimulációk, így ezek szerepe kiemelked e téren. E módszerek nagymértékben fejlesztik a kreativitást, a problémamegoldó és döntéshozatali készséget. Sok szakember a jöv nyelvének tekinti a játék- és szimulációs módszereket (FORRÁSJEGYZÉK: 3-V). Els sorban az Egyesült Államokban és Nagy-Britanniában a játék és szimuláció alapú gyakorlatok elterjedése ugrásszer en megnövekedett mind az oktatásban, mind a képzésben. A játékok, szimulációk és esettanulmányok sokoldalú és rugalmas eszközök lehetnek nemcsak az oktatási, képzési, hanem a nevelési célok elérésében is. A szimuláció során megszerzett gyakorlat alapján a részvev jelöltek lényegesen hamarabb és könnyebben jutnak el a helyes döntésig, mint azon társaik, melyek nem vettek részt szimulációs gyakorlatokban. Nem véletlen az sem, hogy az üzleti életben és a vezet képzésben hamar elterjedt a módszer. 8/67

BUDAPESTI M


SZAKI F ISKOLA

Az ipari és a katonai felhasználás mellett természetesen az oktatásban és a képzésben betöltött szerepe a legjelent sebb a szimulációs programoknak. Az els publikációk 1962-ben jelentek meg (Hemphil-Griffits-Frederiksen: Administrative Performance and Personality; Kersh, B. Y.: The Classroom Simulator). Az új törekvések azonban kezdetben csak az Amerikai Egyesült Államokban jelentek meg, egy évtizeddel kés bb aztán Európában is. A szimulációs módszerek fejl dése ma már folyamatos szerte a világon. Éppen a legutóbbi id kben (az audiovizuális technika intenzív fejl désével) vált a pedagógusok el tt egyre világosabbá, egyértelm bbé, hogy a taneszköz különösen a taneszközök együtteseinek megjelenése - magasabb hatékonyságot biztosíthat a tartalom feldolgozásában (FORRÁSJEGYZÉK: 3-VI). Az 1970-es évek kutatásai igazolták, hogy a játék, szimuláció és esettanulmány néven ismert gyakorlatok szoros összefüggésben vannak egymással. Ezt els ként Reid ismerte fel 1977-ben (Ábra 1).

Ábra 1: Reid Az ábra (Ábra 1) egészen pontosan nem Reidt l származik, hanem az munkásságát felhasználva Ellington, Addinall és Percival készítette (FORRÁSJEGYZÉK: 3-VII). Az ábráról leolvasható, hogy a játék-szimuláció-esettanulmány gyakorlattípusok hét különböz kategóriába sorolhatóak, amib l 3 „tiszta” és 4 9/67

BUDAPESTI M


SZAKI F ISKOLA

„hibrid” típusú gyakorlat. Érdemes áttekinteni a 3 alaptípus definícióját, hogy a teljes ábra érthet és világos legyen. A játék Abt (FORRÁSJEGYZÉK: 3-VIII) megfogalmazása szerint a következ : „A játék bármilyen verseny (játékos magatartás, játékos tevékenység) ellenfelek (játékosok) között, amely kényszer (játékszabályok) szerint folyik valamely cél (nyerés, gy zelem) érdekében.”. Játékos lehet bármely ember, a feladatot megfogalmazó tanár, avagy egy számítógép is. Shubik (FORRÁSJEGYZÉK: 3-IX) megfogalmazása szerint a szimuláció „…egy rendszernek vagy szervezetnek egy másik rendszerre vagy szervezetre való leképezését foglalja magába úgy, hogy az az eredeti rendszer lényeges viselkedési hasonlóságát tartalmazza. A szimulátor rendszerint egyszer bb, mint a szimulált rendszer, amely elemzés és kezelés céljaira sokkal alkalmasabb.”. Megjegyzem azonban, hogy számos más definíció is létezik az adott fogalomra. Az esettanulmány (case study) „a valóságos esetekb l kiválasztott olyan adatokon alapszik, amelyek alkalmasak arra, hogy helyesen tudjunk bemutatni egy speciális jelenséget, vagy pedig gyakorolni egy különleges döntési eljárást” (FORRÁSJEGYZÉK: 3-X). A kutatók többségének véleménye ma már megegyezik abban, hogy a játékok sorozata, a szimulációk és az esettanulmányok többé-kevésbé átfedik egymást. A hibrid típusú gyakorlatokban pedig egyszerre egy vagy több osztály jellemz i ismerhet k fel, ami hallatlanul növeli a variációs lehet ségek számát a tervezésben. A három nagy osztály között az átfedések teljesek. A játék és szimulációs technikák pontosítására Romiszowski készített egy másik ábrát is (Ábra 2), mely gyakorlati megközelítésben mutatja be az összefüggéseket és kapcsolatokat.

Ábra 2: Romiszowski

10/67

BUDAPESTI M


SZAKI F ISKOLA

Az Ábra 2-r l az is jól leolvasható, hogy ma már a szimulációs gyakorlatokban a szimulációk és esettanulmányok mellett a szerepjátékok is beletartoznak. Mindezek után megfogalmazhatjuk, hogy milyen elvárásaink lehetnek az „oktatási szimuláció” fogalommal szemben: legyen modell küls megjelenésében és/vagy hatásában legyen alkalmas arra, hogy a tanulók tudják kezelni, m ködtetni (manipulálni) tanulás céljából A modell rendszerint egyszer sített vázlata az eredeti rendszernek, tárgynak vagy folyamatnak. Egy modellnek a valóságot mindig h en kell tükröznie, bármilyen aspektusából is vizsgáljuk. A modellb l - a valósághoz képest - mindig elhagyhatók azok a részek, amelyeket nem kívánunk tanulmányozni. Az oktatójátékok feladata, hogy segítsék a tanulókat a széles kör és általános oktatási célok - mint az alapjártasságok/készségek, általános ismeretek/tudás - elérésében. A készség (fejleszt ) játékok célja, hogy segítsék a tanulókat bizonyos speciális, sok esetben a munkával (szakmával) kapcsolatos célok megvalósításában. A szimulációs játékok egyszerre kínálják mindazokat a lehet ségeket és módszereket, amelyeket külön-külön biztosítanak a játékok és a szimulációs technikák. A játékok versenyfaktora és a szimulációk sokoldalúsága teszi a szimulációs játékot - nemcsak a nevelésben és oktatásban - kétségtelenül az egyik legsokoldalúbb és leghatékonyabb m veleti eszközzé.

3.3 Lehet ségek és korlátok a hazai játékkultúra kiterjesztésében Külföldön az 1960-as években látható robbanásszer fejl dés a játék- és szimulációs módszerek terén. Miért nem kapcsolódott be Magyarország ebbe a hullámba? A dolog oka valószín leg az, hogy nyugaton jó üzleti érzékkel rendelkez emberek fantáziát láttak benne, és támogatták, itthon azonban nem. Az ilyen játékok és szimulációk tervezése, gyártása és forgalmazása jelent s hasznot hoz, és az angolszász országok nagy felvev piacával szemben mi nehezen tudunk lépést tartani (egy angol nyelven írt programot könnyebb eladni külföldre, mint egy magyar nyelven írtat). Magyarországon a kis felvev piac miatt a költséges tervezés és gyártás nem térül meg, így nem éri meg ilyenbe beruházni. Egy esetleges megoldás erre, hogy azon programokat, melyek olyan szakterületbe tartoznak, ahol például az angol elterjedt nyelv (pl. informatika), nem magyarul, hanem angolul készítünk el. Ugyancsak lehet ség van arra, hogy a program változtatása nélkül többnyelv programot készítsünk egy egyszer nyelv állomány lecserélésével.

11/67

BUDAPESTI M


SZAKI F ISKOLA

A magyarországi helyzeten természetesen változtatni érdemes, így más módszereket célszer keresni. Az egyik ilyen módszer el tt nézzük meg Kupisiewicz lényegre mutató megállapítását: "… nem kizárólag a taneszközök határozzák meg a didaktikai munka és nevelés végs eredményét, viszont gazdagítják az oktatási módszereket, ezáltal hozzájárulnak ezek hatékonyságának növeléséhez…" Nagy Sándor véleménye szerint általánosságban fogalmazva nem a taneszközökre nézve állunk rosszul, hanem a software-ek terén. Külföldön már hosszú id óta sikerrel használnak úgynevezett „nem hardware” megoldásokat, melyekb l Magyarországnak sajnos hiánya van. Legkézenfekv bb lehet ség, hogy a hiányzó software elemeket pótoljuk, hogy a pedagógusok – esetleg a hallgatóság bevonásával közösen – valósítják meg ezeket.

3.4 A számítógép, mint oktatási eszköz Egy szimulációs feladat bemutatására számos segédeszközünk lehet. Elképzelhet például egy valós fizikai modell. Az ilyen jelleg prezentálása egy problémának valahol a kísérlet és a szimuláció között van. Azonban, ha egy problémát számítógépen mutatunk be (és természetesen „valós” környezetében nem köt dik szorosan számítógépekhez a téma), akkor számítógépes szimulációról beszélhetünk. Vizsgáljuk meg, hogy az oktatástechnológia folyamatába hol kapcsolódik be a számítógép, valamint mik a használatának el nyei, illetve hátrányai (FORRÁSJEGYZÉK: 3-XI). Minden kornak, korszaknak megvannak azon oktatási eszközei, melyek használata „divatos”. Egy id ben az írásvetít volt az, amit felfedezett az oktatás, tanulmányok születtek arról, hogy mennyivel jobb, mint a kréta. Ma ugyanígy a számítógép van ebben a helyzetben. Ennek ellenére a számítógép nem tudja kiváltani az eddigi módszereket, mivel minden módszernek vannak olyan tulajdonságai, melyek kiemelked ek a többihez viszonyítva. A kréta, vagy a tanár egészségét jobban figyelembe vev tábla filc használatával a hallgatóság a gondolkodás folyamatát ismerheti meg. Ugyanerre a célra bár léteznek számítógépes megoldások is, véleményem szerint ezek az otthoni tanulás kiegészítésére alkalmasak (felidézi az órán tanár által sorrendben bemutatott feladatmegoldást), nem pedig órai használatara. A tankönyv, mint oktatási eszköz szerepe ma még kiemelked , és egyértelm en több el nnyel jár, mint egy úgynevezett e-book, azaz számítógépen olvasható párja. A diák, ha számítógép el tt ül, és olvasnia kell a monitort hosszú órákon keresztül, akkor ennek a tudásnak a hatékonysága nem lesz megfelel , nem beszélve arról, hogy mind a szeme, mind a gerincoszlopa károsodhat. Sokkal kényelmesebb ágyon feküdni, átfordulni, sétálni, buszon olvasni, élni az életet, miközben bármikor el vehetjük a tankönyvet, hogy tanuljunk, mint adott helyhez fixen kötve elsajátítani az elméleti tudást.

12/67

BUDAPESTI M


SZAKI F ISKOLA

Véleményem szerint azonban ennek látható a közeljöv ben a megváltozása. Kezdenek elterjedni a tenyérgépek (Pocket PC) és a tábla PC-k (Tablet PC), melyek alkalmasak méretüknél fogva arra, hogy szinte bárhol úgy tudjuk forgatni ket, mint egy könyvet, ráadásul egyéb járulékos el nyökkel is jár, melyeket talán említeni sem érdemes (Pl. sokan zenehallgatás mellett hatékonyabban tudnak tanulni, ez egy hordozható számítógép segítségével bármikor elérhet , avagy, csak hogy a legkézenfekv bbet említsem, egy Tablet PC-n könyvtárnyi irodalmat cipelhetünk magunkkal, így ha hirtelen ahhoz van kedvünk, elolvashatunk egy verset, majd visszatérhetünk tanulmányainkhoz). Térjünk rá a számítógépre. Nyirati László véleménye szerint „csak azokon a területeken lehet az oktatásban hatékonyan felhasználni, amely területeken a mindennapi életben is érezhet en jelen lesz. Mivel várhatóan egyre több ilyen terület jelenik meg, ahol a számítógép szerepet kap, egyre több szempont jöhet az oktatásban is a számítógép, vagy a számítógéppel segített tanulás módszereihez”. Mire is jó egy számítógép az oktatási folyamatban? A kérdés megválaszolása ma már kézenfekv : Ahol írásos feladat el kerül, ott a szövegszerkeszt k, táblázatkezel k segítségével a tanár munkája kényelmesebb, gyorsabb, egységesebb lesz, melynek hasznát a diákok is megélik. Az el adásokat kísér prezentációkat erre alkalmas software-ekkel el lehet készíteni, és projekttor segítségével ki lehet vetíteni. Szinte nem létezik olyan bemutatható, szemléltethet dolog, melyet nem lehet számítógépre ültetni. Képeket, hangokat, videókat digitalizálhatunk be, és mutathatjuk be a hallgatóságnak számítógép segítségével. Minden az órán bemutatott, kivetített anyagot a diákok könnyen elérhetik otthon is, amennyiben a tanár elérhet vé teszi azt (pl. Internet segítségével). Számos szakmai tárgy, mint pl. elektronika, számítástechnika, építészet használ számítógépeket, hiszen maga az ipar is alkalmazza ket. Amennyiben minden diák számítógép el tt ül az órán, lehet ség van interaktív feladatok megoldására, melyb l a tanár azonnal pontos képet kaphat az egyes emberek felkészültségéb l, avagy hogy sikerült-e átadnia a tudást, vagy még gyakorlásra szorulnak a hallgatók. Els sorban a fels oktatásban, a rugalmasabb id beosztás és nagyobb távolságok miatt a tanár és hallgató közötti internetes levelezés (e-mail) a kapcsolattartásnak fontos eleme. Még bizonyosan lehetne találni felhasználási területeket, azonban legvégül a jelen projekt számára legfontosabbat említsük meg: a számítógépes szimulációt. Két oktatási eszközt szorosan kapcsolni szoktak a számítógépekhez, mégpedig a multimédiát, és az Internetet, így ezekkel is érdemes foglalkoznunk.

13/67

BUDAPESTI M


SZAKI F ISKOLA

A multimédia szerepét Nyirati László úgy látja, mint a „teljes irodalmat”. Nem tanítható minden egyes könyv az iskolákban (sajnos csak töredéke annak, mint amit minden embernek ajánlott lenne elolvasni), mégis sokan vannak, akik olvasnak iskolán kívül is. A multimédiás anyagok elkészítése sok munkával jár, és kevés sikerrel. Jelenleg még üzletileg sem éri meg, mert általában többletinformációkat tartalmaz, nem pedig a számon kért anyagot, valamint – mint már említettem – nem kényelmes számítógép el tt ülve tanulni. Ennek ellenére a haszna vitathatatlan, az otthoni tanulás remek eszköze, és az iskolán kívüli ismeretszerzést és információgy jtést gyorsítja, segíti. Az Internethez Nyirati László egy másik hasonlatot hoz fel, miszerint szerepe olyan, mint a TV-é, a haveroké, az utcáé. Az Internettel a diákok, mint társalgási eszközzel találkoznak (számos egyéb lehet ség mellett persze), és mint ilyennek a nevelésre tett hatása kiemelked (mint ahogy a TV-nek, haveroknak, utcának). A „jó” tanárnak ezt a saját el nyére érdemes fordítania, megmutatva a diáknak a hatékony és jó irányú felhasználását.

3.5 LabView, mint a számítógépes szimuláció eszköze A „Gráf szimuláció az oktatásban” projektb l véleményem szerint nem szabad kihagyni a LabView program rövid bemutatását. A LabView eredetileg folyamatirányításra és mérésadatgy jtésre szánt alkalmazás volt, mára azonban egy teljes érték általános programozási nyelv lett. Programozni grafikusan, a Gnyelv szabályait figyelembe véve lehet. A LabView programok (VI-ok) két részb l állnak, egy grafikus felhasználói felületb l, és a tényleges programot tartalmazó diagramból. Segítségével minimális programozási tudás ismeretében lehet többek között szimulációs feladatokat is készíteni. Aki jártas magas, avagy alacsony szint programozási nyelvekben, annak sokszor körülményes lehet megoldani egy adott problémát folyamatmodell segítségével, ezért van lehet ségünk arra is, hogy a LabView VI programunkba beékeljünk C++ forráskódot! Bár a projekt céljától eltér a LabView programok elemzése, megemlítem, hogy volt szerencsém egy úgynevezett „Inverted Pendulum” feladat megoldását elvégezni Norvégiában LabView segítségével. Az „Inverted Pendulum” egy irányítástechnikai probléma, melyet egy sepr egy ujjon való egyensúlyozásához tudnék hasonlítani. Ezt a feladatot kell egy modell, egy a modellt állandóan vev kamera, és a számítógépen futó LabView program segítségével megoldani. A köd szimulációs feladat eredménye, hogy a számítógép gyakorlatilag bármeddig képes „egyensúlyozni a sepr vel”, amíg a fényviszonyok megfelel ek (kamera képe miatt fontos). A fenti program bemutatása rendkívül terjedelmes lenne, ezért szemléltetésképpen egy sokkal egyszer bb feladatot fogunk elkészíteni LabView programban. A feladat legyen az, hogy megadott két számot kivonunk egymásból, de minden esetben a nagyobbat vonjuk ki a kisebb l (a feladatnak számos különböz megoldása van, mi egyet mutatunk most be)! 14/67

BUDAPESTI M


SZAKI F ISKOLA

A probléma matematikai hátterével természetesen senkinek sincs problémája, a szimuláció célja nem is a felhasználhatóság, csupán a LabView bemutatása. Legels lépésben megtervezzük a grafikus felületünket. Szükségünk lesz két olyan mez re, ahova beírhatjuk a két számot, valamint egy olyanra, ahol az eredmény megjelenik (Ábra 3).

Ábra 3: LabView Front panel A STOP gomb szerepe az, hogy a programunk addig fog futni, míg a STOP gombot meg nem nyomjuk. Ha ezzel kész vagyunk, akkor el kell készíteni a tényleges programot. Ezt az (Ábra 4) tartalmazza.

15/67

BUDAPESTI M


SZAKI F ISKOLA

Ábra 4: LabView Black Diagram Ha futtatjuk a programunkat (Ábra 5 és Ábra 6), akkor megfigyelhetjük, hogy függetlenül attól, hogy melyik mez be írunk nagyobb számot, a végeredmény minden esetben a két szám különbségének abszolút értéke lesz (a feladatot természetesen abszolút érték jel használatával is meg lehetett volna valósítani).

Ábra 5: Futás eredménye I

Ábra 6: Futás eredménye II

16/67

BUDAPESTI M


SZAKI F ISKOLA

4 – GRAPHS AND SPANNING TREES 4.1 - A programról általában A Graphs and spanning trees (Gráfok és feszít fák) alkalmazás egy szimulációs program. Modellezni lehet vele a gráfok problémakörébe tartozó feladatokat. Ide lehet sorolni egy egyszer matematikai problémától kezdve egy összetett térképprogramig mindent, s t, akár elvont fogalmak szintjén értelmezve, gráfok segítségével akár gondolkodásmód is bemutatható! Az alkalmazás egy úgynevezett MDI Application, azaz egy többdokumentumos alkalmazás, mint például a Microsoft Word, vagy az Adobe Photoshop. Ebb l következik, hogy egyszerre több gráffal is tudunk dolgozni általa, és mindegyiket egymástól függetlenül tudjuk kezelni. A gráfnak tudunk új csomópontokat, új éleket felvenni, módosítani, avagy törölni. Be tudjuk állítani a gráf típusát, tulajdonságait és bizonyos mértékig konvertálni is tudunk gráfokat. Személyre szabhatjuk, hogy a három dimenzióban mozgó gráfunk képén milyen információk jelenjenek meg, és mindezek milyen színnel, bet típussal, stb. Képesek vagyunk adott feltételek megadása mellett kapcsolatmátrix készítésére, valamint ha ezt megtettük, akkor Dijkstra algoritmusa segítségével meg tudjuk bármely két pont között határozni a legrövidebb utat (adott súly szerint). A program a kés bbiekben szomszédsági listák elkészítésére is alkalmas lesz, valamint többféle útkeres algoritmust fog tudni kezelni. Mélységi és szélességi bejárás alapján tudunk majd információt keresni, és lehet ségeink között lesz a gráf alapján egy feszít fa elkészítése is. Az útkeresés során számos információt tudunk gy jteni, mely listázása nehézkesen átlátható. Tervbe van véve egy script nyelv elkészítése, melynek segítségével a töménytelen információt sz rni fogjuk tudni. Mindenezek lehet ségek felsorolásszint bemutatása után egy nagyon fontos dologot meg kell említeni: mik is azok a gráfok valójában? Ahhoz, hogy a gráfokkal dolgozzunk, hogy felhasználjuk ket munkánk, tanulmányaink során, néhány alapfogalommal tisztában kell lennünk. Az alkalmazés kés bbi verzióiban ezen el tanulmányokat a felhasználó is megteheti majd interaktív bemutató keretében!

4.2 Gráf, mint matematikai fogalom 4.2.1 Néhány alapfogalom Hurok él: olyan él, melynek kezd és végpontja azonos csúcsból indul, illetve érkezik. Szomszéd pontok: A és B szomszéd pontok, ha a gráfban van él A és B között Fokszám: Megadja, hogy egy adott pontra hány él illeszkedik.

17/67

BUDAPESTI M


SZAKI F ISKOLA

Izolált pont: olyan pont, amelyre nem illeszkedik él, azaz fokszáma nulla. Többszörös élek: Ugyanazon kezd és végpontokat tartalmazzák. 4.2.2 - Gráfok Sokféle gráf létezik (a gráf egy absztrakt adatszerkezet), és mindegyiknek megvan a maga felhasználási területe. Csak felsorolás szinten nézzük ezeket végig: Egyszer összefügg gráf Egyszer nem összefügg gráf Irányított összefügg gráf Irányított nem összefügg gráf Súlyozott összefügg gráf Súlyozott nem összefügg gráf Irányított és súlyozott összefügg gráf Irányított és súlyozott nem összefügg gráf Speciális gráf (hurokmentes, minimum távolság limit, többszörös élek stb…) Természetesen a teljesség igényével azok vannak felsorolva, melyekkel már találkoztam. A program mindegyik gráftípust támogatni fogja. Egy adott problémának a szimulálásához nekünk majd a megfelel modellt kell megépítenünk. Például egy térképprogramhoz nekünk egy súlyozott és irányított összefügg gráfra lesz szükségünk, ami nem hurokmentes, tartalmazhat többszörös éleket. 4.2.3 - Gráfok ábrázolása Gráfok ábrázolására is többféle módszer létezik, és a legtöbb esetben függ a gráf típusától. Nézzünk el ször egy egyszer gráfot, amit statikus adatstruktúrával tárolunk (nagyon redundáns megoldás). A kapcsolatmátrixszal történ tárolást a (7. ábra) mutatja. X 1 2 3 4 5 6 7

1 H I H I H H H

2 I H I H H I H

3 H I H I I H H

4 I H I H H H H

5 H H I H H I I

6 H I H H I H I

7 H H H H I I H

7. ábra - Kapcsolatmátrixos ábrázolás

Talán jól látszik az ábráról pár dolog: Egy adott i, j a mátrixban I (igaz) vagy H (hamis) érétket vehet fel.

18/67

BUDAPESTI M


SZAKI F ISKOLA

Adott i, j igaz lesz, ha i és j között létezik él. A f átlón lév értékek mindig hamisak, amennyiben a gráfban nincsenek hurok élek. A statikus mátrix a f átlóra szimmetrikus. Lehet ség van dinamikus tárolásra is, ezt a (8. ábra) alapján lehet elképzelni.

8. ábra - Szomszédsági lista Ezt a tárolási elemet nevezik szomszédsági listának. A harmadik lehetséges módszert már nem rajzolom fel, de könnyen el lehet képzelni egy teljesen dinamikus struktúrát, melynél a statikus mutató vektort felváltja egy olyan dinamikus adatszerkezet, mely elemeinek két mutató mezeje van. Tegyük fel, hogy az új gráfunk súlyozott és irányított, vannak benne többszörös élek. Ekkor a kapcsolatmátrixát a (9. ábra) prezentálja (a gráf ábrája nem méretarányos). X 1 2 3 4 5 6 7

1 0 20 0 10 0 0 0

2 0 0 25 0 0 0 0

3 0 0 0 0 35 0 0

4 10 0 5 0 0 0 0

5 6 7 0 0 0 0 40 0 35 0 0 0 0 0 0 15 0 0 0 30 17 30 0

9. ábra - Súlyozott, irányított gráf Ami látszik a kapcsolatmátrixról: Megsz nt a szimmetria az irányítottság miatt. Csak ott szimmetrikusak az értékek, ahol többszörös él van. Ott, ahol nincs él, ott 0 szerepel.

19/67

BUDAPESTI M


SZAKI F ISKOLA

4.2.4 - Minimális költségtérítés feszít fa A feszít fa fogalma: Egy g gráfnak egy másik F gráf feszít fája, ha F tartalmazza G összes pontját, további pontokat nem tartalmaz és G élei közül annyit tartalmaz, amennyi F-et összefügg vé teszi, de F körmentes (fa). A minimális költség feszít fa fogalma: Egy G gráf minimális költség feszít fája az a fa-gráf, amely feszít fája G-nek, és G összes lehetséges feszít fája közül éleinek összes hossza a legkisebb (elképzelhet több megoldás is). Algoritmusa MinfeszFa(i) PriSorInit(Sor) Segéd.pont:=i Segéd.súly:=0 PriSorBa(Sor,Segéd) Érintett(i):=0 Ciklus PriSorBól(Sor,Segéd) i:=Segéd.pont ÉletBeilleszt(Fa,Érintett(i),i) Ciklus j:=1-t l N-ig Ha A(i,j)>0 akkor Ha Érintett(j)=NEMÉRINTETT akkor Segéd.pont:=j Segéd.súly:=A(i,j) PriSorba(Sor,Segéd) Érintett(j):=i különben VanRövidebb(Sor,j,A(i,j),Volt) Ha Volt akkor Érintett(j):=i elágazás vége elágazás vége elágazás vége Ciklus vége amíg nem(PriSorÜres(Sor)) Eljárás vége

20/67

BUDAPESTI M

Gráf szimuláció az oktatásban Megjegyzések: NEMÉRINTETT

Életbeilleszt (G,x,y) VanRövidebb (Sor,a,b,Volt)

SZAKI F ISKOLA

az az érték, amely jelzi, hogy egy adott pontot a bejárás során már érintettünk, vagy sem. Kezdetben Érintett() vektor minden eleme ezt tartalmazza. a G gráfba az x,y pontok közé élet illeszt be megvizsgálja, hogy szerepel-e az „a” pont a prioritási sorban, ha igen, akkor megvizsgálja, hogy a „b” súlynál nagyobb-e az ott szerepl pont súlya. Ha igen, akkor kicseréli ezt a pontot az „a” pontra, amelynek „b” a súlya. Ha a sor így módosul, akkor Volt=igaz lesz.

4.2.5 - Legrövidebb út Fogalama A legrövidebb út fogalmát kétféleképpen értelmezhetjük: A kiindulópontból a végpontig milyen úton kell haladnunk, hogy kevesebb csomóponton lépjünk át, mint bármely más úton? Ennél a feladatnál akár súlyozatlan, akár súlyozott, kezelhetjük úgy a gráfot, mintha éleinek hosszúsága (súlya) egységnyi lenne. A kiindulópontból a végpontig milyen úton kell haladnunk, hogy az utat alkotó élek összes hossza kisebb legyen, mint bármely más út esetén? Ennél a feladat természetesen súlyozott gráfot feltételez. Egyértelm en látszik, hogy a második eset sokkal általánosabb, ráadásul a térképprogramhoz is ez van közelebb, így ezzel foglalkozok a továbbiakban. A probléma megoldására számos algoritmust dolgoztak ki. Ezek közül alapvet nek számít a neves holland matematikus Dijkstra 1959-ben közölt algoritmusa, ezért itt is ezt ismertetem. Az algoritmus lényege Lássuk el a gráf minden pontját egy címkével, amely a következ adatokat tartalmazza: a pillanatnyilag ismert legrövidebb úton az adott pont milyen távolságra van a kiindulóponttól (kezdetben legyen ez az adat minden pont esetén végtelen nagy) az adott pontnak melyik az a szomszédos pontja, amely fel l haladva az el bbi távolságot kaptuk Egy csomópont címkéje kétféle lehet: ideiglenes: még lehetséges, hogy más irányból rövidebb utat is találunk hozzá a kiindulópontból 21/67

BUDAPESTI M


SZAKI F ISKOLA

állandó: a kiindulópontból már minden hozzá vezet utat megvizsgáltunk, s rövidebb út nem lehetséges Az algoritmus lényege az, hogy meghatározzuk minden pont legrövidebb távolságát a kiindulóponttól számítva, s mivel minden pont címkéje tartalmazza azt is, hogy ezen úton melyik pont el zi meg, a végponttól visszafelé haladva meghatározhatjuk a két pont közötti legrövidebb utat. Nézzük ezt most egy példán keresztül (10. ábra).

22/67

BUDAPESTI M


SZAKI F ISKOLA

10. ábra - A legrövidebb út algoritmus Az algoritmus részletesebben 1. Inicializáljuk a gráf-pontok legrövidebb útjait tároló adatszerkezetet. 2. Az aktuális pont legyen a kiinduló pont 3. Járjuk be az aktuális pont minden ideiglenes szomszédját (szélességi bejárás). Ha találunk olyan szomszéd pontot, amelyhez az aktuális pont fel l rálépve rövidebb úton jutnánk el a kiinduló ponttól, mint a címkében rögzített korábbi irányból, akkor e pont címkéjét módosítjuk. A módosítás: a kezd ponttól mért távolságnak beírjuk az új irányból mért távolságot, a megel pont helyére pedig az aktuális pontot. 4. A gráf összes ideiglenes címkéjét megvizsgálva kiválasztjuk azt a pontot, amely az ideiglenesek közül a legrövidebb úton érhet el a kezd pontból, vagyis azt, amelyiknek a címkéjében a hosszúság értéke a legkisebb. E pont címkéjét véglegesre állítjuk, ezzel jelezve, hogy e ponthoz nem vezethet a már bejegyzettnél rövidebb út. 5. Legyen most az így kiválasztott pont az aktuális.

23/67

BUDAPESTI M


SZAKI F ISKOLA

6. Ismételjük a 3. részt l a m veletet egészen addig, amíg az aktuális pont azonos nem lesz a végponttal. Az algoritmus pszeudokódja LegrövidebbÚt (A, kezd , vég, N) Init(állapot) aktuális:=kezd állapot[aktuális].hossz:=0 állapot[aktuális].címke:=VÉGLEGES ismétlés SzomszédokBejárása(A,N,aktuális,állapot) aktuális:=Minimum(állapot,N) állapot[aktuális].címke:=VÉGLEGES amíg aktuális=vég EredményKiírása(állapot,kezd ,vég) Eljárás vége SzomszédokBejárása(A,N,aktuális,állapot) Ciklus i:=1-t l N-ig Ha (A[aktuális,i]<>0) és (állapot[i].címke=IDEINGLENES) akkor Ha (állapot[aktuális].hossz+A[aktuális,i])<állapot[i].hossz akkor állapot[i].el :=aktuális állapot[i].hossz:= állapot[aktuális].hossz+A[aktuális,i] Elágazás vége Elágazás vége Ciklus vége Eljárás vége A fenti algoritmusban ’A’ jelöli a gráf kapcsolatmátrixát, ’N’ pedig a gráf pontjainak számát.

24/67

BUDAPESTI M


SZAKI F ISKOLA

4.3- Felhasználói kézikönyv

11. ábra: Képerny kép indítás után 4.31 - Új gráf létrehozása A [File|New graph] (File menü New graph parancsa) hatására a gráf tulajdonságait beállító ablakot láthatunk (12. ábra). Itt számos adatot megadhatunk, mely a gráfunk m ködését a jöv ben er sen befolyásolni fogja. Vannak olyan tulajdonságok, melyek csak itt állíthatóak, és vannak, melyek módosítására a program kés bbi részén is lesz lehet ség.

25/67

BUDAPESTI M


SZAKI F ISKOLA

12. ábra: Új gráf létrehozása A gráf nevét (Name of graph) mindenképp adjuk meg, különben NonameGraph lesz a munkánk neve, és amennyiben ezt a nevet meghagyjuk, a következ NonameGraph felülírhatja ezen gráfunkat (amennyiben nem adunk meg nevet, a program figyelmeztet minket, hogy a kés bbiekben ne felejtsük beállítani). A gráf neve lesz elmentés után egy könyvtár neve, benne számos különböz kiterjesztés file-lal, melyeknek a nevük szintén az itt megadott (a gráf betöltéséhez természetesen minden file-ra szükségünk lesz). A gráf típusát se felejtsük el beállítani (Type of graph). Négy alapvet en különböz gráfot ismer a program. Az egyszer gráf (Simple graph) pontokból, és azokat összeköt élekb l áll. Az irányított gráf (Guided graph) éleinek irányítottságot adhatunk, a súlyozott gráf esetén (Weighted graph) pedig súlyértékeket. Az utolsó lehet ség az utóbbi kett kombinációja (Guided weighted graph), mely például egy térkép program szimulációjához is szükséges lehet. Beállíthatjuk a tárolás típusát (Storage), hogy statikus, avagy dinamikus legyen-e, de ez a lehet ség még nincs kihasználva. Egyel re minden gráf teljesen statikus adatszerkezetekb l épül fel. A többszörös élek (Multiple edges) engedélyezése, illetve tiltása még szintén nincs implementálva. Nagyon fontos, és csak itt megadható tulajdonsága egy gráfnak a grafikus mérete! Ez egy kép méretét jelenti, melyre a gráf csomópontokat elhelyezhetjük

26/67

BUDAPESTI M


SZAKI F ISKOLA

három dimenzióban. Minimálisan ez az érték 300 (nem is enged a program kisebb értéket megadni), azaz egy 300x300x300-as kockában tudunk dolgozni, mégpedig koordináták nyelvén szólva mind az X, Y és Z tengely esetén az értelmezési tartomány a (-150;150) intervallum. Egy megjegyzést is tárolhatunk minden gráf esetén (Comment), melynek a megadása természetesen nem kötelez . Mindezek mellett lehet ségünk van két lista elkészítésére is még szintén ebben az ablakban: gráf pontok adatai (Data of graph points) és súlyvektor beállítása (Multiple weights). Mindkét esetben tíz elemet vehetünk fel a listába (statikus esetben), és minden elemnek beállíthatjuk a nevét (Item name), típusát (Item type) és alapértelmezett értékét (Default value)(13. ábra). A név alapján tudjuk majd azonosítani. Az alapértelmezett érték megadása nem kötelez (ha nem adjuk meg, beállít helyettünk egy értéket a program). De mire is jók ezek nekünk?

13. ábra: Új elem hozzáadása a gráf-pontok illetve a súlyvektor listájába Minden gráf pont esetén tárolhatunk tíz különféle értéket az adott típusnak megfelel en, melyeket aztán script programok írása esetén fel tudunk használni, és/vagy modellezés során hasznos információkkal tudjuk ellátni a gráfunk csúcspontjait. Térképprogram esetén például, itt tárolhatjuk majd az olyan kiegészít információkat, hogy az adott pont most egy járdán van-e, avagy egy zebrán, stb. Az élek esetén ugyanezen az elven m ködik a súlyvektor megadása. Nem csupán egy súly tartozhat egy élhez, hanem minden élhez egy maximum tízelem vektor tartozik (statikus esetben). Térképprogram esetén egyik súly tárolhatja a két gráf pont közötti út hosszát, egy másik az adott úton a maximális haladási sebességet, a harmadik azonosíthatja a felület típusát (aszfalt, földút, stb.), stb. Lényegében a KRESZ szabályok figyelembevétele e két lista segítségével megvalósulhat, amennyiben a szimulációs programmal egy komolyabb térképprogram motorját szeretnénk elkészíteni! Ezt a két listát még a kés bbiekben is tudjuk majd szerkeszteni.

27/67

BUDAPESTI M


SZAKI F ISKOLA

14. ábra: Egy létrehozott új gráf 4.3.2 - Gráf megnyitása A [File|Open graph] hatására egy standard file megnyitó ablakban a (*.grp) file-okat tudjuk megnyitni. Ez egy szöveges állomány, mely lényegében a gráf alapvet tulajdonságait tárolja. Szükséges, hogy abban a könyvtárban, ahonnan megnyitottuk a *.grp file-t, legyen további öt azonos nev állomány is (*.das, *.dat, *.edg, *.pnt, *.was)! Ezen állományok mind egyt l egyik binárisak. 4.3.3 - Globális beállítási lehet ségek A program számos beállítási lehet séggel rendelkezik, melyek minden megnyitott gráfra hatással vannak. Ezeket a [Setting] menüben találhatjuk. Nézzük elsz ször a [Setting|Show information on graph] menüpontot. Itt azokat a vizuális tényez ket tudjuk beállítani, mely a gráfunkon megjelen adatok kinézetét befolyásolják (15. ábra).

28/67

BUDAPESTI M


SZAKI F ISKOLA

15. ábra: Megjelenítési beállítások A gráf grafikai megjelenése és azon információk, melyek a gráfon megjelennek egymástól függetlenül kezelhet k. Meg lehet adni, hogy az egyes gráf pontoknál, valamint az egyes élek esetén milyen információ jelenjen meg. Beállíthatjuk, hogy a pontok illetve élek sorszáma (Serial of graph points/Serial of graph edges), avagy neve (Name of graph points if allow/Name of graph edges if allow) jelenjen meg, és lehet ségünk van kikapcsolni mindenféle információ megjelenítését is (none). Továbbá megadhatjuk, hogy valamelyik adatmez , illetve súlymez jelenjen meg (One datum of graph points/One weight of graph edges). Amennyiben a gráf pontok vagy az élek nevét állítjuk be, és vannak olyan pontok/élek, melyeknek nincs beállítva név érték (majd kés bb visszatérünk arra, hogy mit lehet beállítani az egyes pontok és élek esetén), akkor nem jelenik meg semmi az adott pontnál/élnél. Meg lehet adni a gráfok hátterének színét (Background color), valamint hogy a gráfon megjelen szövegek háttere felülírja-e a képet, vagy ne (érdemes kipróbálni, hogy ki melyik variációt látja át jobban)(Texts overwrite the graphics). A gráfon megjelen feliratok színét egyesével meg tudjuk adni. Ehhez kattintsunk az adott rádiógomb melletti kis színezett téglalapra. Van arra is lehet ségünk, hogy egy kattintásra minden él és gráf-pont színét egy el re megadottra állítsunk be (Use adjusted colors). Ezáltal bináris képet kaphatunk (ha kikapcsoljuk a feliratokat, vagy beállítjuk azokat is erre a színre). Az élek és a gráf-pontok színét egyesével tudjuk majd beállítani felvételükkor. Mindenféle felirat bet típusa egységes. Ezt a „Set font” gombra kattintva tudjuk beállítani. 29/67

BUDAPESTI M


SZAKI F ISKOLA

Utolsó lehet ségként - ebben a menüben - az út színét adhatjuk meg (Way color). Ez lesz a színe azon éleknek, melyek az útkeresés eredményében „részt vesznek”. Térjünk át a [Setting|Global constants] menüpontra. Itt a legtöbb tényez csak információt közöl a felhasználóval, beállítani egyáltalán nem, vagy majd csak a program kés bbi verzióban lesz lehetséges (16. ábra).

16. ábra: Globális konstansok és változók A statikus jellegb l adódóan gráfunknak vannak bizonyos számbeli korlátai. Ezeket átállítani csak forráskód szinten lehet, ezért a felhasználó csak mint információ láthatja. Nézzük ezek magyarázatát sorban: Maximális elemszáma a súlyvektornak és a pontokban tárolható adat tömbnek (Max item of weights and data). Legfeljebb ennyi gráf-pont lehet a gráfunkban (Max graph points). Legfeljebb ennyi él lehet a gráfunkban (Max graph edges). Egy adott gráf-pont nem csupán egy grafikai pontnak felel meg, mivel egy kis 3D-s objektummal jelöljük meg a képen. Emiatt egy fels korlátja van ennek is. Célszer en ez a szám lényegesen magasabb, mint a gráf-pontok maximális száma (Max graphic points). Az irányított él esetén maga az él is tartalmaz további grafikai pontokat (a nyíl miatt)! Az el alapján a maximális grafikai élek száma is korlátozott (Max graphic edges). A program által használt egyedi szoftveres 3D motor képes úgynevezett robotkar kezelésére. Egy konstans meghatározza azt, hogy maximum mennyi kartagja lehet a robotunknak. Ez fixen három ebben a programban, mivel nincs kihasználva a 3D motor ezen funkciója (Max arm of 3D objects). 30/67

BUDAPESTI M


SZAKI F ISKOLA

Manuálisan tudunk készíteni egyedi mintákat arra nézve, hogy egy gráfpont hogyan nézzen ki. Egy konstans tárolja, hogy egy ilyen minta maximum mennyi grafikai pontból állhat. A grafikai élek száma nincs korlátozva (Max graphic points of each shapes). Ugyanitt le tudjuk olvasni a sémák listáját tároló szöveges file nevét (Shape List file name), valamint az alapértelmezett könyvtárát a sémáknak (Shape files directory) és a gráfoknak (Save directory). A jelenlegi verzióban még két változó értékét tudjuk leolvasni és módosítani (!) a „Global constants” menüben: az irányított él két grafikai paraméterét (Directivity Length és Directivity Length 2). Ezek funkcióját leírni nehézkes, célszer kipróbálni, hogy módosításukkal mi változik a képen (a nyíl különböz mérete fog változni irányított gráfok esetén). 4.3.4 - Lokális beállítások Létrehozva, avagy megnyitva egy új gráfot a menüsor kiegészül számos új elemmel. A [Local Setting] menüben a gráf forgatásáért felel s grafikai ablak egy vizuális effektjét tudjuk ki, illetve bekapcsolni (Allow animated frame/Forbid animated frame). Vizsgáljuk meg közelebbr l a gráf forgatásáért felel s gombokat. Az X, Y, Z tengelyek körüli forgatásra vonatkozik a gráf megjegyzése alatt található hat nyomógomb. A szerkesztési mez ben megadható szám jelzi, hogy egy kattintásra hány fokot fordul el a gráf. A piros bal és jobb nyíl egy el re beállított ’u’ tengely körül forgatja a gráfot egy fokonként. A kis földgömbre kattintva automatiusan két tengely körül forogni fog a gráfunk (X és U tengely körül). A „Refresh” gomb bármikor hasznos lehet, ha úgy érzékeljük, hogy a módosításunk nem látható jelenleg még a gráfon. Ha a „Refresh” (frissítés) hatására sem jelentkezik a változás, akkor a hibát máshol keressük. 4.3.5 - Új gráf pont felvétele Az [Edit|Add new junction (graph point)] menüpontra kattintva tudunk az aktuális gráfunkhoz új csomópontot felvenni. Itt kell beállítanunk mindent, ami a gráf ponttal kapcsolatos (17. ábra).

31/67

BUDAPESTI M


SZAKI F ISKOLA

17. ábra: Új gráf pont hozzáadása A pont koordinátáinak (coordinates) (X,Y,Z) felvétele történhet manuálisan, de van lehet ség az (X,Y) sík vizuális megadására is a ’#’ gombra kattintva (18. ábra) Az itt megjelen pontok a már felvitt gráf pontokat jelképezik a könnyebb tájolás érdekében!.

32/67

BUDAPESTI M


SZAKI F ISKOLA

18. ábra: Koordináta grafikus beállítása A sorszám (serial) mez automatikusan generálódik, szerkeszteni nem tudjuk, azonban adhatunk egy egyedi azonosítót (nevet) a csomópontnak (name), amennyiben ezt engedélyezzük (Allow name). Már említettem, hogy minden ponthoz tartozik egy 3D-s objektum, mely grafikusan fogja jelölni a képen a csomópontot. Ezt a ’Design’ panelen tudjuk beállítani. A piros bal és jobb irányú nyilakkal tudunk váltani az elérhet minták között (shape). Ilyen mintákat manuálisan bárki képes készíteni (*.shp file-ok). A program kés bbi verziójában lesz lehet ség program szinten is minták létrehozására. A gráf pont színét a színes téglalapra kattintva tudjuk beállítani.

33/67

BUDAPESTI M


SZAKI F ISKOLA

Minden gráf pont tartalmazhatja azon adatokat, melyek a gráf tulajdonságai között definiálva vannak. A bal oldali listában (Data of graph point) kiválasztva az adott elemet, majd az szerkesztési mez be egy értéket írva (Value), végül a ’Set’ gombra kattintva az adott csomópontnak felvittük az új adatát. A jobb oldali listában láthatjuk a beállított értékeket. Kezdetben ezek a gráf tulajdonságai között beállított alapértelmezett értékek lesznek (Default value). 4.3.6 - Új él felvétele a gráfba Miután felvittünk pár csomópontot a gráfunkba, felmerülhet az igény élek elhelyezésére is ([Edit|Add bew edge])(19. ábra). Egy gráfban él csak két csomópont között mehet. Ezt a két pontot a ’List of points’ gombokra kattintva tudjuk megadni (20. ábra). Irányítatlan gráf esetén lényegtelen, hogy melyik az egyes, és melyik a kettes pont, ellenben irányított esetben a ’Directivity’ részben ennek szerepe van! Amennyiben egy irányított élnek nem állítunk be irányítottságot (none), akkor ez olyan lesz, mintha lenne egy él A-ból B-be, és Bl A-ba is.

19. ábra: Új él felvitele A sorszám (Serial), az egyedi azonosító (name, Allow name) és a szín megadása hasonlóan történik, mint a gráf pontjai esetén. A súlyvektort a gráf súlyvektor tulajdonsága alapján tudjuk feltölteni szintén még ebben az ablakban.

34/67

BUDAPESTI M


SZAKI F ISKOLA

20. ábra: Gráf pont kiválasztása 4.3.7 - Gráf pontok és élek módosítása illetve törlése Utólag lehet ségünk van a felvitt gráf pontok és élek teljes szerkesztésére, és törlésére is ([Edit|Edit junction][Edit|Edit edge][Edit|Delete juction (with edges)][Edit|Delete edge]). Mindegyik esetben egy listából ki kell választanunk, melyik elemmel szeretnénk dolgozni. Grafikus kijelölésre itt még nincs lehet ség. Él esetén segédinformációként kiválasztáskor megjelenik az általa összekötött csomópontok sorszáma és neve is (21. ábra)

21. ábra: Él kiválasztása

35/67

BUDAPESTI M


SZAKI F ISKOLA

A törlés logikai, azaz fizikailag az adott csomópont illetve él nem törl dik a gráfból, csak a felhasználó többé már se látni, se szerkeszteni nem tudja. A program jelenlegi verziójában a fizikai törlés még nem készült el. 4.3.8 - Gráf tulajdonságainak utólagos beállítási lehet sége Ha utólag rájöttünk, hogy a gráfunk tulajdonságai nem a legoptimálisabbak feladatunk megoldására, néhány dolgot a [Data|Display data of graph] menüpont alatt át tudunk állítani (22. ábra).

22. ábra: A gráf tulajdonságai Adhatunk új nevet a gráfnak (gyakorlatilag így lehet elmenteni más néven a gráfot), megjegyzést és típust! A típus változásával óvatosan bánjunk, számos információt veszíthetünk általa. A csomópont adatvektorát, valamint a súlyvektort is tetszés szerint módosíthatjuk. 4.3.9 - Az aktuális súly illetve gráf pont adat beállítása Egyszerre nem jeleníthetünk meg egy élen több információt, avagy egy csomópontban több adatot. Amennyiben a [Setting|Show information on graph] menüpontban az adat- illetve súlyvektor megjelenítését jelöltük be, akkor megadhatunk egy aktuális adatot, és egy aktuális súlyt, mely a gráfon grafikailag is látszani fog. Ezt a [Format|Set current weight] menüpontban illetve a [Format|Set current data] menüpontban tehetjük meg (23. ábra).

36/67

BUDAPESTI M


SZAKI F ISKOLA

23. ábra: Aktuális súly beállítása 4.3.10 - Gráf mentése A programban nincs automatikus mentés, és figyelmeztetni sem figyelmeztet mentésre (a jelenlegi verzió). A [File|Save graph] menüpontra kattintva a beállított gráf könyvtárba a megadott gráf névvel egy könyvtár jön létre, benne számos file-lal, melyek a gráfunk különböz adatait tárolják. Ha másodszor is elmentjük a programot azonos névvel, akkor a program figyelmeztet arra, hogy az el állapot el fog veszni. A gráf átnevezésével (4.3.8 fejezet) ez a probléma elkerülhet . 4.3.11 - Kapcsolatmátrix generálása Számos ábrázolási formája létezik a gráfoknak. Amit a Graphs and spanning trees valósít meg, az egy teljesen egyedi TGraph nev osztályon alapul. Lényegesen több információt képes tárolni ez a szerkezet, mint mondjuk egy hagyományos kapcsolatmátrix, bár tény, hogy maga a TGraph osztály megvalósítható lenne úgy is, hogy alapja egy kapcsolatmátrix! Ellenben egészen máshogy épül fel a TGraph osztály, melynek azonban része egyetlen statikus kapcsolatmátrix is. Az egyetlenen azért van hangsúly, mert minimum annyi mátrix kellene, amennyi súlyunk létezik. Mi itt generálni vagyunk képesek kapcsolatmátrixot egyetlen súly (vagy opcionálisan más adat) alapján a [Data|Static relation matrix] menüpontra kattintva (24. ábra).

37/67

BUDAPESTI M


SZAKI F ISKOLA

24. ábra: Statikus kapcsolatmátrix generálása A két legördül lista segítségével be tudjuk állítani, hogy a gráf pontok sorszáma (Show serial of points), vagy a neve jelenjen-e meg (Show name of points if allow). Ha nem állítottunk be egy csúcspontnál nevet, akkor a sorszáma fog megjelenni. A másik legördül listában szintén kiválasztható, hogy mely súly értékei jelenjenek meg a kapcsolatmátrixban. S t, megadható az is, hogy az élek sorszáma jelenjen meg, avagy a nevük! Természetesen ezen utóbbi esettel számolni nem tudunk, csupán egy nézetet biztosíthat számunkra, melyet a program kés bbi verziójában majd ki fogunk tudni használni, ott ugyanis lehet ség lesz a kapcsolatmátrix szerkesztésével módosítani a gráf adatait! Bezárva az ablakot (OK gombra kattintva) kapunk egy visszajelzést, hogy a gráf kapcsolatmátrixa elkészült-e! Mivel ezzel a kés bbiekben számolni fogunk, ezért nem készül kapcsolatmátrix hogyha nem valós számok szerepelnek a súly értékei között. Az elkészült kapcsolatmátrix ellen rizhet a [Pathfinding|Show relation matrix] menüpontra kattintva (25. ábra).

38/67

BUDAPESTI M


SZAKI F ISKOLA

25. ábra: A kapcsolatmátrix 4.3.12 - Legrövidebb út meghatározása Dijkstra algoritmusa alapján Ha elkészítettünk egy kapcsolatmátrixot, lehet ségünk van legrövidebb út keresésére. A program jelenlegi változatában Dijkstra algoritmusát implementáltam. A [Pathfinding|Simple pathfinding] menüpontra kattintva (26. ábra) a kiindulási (Start point) és a cél pontot (Destination Point) lehet megadni az útkeres algoritmusnak („Set” gomb segítségével), valamint be kell állítanunk, hogy az útkeresés során használja a már memóriában lév kapcsolatmátrixunkat.

39/67

BUDAPESTI M


SZAKI F ISKOLA

26. ábra: Útkeresés kapcsoaltmárix segítségével A ’GO’ gombra kattintva az út (természetesen amennyiben létezik) elkészül. Az ehhez szükséges eredmény adatszerkezet megjelenik a szövegterületben (innen az algoritmus ismeretében számos plusz információ is leolvasható). Bezárva az ablakot (’OK’ gombbal) a gráfunkon a megtalált út a beállított színnel meg fog jelenni (27. ábra).

40/67

BUDAPESTI M


SZAKI F ISKOLA

27. ábra: Legrövidebb út A és C pont között Ezzel a rövid bemutatóval végig is szaladtunk a program legalapvet bb funkcióin, azonban a program nem csak ennyit tud! 4.3.13 – Szerkesztés gyorsítása A legnagyobb probléma gráfok szerkesztése során az adatfelvitel. Ha nagy gráfot szeretnénk készíteni, nagyon sok id re van szükség, míg minden egyes gráf pontot felviszünk, és minden egyes ezekhez tartozó élet. A gyakorlatban azonban ezen pontok és élek tulajdonságainak nagyon nagy része megegyezhet. Ennek érdekében készültek a programhoz olyan szerkeszt k, melyek pontok és élek egyidej felvitelét teszik lehet vé az el bbi módszerhez viszonyítva rendkívüli sebességgel! Ez azt jelenti, hogy egy pár száz gráf pontból és pár száz élb l elkészített gráf háló negyed óra alatt elkészítehet ! Válasszuk ki az [Edit|Junctions and Edges Editor] elnevezés menüpontot (28. ábra).

41/67

BUDAPESTI M


SZAKI F ISKOLA

28. ábra: Él és pont szerkeszt Ez a menüpont sokkal többet tud, mint amit els ránézésre gondolnánk! A bal fels sarokban beállíthatjuk, hogy mit szeretnénk felvenni (Junctiont, azaz pontot, Edge-t, azaz élet), illetve hogy szeretnénk e grafikusan szerkeszteni a már felvitt elemeket (Edit mode)! Alatta kiválaszthatjuk, hogy a majd felvitt gráf pontok milyen grafikai formát öntsenek, illetve milyen szín ek legyenek (a szín élekre is vontkozik). Az „Edges and Junctions Data” résznél megadhatjuk a következ felviend gráf pont, illetve él 3D-s Z koordinátáját (az X és Y koordinátákat grafikusan tudjuk majd beállítani!), valamint megadhatjuk az elem nevét is. Láthatunk két kijelöl négyzetet is. Ha az Edges mellett pipa van, az azt jelenti, hogy az ábrán az élek látszani fognak. Ugyanígy ha a Serials mellett is pipa van, akkor a gráf pontok sorszáma fog látszódni a 3D-s gráf vetületi képén! A Step mez vel az érzékenységet tudjuk beállítani. Ez majd arra lesz jó, hogy egyes pontokat azonosítsunk. Válasszuk ki legel ször a bal fels sarokban az új gráf pont felvételét (Junction). Állítsunk be minden számunkra szükséges információt, majd kattintsunk oda a képen, ami számunkra épp megfelel (itt hívnám fel a figyelmet arra, hogy a képen azon gráf pontok, melyek nagyobbnak t nnek, mint a többiek, velünk egy síkban vannak a Z tengelyt tekintve). A (29. ábra) épp ezt a 42/67

BUDAPESTI M


SZAKI F ISKOLA

folyamatot mutatja. Felvittünk egy új gráf pontot, mely automatikusan megkapta a sorban következ gráf pont sorszámát.

29. ábra: Egy új gráf pont felvétele Ezek után váltsunk át új gráf él felvitelére! Állítsuk be itt is az él színét, esetlegesen a nevét, majd kattintsunk a képen arra a gráf pontra, ahonnan az élünk kiindul, és az egér felengedése nélkül húzzuk oda, ahol az élünk vége lesz. Segítségképpen a bal oldalon látható Serial, X, Y és Z mez k változása jelzi, hogy a kurzor épp melyik koordinátájú gráf pont felett tartózkodik! Ezt a folyamatot a (30. ábra) mutatja be. Ha mindent jól csináltunk, és az élek be rajzolása be van kapcsolva, azonnal meg is jelennek az új éleink!

43/67

BUDAPESTI M


SZAKI F ISKOLA

30. ábra: Új gráf élek felvitele Mindezek után még ugyanezen a képerny n arra is képesek vagyunk, hogy egy gráf pont helyzetén változtassunk a térben! Ehhez válasszuk ki az „Edit mode”-ot, mint m velet a bal fels sarokban, kattintsunk egy tetsz leges gráf pontra a képen, majd a bal fels sarokban id közben megjelent mozgató gombokra kattintva figyeljük meg, ahogyan a gráf pontunk, a hozzá tartozó összes éllel együtt átdefiniálódik! A (31. ábra) épp azt mutatja, hogy a 14-es sorszámú gráf pontot kimozdítom a helyér l.

44/67

BUDAPESTI M


SZAKI F ISKOLA

31. ábra: Gráf pont grafikus mozgatása Az “OK” gombra kattintva az elvégzett m veletek érvényesülnek (32. ábra).

45/67

BUDAPESTI M


SZAKI F ISKOLA

32. ábra: M veletek véglegesítése 4.3.14 – Tömegesen felvett élek és gráf pontok módosítása és törlése A fenti módszer kiegészítéseként az [Edit|Junctions and Edges Multi Editor] menüpontot kiválasztva (33. ábra) lehet ségünk van arra, hogy egy kattintással a középs listába felvett élek és gráf pontok színét, illetve nevét egységesen beállítsuk.

46/67

BUDAPESTI M


SZAKI F ISKOLA

33. ábra: Multi Editor 4.3.15 – Útkeresés egyszer bb formája Ahhoz hogy egy gráfokkal foglalkozó programot hatékonyan tudjuk kezelni, alapvet en szükséges az, hogy tisztában legyünk a gráfok matematikai alapjaival, hogy meg tudjuk mondani, hogy mi is az a kapcsolatmátrix. Ennek ellenére lehet ségünk van arra, hogy ne kelljen kapcsolatmátrixot generálnunk ahhoz, hogy a Dijkstra féle legrövidebb utat meghatározzuk egy adott súlyra nézve! A program képes dinamikusan létrehozni a kapcsolatmátrixnak a számára szükséges részét, így a kapcsolatmátrixot nem szükséges a memóriában tárolni, így elkészíteni sem (34. ábra). Ennek természetesen hátránya a sebesség lesz, de ez pár száz gráf pontot tartalmazó gráfok esetén nem számottev . Ha kapcsolatmátrix nélkül keresünk utat, természetesen meg kell adnunk azt a súlyt is, melyet felhasználva a program dinamikusan kiszámolja majd a szükséges értékeket.

47/67

BUDAPESTI M


SZAKI F ISKOLA

34. ábra: Útkeresés kapcsolatmátrix nélkül Mi az a lépés, mely segítségével még gyorsabbá tehetjük az útkeresést? Természetesen kézenfekv , hogy az út hosszának automatikus megállapításával. Ha például egy térképhez készített gráf pontokat arányosan veszünk fel, avagy egy alakzatot méretarányosan modellezünk (azaz amit látunk, az körülbelül megfelel a valóságnak), akkor a program képes a pontok közötti 3D-s távolság kiszámolására minden egyes pontra nézve (35. ábra).

48/67

BUDAPESTI M


SZAKI F ISKOLA

35. ábra: Súlyok együttes szerkesztése Ugyanitt megtehetjük azt is, hogy egy megadott konstans értéket állítunk be minden él adott súlyára (a súlyt ki kell választani a listából, majd a „Set Constant” avagy a „Set Distance 3D” gombra kell kattintani a kívánt eredmény függvényében). Kés bbi program verzióba bekerülhet olyan lehet ség is, hogy minden egyes súlyra megadott m veletet végrehajt a program (például kett vel való szorzás, stb.).

49/67

BUDAPESTI M


SZAKI F ISKOLA

36. ábra: Képerny kép

4.4 - Fejleszt i dokumentáció 4.4.1 - A programról A Graphs and spanning trees alkalmazás Borland Delphi 7 környezetben készült Pascal/Delphi szintaktikával. Microsoft Windows 32 bites környezet alatt futtatható. Többdokumentumos, úgynevezett MDIApplication, mely lehet vé teszi, hogy egy id ben több gráfon dolgozzunk, és a gráfokat egymástól függetlenül tudjuk kezelni. Jelenleg 23 darab példánya van az alkalmazásnak a TForm osztályból, és három saját készítés osztályt tartalmaz: TQWVWin, TObject3D és TGraph. Az els kett grafikai osztályok. A TQWVWin a gráfok forgatásáért felel s panel grafikáját dolgozza át. Az összes grafikai hatását bekapcsolva a gépet meglehet sen „visszafogja”. A TObject3D osztály egy egyedi szoftveres 3D objektumok tárolásáért, és kezelésért felel s. Részleteivel a 4.4.2-es fejezet foglalkozik. Végül a TGraph osztály maga a gráf, minden adatával és veletével. Erre a 4.4.3 fejezetben térünk ki.

50/67

BUDAPESTI M


SZAKI F ISKOLA

4.4.2 - A TObject3D osztály A Wevi3DUnit tartalmazza els sorban a TObject3D osztály deklarációját, a hozzá tartozó típus deklarációkat, valamint a szükséges konstansokat és változókat. METÓDUS InitObject3D DataInit AddArm AddEdge AddPoint AddPointColor AddPointWithLabel DataStart SetVector3D SetPoint4D SetCoords InitRotateUgamma InitRotXAlpha InitRotYAlpha InitRotZAlpha SetTrans

TÍPUS Eljárás Eljárás Eljárás Eljárás Eljárás Eljárás Eljárás Eljárás Függvény Függvény Függvény Eljárás Eljárás Eljárás Eljárás Függvény

SetNegativMatrix SetInvTrans SetTransponalt Multiplication3x1_3x3 Multiplication4x1_4x4Single Multiplication4x1_4x4 Multiplication4x1_4x4Coords DrawObject MoveManipulator

Függvény Függvény Függvény Függvény Függvény Függvény Függvény Eljárás Eljárás

GetVectorLength SetNormalVector

Függvény Függvény

LEÍRÁS Inicializálja a példányt. Inicializálja a példány pontjait, és éleit. Egy elemet ad hozzá a példányhoz. Egy élet ad hozzá egy adott elemhez. Egy pontot ad hozzá egy adott elemhez. Egy pont színét adja hozzá egy adott ponthoz. Egy pontot ad hozzá az elemhez felirattal együtt. Rögzíti az adatbevitelét egy elemnek. Egy TVector3D típusú változó értékeit állítja be. Egy TPoint4D típusú változó értékeit állítja be. A koordináta tengelyeket állítja be. Az U tengely körüli forgatás mátrixát állítja be. Az X tengely körüli forgatás mátrixát állítja be. Az Y tengely körüli forgatás mátrixát állítja be. Az Z tengely körüli forgatás mátrixát állítja be. Három tengely és egy eltolás alapján egy TTrans típusú változó értékeit állítja be. Negál egy mátrixot. Invertál egy mátrixot. Transzponál egy mátrixot. Mátrixokat szoroz (3x1_3x3). Mátrixokat szoroz (4x1_4x4). Mátrixokat szoroz (4x1_4x4). Mátrixokat szoroz (4x1_4x4). Kirajzolja a példányban tárolt elemeket. Forgatja a beállított értékek alapján a példány elemeit. Visszaadja egy TVector3D típusú változó hozzsát. Meghatározza egy TVector3D típusú változó normálvektorát.

Konstansok CONST MAXPOINTS MAXEDGES MAXARMS ACCURACY

= = = =

500; 1000; 3; 0.001;

A MAXPOINTS határozza meg, hogy maximálisan mennyi grafikai pont lehet az ábrán. A program ezen része is teljesen statikus m ködésre van felkészítve, a kés bbi programverziók legfontosabb lépése a dinamikus tárolás megvalósítása lesz.

51/67

BUDAPESTI M


SZAKI F ISKOLA

A MAXEDGES értelemszer en a maximálisan ábrázolható grafikai élek számát jelenti (már többször említettem, hogy a grafikai élek és pontok száma nem egyezik meg a gráf éleinek és pontjainak számával). A MAXARMS egy bels konstans, mely korlátozásával (3 a legkisebb értéke) a TObject3D osztály egy lényeges funkcióját elérhetetlenné tesszük. Képes lenne az osztály több elem tárolására (mindegyiket külön lokális koordinátarendszerben), és ezen elemeket egy osztálypéldány tagjaiként egymáshoz képest mozgatni, forgatni tudnánk. EZ a MAXARMS határozza meg, hogy mennyi ilyen elem tárolható egy példányban. Az 1. elem nem tényleges elem, itt nem tárolhatunk adatot. Ez a bázis koordinátarendszert határozza meg. A 2.-ban tároljuk a tárgyainkat, és ennek biztonságos kezeléséhez (mutatók elérik még a következ elemet is) szükséges még egy elem. Ezért 3 az értéke minimálisan a MAXARMS-nak. Az ACCURANCY egy pontosság érték. Két valós számot az osztály már egyenl nek tekint, ha ezen értéknél kisebb a különbség közöttük. Típusok TYPE (*** T3DObjects ***) TTrans = Array [1..4,1..4] Of Double; TVector3D = Array [1..3] Of Double; TPoint4D = Array [1..4] Of Double; TCoords = Array [1..3] Of TPoint4D; TPoints = Array [1..MAXPOINTS] Of TPoint4D; TPointsColor = Array [1..MAXPOINTS,1..3] Of Byte; TPointsLabel = Array [1..MAXPOINTS,1..2] Of ShortString; TEdges = Array [1..MAXEDGES,1..5] Of Integer; TMatrix3x3 = Array [1..3] Of TVector3D; TData = Record Active : Boolean; Prev : Byte; Next : Byte; Coords : TCoords; Offset : TVector3D; PointsDB : Integer; Points : TPoints; EdgesDB : Integer; Edges : TEdges; ResultPoints : TPoints; PointsLabel : TPointsLabel; PointsColor : TPointsColor; End; TDataArray = Array [1..MAXARMS] Of TData;

A TTrans mátrix tartalmazza a transzformációs m veleteket (forgatás, eltolás, stb.). A TVector3D egy 3D-s vektor avagy egy pont tárolására alkalmas. A TPoint4D ehhez hasonlósan a homogén koordinátás alakban képes ugyanerre. A TCoords a koordinátatengelyek homogén koordinátás alakjait tárolja. A TPoints tömbben találhatók a grafikus pontok, a TEdges tömbben pedig a grafikus élek adatai. A TPointsColor minden pontra tárolja a színét, a TPointsLabel pedig egy 52/67

BUDAPESTI M


SZAKI F ISKOLA

feliratot, mely szintén megjelenhet, ha a beállítások ezt engedik. A TMatrix3x3 egy 3D-s környezetben tárolt mátrix. A TDataArray tárolja az egyes elemek (amib l a Graphs and spanning trees csak ténylegesen egyet használ) adatait. Változók VAR TextFont BACKGROUND DefaultColor TEXTOVERWRITE VISI_SERIALOFPOINTS VISI_NAMEOFPOINTS VISI_SERIALOFEDGES VISI_NAMEOFEDGES VISI_WEIGHT VISI_COLORS VISI_DATUM SerialOfPointsColor NameOfPointsColor SerialOfEdgesColor NameOfEdgesColor WeightColor DatumColor

: : : : : : : : : : : : : : : : :

TFont; TColor; TColor; Boolean; Boolean; Boolean; Boolean; Boolean; Boolean; Boolean; Boolean; TColor; TColor; TColor; TColor; TColor; TColor;

A változók az egyes feliratok láthatóságát, illetve színét állítják be. A TEXTOVERWRITE igaz értéke esetén a feliratok háttere átlátszó lesz. Így bár több információ lesz az ábrán, ám ezek kevésbé leolvasható formában. Az osztály TObject3D = Class (TObject) Data : TDataArray; // Az objektumok adatai OX : Integer; // Origó X koordinátája OY : Integer; // Origó Y koordinátája RotateUgamma : TTrans; // Tetsz leges U tengely körüli forgatás mátrixa (gamma szöggel) u : TPoint4D; // Az u tenngely gamma : Double; // A gamma szög (radián) Act : Byte; // Az aktuális kar. RotXAlpha : TTrans; // Az X tengely körüli forgatás mátrixa RotYAlpha : TTrans; // Az Y tengely körüli forgatás mátrixa RotZAlpha : TTrans; // Az Z tengely körüli forgatás mátrixa alpha : Double; // A X, Y, Z tengely körüli forgatás szöge. PROCEDURE InitObject3D ( KX : Integer; KY : Integer ); PROCEDURE DataInit; PROCEDURE AddArm ( num : Byte; prev : Byte; next : Byte; coords : TCoords; offset : TVector3D ); PROCEDURE AddEdge ( num : Byte; p1 : Integer; p2 : Integer; ColorR : Byte; ColorG : Byte; ColorB : Byte ); PROCEDURE AddPoint ( num : Byte; pointDB : Byte; x : Double; y : Double;

53/67

BUDAPESTI M

Gráf szimuláció az oktatásban z ( num pointDB R G B

PROCEDURE AddPointColor

PROCEDURE AddPointWithLabel

( num pointDB x y z PLabel PLabelType ( num

: : : : : :

SZAKI F ISKOLA

Double ); Byte; Byte; Byte; Byte; Byte );

: : : : : : :

Byte; Byte; Double; Double; Double; ShortString; ShortString ); PROCEDURE DataStart : Byte ); FUNCTION SetVector3D ( x : Double; y : Double; z : Double ) : TVector3D; FUNCTION SetPoint4D ( x : Double; y : Double; z : Double; h : Double ) : TPoint4D; FUNCTION SetCoords ( X : TPoint4D; Y : TPoint4D; Z : TPoint4D ) : TCoords; PROCEDURE InitRotateUgamma ( v : TPoint4D; rad : Double ); PROCEDURE InitRotXAlpha ( rad : Double ); PROCEDURE InitRotYAlpha ( rad : Double ); PROCEDURE InitRotZAlpha ( rad : Double ); FUNCTION SetTrans ( Coords : TCoords; Offset : TVector3D ) : TTrans; FUNCTION SetNegativMatrix ( Matrix : TMatrix3x3 ) : TMatrix3x3; FUNCTION SetInvTrans ( Coords : TCoords; Offset : TVector3D ) : TTrans; FUNCTION SetTransponalt ( TT : TMatrix3x3 ) : TMatrix3x3; FUNCTION Multiplication3x1_3x3 ( Matrix : TMatrix3x3; v : TVector3D ) : TVector3D; FUNCTION Multiplication4x1_4x4Single ( Matrix : TTrans; v : TPoint4D ): TPoint4D; FUNCTION Multiplication4x1_4x4 ( v : TPoints; Matrix : TTrans; PointsDB : Integer ) : TPoints; FUNCTION Multiplication4x1_4x4Coords ( v : TCoords; Matrix : TTrans ) : TCoords; PROCEDURE DrawObject ( ManipulatorImage : TImage; Original : Boolean; PointsOrEdgesDraw : Char ); PROCEDURE MoveManipulator ( ManipulatorImage : TImage; CLRSCR : Boolean; PointsOrEdgesDraw : Char ); FUNCTION GetVectorLength ( A : TVector3D ) : Double; FUNCTION SetNormalVector ( A : TVector3D; B : TVector3D ) : TVector3D; End;

4.4.3 - A TGraph osztály A TypeUnit része többek között a TGraph osztály is, de itt megtalálható számos, a Graphs and spanning trees-ben használt további típusok deklarálása is. METÓDUS InitGraph AddItemRecArray

TÍPUS Eljárás Eljárás

AddPoint

Eljárás

LEÍRÁS Inicializálja a gráfot. Egy elemet hozzáad egy TRecArray típusú vektorhoz. Egy gráf pontot hozzáad a gráfhoz.

54/67

BUDAPESTI M

Gráf szimuláció az oktatásban DeletePoint EditPoint AddEdge DeleteEdge EditEdge Draw PathfindingDijkstra DijkstraNeighbours DijkstraMinimum InitEdgeWay

Eljárás Eljárás Eljárás Eljárás Eljárás Eljárás Eljárás Eljárás Függvény Eljárás

SearchEdge

Függvény

SZAKI F ISKOLA

Egy élet hozzáad a gráfhoz. Szerkeszt egy gráf pontot. Szerkeszt egy élet a gráfban. Logikailag töröl egy élet a gráfból. Logikailag töröl egy gráf pontot. Kirajzolja a gráfot. Dijkstra legrövidebb út keres algoritmusa. Dijkstra algoritmusához szükséges. Dijkstra algoritmusához szükséges. Törli (inicializálja) a megtalált utat (nem lesz kijelölt út). Két pont közötti él sorszámát adja vissza, amennyiben létezik.

Algoritmusok A Draw() és a PathfindingDijkstra() algoritmusa kulcsfontosságú az osztály szempontjából, így ezek forráskódját teljes terjedelmében közlöm. Dijkstra algoritmusának pszeudó kódja már szerepelt az irodalomkutatásban is. Most nézzük meg Delphi 7 forrását. PROCEDURE TGraph.PathfindingDijkstra ( ); Var

StartPoint DestinationPoint Var PFArray

: Word; : Word; : TPFArray

i : Integer; act : Word; Begin For i:=1 To (PointsNum) Do Begin PFArray[i].Length:=High(Integer); PFArray[i].Prev:=0; PFArray[i].Status:=FALSE; End; act:=StartPoint; PFArray[act].Length:=0; PFArray[act].Status:=TRUE; REPEAT DijkstraNeighbours(PFArray,act); act:=DijkstraMinimum(PFArray); PFArray[act].Status:=TRUE; UNTIL (act=DestinationPoint); End; PROCEDURE TGraph.DijkstraNeighbours ( Var 55/67

Var PFArray act

: TPFArray; : Word );

BUDAPESTI M


SZAKI F ISKOLA

i : Integer; Begin For i:=1 To (PointsNum) Do Begin If (RelationMatrix[act,i]<>0) And (Not(PFArray[i].Status)) Then Begin If (PFArray[act].Length+RelationMatrix[act,i])<(PFArray[i].Length) Then Begin PFArray[i].Prev:=act; PFArray[i].Length:=PFArray[act].Length+RelationMatrix[act,i]; End; End; End; End; FUNCTION TGraph.DijkstraMinimum ( PFArray : TPFArray ) : Word; Var min : Double; minH : Integer; i : Integer; find : Boolean; j : Integer; Begin find:=FALSE; i:=0; REPEAT Inc(i); If (Not(PFArray[i].Status)) Then Begin min:=PFArray[i].Length; minH:=i; find:=TRUE; End; UNTIL (find); If (find) Then Begin For j:=i To (PointsNum) Do Begin If (min>PFArray[j].Length) And (Not(PFArray[j].Status)) Then Begin min:=PFArray[j].Length; minH:=j; End; End; End; If (find) Then Begin Result:=minH; End Else Begin 56/67

BUDAPESTI M


SZAKI F ISKOLA

Result:=0; End; End; PROCEDURE TGraph.Draw( Image : TImage ); Var I : Integer; TF : TextFile; Num : Integer; X : Integer; Y : Integer; Z : Integer; Numglobal : Word; AidePair : TPair; PairNum : Byte; Line : ShortString; Numglobalinfo : Word; SX : Integer; SY : Integer; SZ : Integer; Sdiv : Integer; A : TVector3D; B : TVector3D; IV : TVector3D; NV : TVector3D; Scolor : TColor; BEGIN ShowPoints.Free; ShowPoints:=TObject3D.Create; ShowPoints.InitObject3D(MaxXY Div 2,MaxXY Div 2); ShowPoints.DataInit; ShowInfo.Free; ShowInfo:=TObject3D.Create; ShowInfo.InitObject3D(MaxXY Div 2,MaxXY Div 2); ShowInfo.DataInit; ShowPoints.AddArm(1,0,2,ShowPoints.SetCoords(ShowPoints.SetPoint4D(1,0,0,1),ShowPoints. SetPoint4D(0,1,0,1),ShowPoints.SetPoint4D(0,0,1,1)),ShowPoints.SetVector3D(0,0,0)); ShowPoints.AddPoint(1,1,0,0,0); ShowPoints.DataStart(1); ShowPoints.AddArm(2,1,0,ShowPoints.SetCoords(ShowPoints.SetPoint4D(1,0,0,1),ShowPo ints.SetPoint4D(0,1,0,1),ShowPoints.SetPoint4D(0,0,1,1)),ShowPoints.SetVector3D(0,0,10)); ShowInfo.AddArm(1,0,2,ShowInfo.SetCoords(ShowInfo.SetPoint4D(1,0,0,1),ShowInfo.SetPoint 4D(0,1,0,1),ShowInfo.SetPoint4D(0,0,1,1)),ShowInfo.SetVector3D(0,0,0)); ShowInfo.AddPoint(1,1,0,0,0); ShowInfo.DataStart(1); ShowInfo.AddArm(2,1,0,ShowInfo.SetCoords(ShowInfo.SetPoint4D(1,0,0,1),ShowInfo.SetPoint 4D(0,1,0,1),ShowInfo.SetPoint4D(0,0,1,1)),ShowInfo.SetVector3D(0,0,10)); numglobal:=0; numglobalinfo:=0; For i:=1 To (PointsNum) Do Begin If (PointsArray[i].Enable) Then Begin AssignFile(TF,SHAPEDIRECTORY+PointsArray[i].Shape);

57/67

BUDAPESTI M


SZAKI F ISKOLA

{$I-} ReSet(TF); {$I+} If (IoResult<>0) Then Begin ShowMessage('There was some error during shape file opening.'); Halt; End; Line:=''; If (VISI_SERIALOFPOINTS) Then Begin Line:=IntToStr(PointsArray[i].Serial); End; If (VISI_NAMEOFPOINTS) And (PointsArray[i].AllowName) Then Begin Line:=PointsArray[i].Name; End; If (VISI_DATUM) And (CurrentDatum<>0) Then Begin Line:=PointsArray[i].DataArray[CurrentDatum]; End; If (VISI_SERIALOFPOINTS) Or (VISI_NAMEOFPOINTS) Or (VISI_DATUM) Then Begin Inc(numglobalinfo); ShowInfo.AddPointWithLabel(2,numglobalinfo,PointsArray[i].X,PointsArray[i].Y, PointsArray[i].Z,Line,'Point'); End; ReadLn(TF,Line); ReadLn(TF,num,X,Y,Z); InitPair(AidePair,PairNum); While (Not(EoF(TF))) And (num<>0) Do Begin Inc(numglobal); ShowPoints.AddPoint(2,numglobal,PointsArray[i].X+X,PointsArray[i].Y+Y,Points Array[i].Z+Z); Inc(PairNum); AidePair[PairNum,1]:=num; AidePair[PairNum,2]:=numglobal; ReadLn(TF,num,X,Y,Z); End; While (Not(EoF(TF))) Do Begin ReadLn(TF,X,Y); X:=SearchPair(AidePair,X); Y:=SearchPair(AidePair,Y); ShowPoints.AddEdge(2,X,Y,GetRValue(PointsArray[i].Color),GetGValue(PointsAr ray[i].Color),GetBValue(PointsArray[i].Color)); End; Close(TF); End; End; For i:=1 To (EdgesNum) Do Begin If (EdgesArray[i].Enable) Then Begin Line:=''; If (VISI_SERIALOFEDGES) Then Begin Line:=IntToStr(EdgesArray[i].Serial); End;

58/67

BUDAPESTI M


SZAKI F ISKOLA

If (VISI_NAMEOFEDGES) And (EdgesArray[i].AllowName) Then Begin Line:=EdgesArray[i].Name; End; If (VISI_WEIGHT) And (CurrentWeight<>0) Then Begin Line:=EdgesArray[i].WeightsArray[CurrentWeight]; End; If (VISI_NAMEOFEDGES) Or (VISI_SERIALOFEDGES) Or (VISI_WEIGHT) Then Begin Inc(numglobalinfo); ShowInfo.AddPointWithLabel(2,numglobalinfo,(PointsArray[EdgesArray[i].Point One].X + PointsArray[EdgesArray[i].PointTwo].X)/2,(PointsArray[EdgesArray[i].Point One].Y + PointsArray[EdgesArray[i].PointTwo].Y)/2,(PointsArray[EdgesArray[i].Point One].Z +PointsArray[EdgesArray[i].PointTwo].Z)/2,Line,'Edge'); End; Inc(numglobal); ShowPoints.AddPoint(2,numglobal,PointsArray[EdgesArray[i].PointOne].X,PointsArr ay[EdgesArray[i].PointOne].Y,PointsArray[EdgesArray[i].PointOne].Z); Inc(numglobal); ShowPoints.AddPoint(2,numglobal,PointsArray[EdgesArray[i].PointTwo].X,PointsArr ay[EdgesArray[i].PointTwo].Y,PointsArray[EdgesArray[i].PointTwo].Z); If (EdgesArray[i].IsWay) Then Begin SColor:=WayColor; End Else Begin SColor:=EdgesArray[i].Color; End; ShowPoints.AddEdge(2,numglobal1,numglobal,GetRValue(SColor),GetGValue(SColor),GetBValue(SColor)); If (EdgesArray[i].Directivity=1) Then Begin A:=ShowPoints.SetVector3D(PointsArray[EdgesArray[i].PointOne].X,PointsArray[ EdgesArray[i].PointOne].Y,PointsArray[EdgesArray[i].PointOne].Z); B:=ShowPoints.SetVector3D(PointsArray[EdgesArray[i].PointTwo].X,PointsArray[ EdgesArray[i].PointTwo].Y,PointsArray[EdgesArray[i].PointTwo].Z); IV:=ShowPoints.SetNormalVector(A,B); NV:=ShowPoints.SetVector3D(IV[3],-IV[1],IV[2]); Inc(numglobal); ShowPoints.AddPoint(2,numglobal,PointsArray[EdgesArray[i].PointOne].X+IV[1]* DirectivityLength+NV[1]*DirectivityLength2,PointsArray[EdgesArray[i].Point One].Y+IV[2]*DirectivityLength+NV[2]*DirectivityLength2,PointsArray[Edges Array[i].PointOne].Z+IV[3]*DirectivityLength+NV[3]*DirectivityLength2); ShowPoints.AddEdge(2,numglobal,numglobal2,GetRValue(SColor),GetGValue(SColor),GetBValue(SColor)); Inc(numglobal); ShowPoints.AddPoint(2,numglobal,PointsArray[EdgesArray[i].PointOne].X+IV[1]* DirectivityLengthNV[1]*DirectivityLength2,PointsArray[EdgesArray[i].PointOne].Y+IV[2]*Direc tivityLengthNV[2]*DirectivityLength2,PointsArray[EdgesArray[i].PointOne].Z+IV[3]*Direc tivityLength-NV[3]*DirectivityLength2); ShowPoints.AddEdge(2,numglobal,numglobal3,GetRValue(SColor),GetGValue(SColor),GetBValue(SColor));

59/67

BUDAPESTI M


SZAKI F ISKOLA

NV:=ShowPoints.SetVector3D(-IV[2],-IV[3],IV[1]); Inc(numglobal); ShowPoints.AddPoint(2,numglobal,PointsArray[EdgesArray[i].PointOne].X+IV[1]* DirectivityLength+NV[1]*DirectivityLength2,PointsArray[EdgesArray[i].Point One].Y+IV[2]*DirectivityLength+NV[2]*DirectivityLength2,PointsArray[Edges Array[i].PointOne].Z+IV[3]*DirectivityLength+NV[3]*DirectivityLength2); ShowPoints.AddEdge(2,numglobal,numglobal4,GetRValue(SColor),GetGValue(SColor),GetBValue(SColor)); Inc(numglobal); ShowPoints.AddPoint(2,numglobal,PointsArray[EdgesArray[i].PointOne].X+IV[1]* DirectivityLengthNV[1]*DirectivityLength2,PointsArray[EdgesArray[i].PointOne].Y+IV[2]*Direc tivityLengthNV[2]*DirectivityLength2,PointsArray[EdgesArray[i].PointOne].Z+IV[3]*Direc tivityLength-NV[3]*DirectivityLength2); ShowPoints.AddEdge(2,numglobal,numglobal5,GetRValue(SColor),GetGValue(SColor),GetBValue(SColor)); ShowPoints.AddEdge(2,numglobal,numglobal2,GetRValue(SColor),GetGValue(SColor),GetBValue(SColor)); ShowPoints.AddEdge(2,numglobal-2,numglobal1,GetRValue(SColor),GetGValue(SColor),GetBValue(SColor)); ShowPoints.AddEdge(2,numglobal-1,numglobal3,GetRValue(SColor),GetGValue(SColor),GetBValue(SColor)); ShowPoints.AddEdge(2,numglobal3,numglobal,GetRValue(SColor),GetGValue(SColor),GetBValue(SColor)); End; If (EdgesArray[i].Directivity=2) Then Begin A:=ShowPoints.SetVector3D(PointsArray[EdgesArray[i].PointOne].X,PointsArray[ EdgesArray[i].PointOne].Y,PointsArray[EdgesArray[i].PointOne].Z); B:=ShowPoints.SetVector3D(PointsArray[EdgesArray[i].PointTwo].X,PointsArray[ EdgesArray[i].PointTwo].Y,PointsArray[EdgesArray[i].PointTwo].Z); IV:=ShowPoints.SetNormalVector(A,B); NV:=ShowPoints.SetVector3D(IV[3],-IV[1],IV[2]); Inc(numglobal); ShowPoints.AddPoint(2,numglobal,PointsArray[EdgesArray[i].PointTwo].XIV[1]*DirectivityLength+NV[1]*DirectivityLength2,PointsArray[EdgesArray[i]. PointTwo].YIV[2]*DirectivityLength+NV[2]*DirectivityLength2,PointsArray[EdgesArray[i]. PointTwo].Z-IV[3]*DirectivityLength+NV[3]*DirectivityLength2); ShowPoints.AddEdge(2,numglobal,numglobal1,GetRValue(SColor),GetGValue(SColor),GetBValue(SColor)); Inc(numglobal); ShowPoints.AddPoint(2,numglobal,PointsArray[EdgesArray[i].PointTwo].XIV[1]*DirectivityLengthNV[1]*DirectivityLength2,PointsArray[EdgesArray[i].PointTwo].YIV[2]*DirectivityLengthNV[2]*DirectivityLength2,PointsArray[EdgesArray[i].PointTwo].ZIV[3]*DirectivityLength-NV[3]*DirectivityLength2); ShowPoints.AddEdge(2,numglobal,numglobal2,GetRValue(SColor),GetGValue(SColor),GetBValue(SColor)); NV:=ShowPoints.SetVector3D(-IV[2],-IV[3],IV[1]); Inc(numglobal);

60/67

BUDAPESTI M


SZAKI F ISKOLA

ShowPoints.AddPoint(2,numglobal,PointsArray[EdgesArray[i].PointTwo].XIV[1]*DirectivityLength+NV[1]*DirectivityLength2,PointsArray[EdgesArray[i]. PointTwo].YIV[2]*DirectivityLength+NV[2]*DirectivityLength2,PointsArray[EdgesArray[i]. PointTwo].Z-IV[3]*DirectivityLength+NV[3]*DirectivityLength2); ShowPoints.AddEdge(2,numglobal,numglobal3,GetRValue(SColor),GetGValue(SColor),GetBValue(SColor)); Inc(numglobal); ShowPoints.AddPoint(2,numglobal,PointsArray[EdgesArray[i].PointTwo].XIV[1]*DirectivityLengthNV[1]*DirectivityLength2,PointsArray[EdgesArray[i].PointTwo].YIV[2]*DirectivityLengthNV[2]*DirectivityLength2,PointsArray[EdgesArray[i].PointTwo].ZIV[3]*DirectivityLength-NV[3]*DirectivityLength2); ShowPoints.AddEdge(2,numglobal,numglobal4,GetRValue(SColor),GetGValue(SColor),GetBValue(SColor)); ShowPoints.AddEdge(2,numglobal,numglobal2,GetRValue(SColor),GetGValue(SColor),GetBValue(SColor)); ShowPoints.AddEdge(2,numglobal-2,numglobal1,GetRValue(SColor),GetGValue(SColor),GetBValue(SColor)); ShowPoints.AddEdge(2,numglobal-1,numglobal3,GetRValue(SColor),GetGValue(SColor),GetBValue(SColor)); ShowPoints.AddEdge(2,numglobal3,numglobal,GetRValue(SColor),GetGValue(SColor),GetBValue(SColor)); End; End; End; ShowPoints.DataStart(2); END;

A konstansok CONST MAXITEM MAXGRAPHPOINTS MAXGRAPHEDGES MAXSHAPEPOINTS SHAPELISTFILENAME SHAPEDIRECTORY SAVEDIRECTORY

= = = = = = =

10; 50 100 20; 'shapes.lst'; 'shape/'; 'graphs/';

A MAXITEM határozza meg, hogy statikus esetben egy élen mennyi súly, illetve egy pontban mennyi adat tárolható. A MAXGRAPHPOINTS és a MAXGRAPHEDGES a gráf pontjaira illetve éleire meghatározott statikus korlát. A MAXSHAPEPOINTS meghatározza, hogy egy gráf pont minta 3D-s objektuma maximálisan mennyi grafikai pontból állhat. A SHAPEDIRECTORY és a SAVEDIRECTORY az alapértelmezett könyvtárakat állítja be, míg a SHAPELISTFILENAME a minták listáját tároló file nevét. A változók Var DIRECTIVITYLENGTH

: Byte;

61/67

BUDAPESTI M

Gráf szimuláció az oktatásban DIRECTIVITYLENGTH2 WayColor

SZAKI F ISKOLA

: Byte; : TColor;

A gráf irányítottságát grafikailag jelölni többféleképpen lehet. A DIRECTIVITYLENGTH és a DIRECTIVITYLENGTH2 változók lehet vé teszik, hogy hosszabb, illetve nagyobb nyilakat tudjunk megjeleníteni. A WayColor a megtalált út színét határozza meg. A típusok (*** TGraph ***) TRec

= Record ItemName : ShortString; ItemType : ShortString; DefaultValue : ShortString; End; TGraphDataArray = Array [1..MAXITEM] Of ShortString; TGraphWeightsArray = Array [1..MAXITEM] Of ShortString; TPointRec = Record Enable : Boolean; X : Double; Y : Double; Z : Double; Serial : Word; Name : ShortString; AllowName : Boolean; Shape : ShortString; Color : TColor; DataArray : TGraphDataArray; End; TEdgeRec = Record Enable : Boolean; PointOne : Word; PointTwo : Word; Serial : Word; Name : ShortString; AllowName : Boolean; Color : TColor; Directivity : Byte; WeightsArray : TGraphWeightsArray; IsWay : Boolean; End; TRecArray = Array [1..MAXITEM] Of TRec; TPointsArray = Array [1..MAXGRAPHPOINTS] Of TPointRec; TEdgesArray = Array [1..MAXGRAPHEDGES] Of TEdgeRec; TRelationMatrix = Array [1..MAXGRAPHPOINTS,1..MAXGRAPHPOINTS] Of Double; TPFRec = Record Length : Double; Prev : Word; Status : Boolean; End; TPFArray = Array [1..MAXGRAPHPOINTS] Of TPFRec;

A TRec rekord tárolja a súlyvektor illetve a pontok adatainak tulajdonságait a gráf tulajdonságai között. 62/67

BUDAPESTI M


SZAKI F ISKOLA

A TRecArray vektor tárolja a a TRec típusú elemeket a statikus súlyvektor és gráf pont adatvektor számára. A TGraphDataArray a pontok adatainak statikus vektora szinkronban TRecArray-el. A TGraphWeightsArray a statikus súlyvektor szinkronban TRecArray-el. A TPointRec rekord tárolja egy adott gráf pont tulajdonságait. Az ’Enable’ határozza meg, hogy logikailag törölt-e az elem, avagy sem. Az ’X’,’Y’ és ’Z’ a koordinátáit határozza meg, a ’Serial’ az automatikusan generálódó sorszámát, a ’Name’ a nevét, az ’AllowName’ ennek a létezését. A ’Shape’ az adott grafikai mintát tároló file neve, a ’Color’ pedig a gráf pont színe. A ’DataArray’ tárolja a TGraphDataArray-el szinkronban a gráf csomópontjaiban tárolt adatokat. A TEdgeRec rekord a gráf éleinek tulajdonságait tárolja. Az ’Enable’ itt is a logikai törlöttségre utal, a ’Serial’, ’Name’, ’AllowName’ és ’Color’ szintén azonos jelentéssel bír, mint a gráf pontjai esetén ezt már láttuk. A ’PointOne’ és ’PointTwo’ határozza meg az él által összekötött két pont sorszámát. A ’Directivity’ ennek függvényében az irányítottságot jelölheti. Ha értéke ’0’, akkor nincs irányítottság. Irányított gráf esetében ez azt jelenti, hogy oda-vissza út létezik (ezt a kés bbiekben le lehet majd tiltani, mivel el fordulhat olyan probléma, mely során ezt nem célszer alkalmazni, azonban térkép program esetén a kétsávú utat ezzel tudjuk modellezni)! Az ’IsWay’ logikai változó igaz értéke esetén az adott él egy korábbi útszámítás során az eredmény része volt. Ilyenkor a színe a saját ’Color’ tulajdonsága helyett a ’WayColor’ lesz. A TPointsArray és a TEdgesArray tárolják a pontokat és az éleket statikus esetben. A TRelationMatrix a kapcsolatmátrix típusa. A TPFRec és a TPFArray Dijkstra legrövidebb út keres algoritmusához szükséges. TPArray-ben fog keletkezni az eredmény. Az osztály TGraph

= Class (TObject) public // kesobbiekben private NameOfGraph : ShortString; Comment : ShortString; StorageType : ShortString; TypeOfGraph : ShortString; MultipleEdges : Boolean; Continuous : Boolean; MultipleWeight : Boolean; DataArray : TRecArray; WeightsArray : TRecArray; DANum : Byte; WANum : Byte; MaxXY : Integer; PointsArray : TPointsArray; PointsNum : Word; ShowPoints : TObject3D; EdgesNum : Word; EdgesArray : TEdgesArray; ShowInfo : TObject3D; CurrentWeight : Integer; CurrentDatum : Integer; RelationMatrix : TRelationMatrix;

63/67

BUDAPESTI M


SZAKI F ISKOLA

public PROCEDURE InitGraph; PROCEDURE AddItemRecArray ( Var TRA : TRecArray; Var Num : Byte; ItemName : ShortString; ItemType : ShortString; DefaultValue : ShortString ); PROCEDURE AddPoint ( PointRec : TPointRec ); PROCEDURE DeletePoint ( Serial : Word ); PROCEDURE EditPoint ( PointRec : TPointRec; Serial : Word ); PROCEDURE AddEdge ( EdgeRec : TEdgeRec ); PROCEDURE DeleteEdge ( Serial : Word ); PROCEDURE EditEdge ( EdgeRec : TEdgeRec; Serial : Word ); PROCEDURE Draw ( Image : TImage ); PROCEDURE PathfindingDijkstra ( StartPoint : Word; DestinationPoint : Word; Var PFArray : TPFArray ); PROCEDURE DijkstraNeighbours ( Var PFArray : TPFArray; act : Word ); FUNCTION DijkstraMinimum ( PFArray : TPFArray ) : Word; PROCEDURE InitEdgeWay; FUNCTION SearchEdge ( PointOne : Word; PointTwo : Word ) : Word; End;

4.4.4 – A TypeUnit további részei ALPROGRAM CopyGraph

TÍPUS Eljárás

LoadShapeList LoadShape

Eljárás Eljárás

InitPair SearchPair SaveGraphToFile OpenGraphFromFile

Eljárás Függvény Eljárás Eljárás

LEÍRÁS Egy gráf attribútumait egy másik gráf attribútumaiba másolja. Betölti a minták listáját az adott file-ból. Egy mintát tölt be a TObject3D osztály egy példányába. Inicializálja a segédtömböt. A TPair-hez kapcsolódóan párokat keres. Kimenti a statikus gráfot file-ba. Betölti a statikus gráfot file-ból.

További típusok TPair

= Array [1..MAXSHAPEPOINTS,1..2] Of Word;

A TPair egy segédtömb, mely a gráf pont minták gráfhoz illesztéséhez szükséges. A probléma, melyet meg kellett oldani, hogy egy TObject3D adatmez it (minta) egy másik TObject3D típusba (a gráfba) kellett átmásolni. Ilyenkor a pontok sorszáma megváltozik, de mivel az élek is a pontok eredeti sorszáma alapján tárolódnak, ezért az éleket párosítani kellett a pontokkal. További eljárások illetve függvények PROCEDURE CopyGraph PROCEDURE LoadShapeList PROCEDURE LoadShape PROCEDURE InitPair FUNCTION SearchPair

( Graph1 Var Graph2 ( Var ListBox ( Var Shape FileName ( Var Pair Var Num ( Pair

64/67

: : : : : : : :

TGraph; TGraph ); TListBox ); TObject3D; String ); TPair; Byte ); TPair;

BUDAPESTI M

Gráf szimuláció az oktatásban local PROCEDURE SaveGraphToFile ( FileName PROCEDURE OpenGraphFromFile ( FileName

65/67

SZAKI F ISKOLA

: Byte ) : Word; : ShortString ); : ShortString );

BUDAPESTI M


SZAKI F ISKOLA

5 – TÁRGYSZÓ JEGYZÉK T ÁRGYSZÓ Abt Addinall audiovizuális technika csaturanga e-book Ellington El-Mahaszna esettanulmány Frederiksen G-nyelv gó Griffits harcászati stratégia Hemphil Internet Inverted Pendulum írásvetít játék játékok fejl dése Kersh készség játék Konfucius Kriegspiel Kupisiewicz LabView multimédia Nagy Sándor

Nyirati László oktatási szimuláció oktatástechnológia oktatójáték Percival Pocket PC Poroszország Reid rigid Romiszowski sakk Shubik szerepjáték szimuláció szimulációs játék táblás játék Tablet PC tankönyv Ur városa vezet képzés vietnámi háború

FEJEZET 3.2 3.2 3.2 3.1 3.4 3.2 3.1 3.2 3.2 3.5 3.1 3.2 3.1 3.2 3.4 3.5 3.4 3.2 3.1 3.2 3.2 3.1 3.1 3.3 3.5 3.4 3.3

66/67

3.4 3.2 3.4 3.2 3.2 3.4 3.1 3.2 3.1 3.2 3.1 3.2 3.2 3.2 3.2 3.1 3.4 3.4 3.1 3.2 3.1

BUDAPESTI M


SZAKI F ISKOLA

6 – SZAKIRODALOM ÉS FORRÁSJEGYZÉK 6.1 – Forrásjegyzék (3-I) Murray, H. J. R.: A history of board-games other than chess. The Clarendon press, Oxford, 1952. 12-36. o. (3-II) Novak, Z.: 50 táblás játék. Gondolat Könyvkiadó, Bp., 1982. 92. o (3-III) Gelenczei Emil: A legrégibb magyar sakkemlékek. = Barcza Gedeon: Magyar sakktörténet. Sport, Bp., 1975. 9-11. o. (3-IV) Rockler, J. M.: Applying Simulation/Gaming. On College Teaching. Jossey-Bass Publishers, San Francisco, 1978. 249. o. (3-V) Rockler, M. J: Simulation Games and Furtures Studies. World Future Society Bulletin, 1980. Jan.-Feb. 25. o. (3-VI) Nagy Sándor (1982/b): Oktatástechnológia a neveléstudomány rendszerében. OOK, Veszprém, 18. o (3-VII) Ellington-Addinall-Percival: A handbook of game design. Kogan Page, London, 1982. 11. o., f: 1,1 (3-VIII) Abt, C. C.: Games for learning. = Ellington-Addinall-Percival: i. m. 9. o. (3-IX) Shubik, M.: Games for Society…= Taylor: Guide on simulation and gaming for enviromental education. UNESCO-UNEP, 1983. 8. o. (3-X) Romiszowski, A. J.: Producing Instructional Systems. Kogan Page, London, 1984. 174. o. (3-XI) Nyirati László: A számítógép mint oktatási eszköz (1999)

6.2 – Link gy jtemény http://www.homoludens.hu/htmlm/cik/8031barm.htm http://informatika.kodolanyi.hu/~nyirati/public/aszgazok.htm

67/67

G RÁF SZIMULÁCIÓ AZ OKTATÁSBAN

Recommend Documents