Közlekedési forgalom modellezés

Picture of matematikai alkalmazások

matematikai alkalmazások

Matematikai érdekességek, amelyek jól jöhetnek az érettségin vagy a felvételin is.

Alkalmazások
eca_110_icon

Oszd meg, ha tetszik!

Lesz közlekedési dugó?

Mielőtt megvizsgáljuk, hogy hogyan lehet sejtautomatával modellezni a forgalmat, nézzük át röviden, hogy mik is a sejtautomaták. Egy végtelen négyzetrács minden négyzetében élhet egy sejt. Egy sejt állapota véges sok értéket vehet fel, a legegyszerűbb esetben \(\{1,0\}\). A sejtek állapota lépésenként változik oly módon, hogy egy adott sejt állapota a következő lépésben önmaga és szomszédai állapotától függ. A szabályt, amely leírja, hogy egy sejt egy adott állapotból milyen állapotba kerül, átmenetfüggvénynek nevezzük.
Az elemi sejtautomata egy mindkét irányban végtelen vonalon (számegyenesen) játszódik. A vonal egyes pozícióit (egész számokat) celláknak nevezzük. Egy cella vagy üres, vagy egy élő sejt található benne. Gyakori ábrázolási mód, hogy az üres cellákat fehér, míg az élő sejtet tartalmazó cellákat fekete négyzetek jelölik, így egy kép rajzolható ki az aktuális állapotból.
A jellemző kezdeti állapot az, hogy csupán néhány élő sejt van. Ezután minden körben kiszámítunk egy új generációt, tehát azoknak a celláknak a helyét, ahol a lépés után élő sejtek lesznek. Három eset lehetséges: egy sejt életben maradhat a következő generációra, elpusztulhat, vagy új sejt születhet egy üres cellában (természetesen üres cella, üresen maradhat). A cella következő pillanatban való lakott vagy lakatlan állapotának megadásához annak bal oldali szomszédjának, saját állapotának és jobb oldali szomszédjának állapotát veszi számításba. Ha egy sejt elpusztul, akkor a cellát üresnek tekintjük.
A sejtek életciklusát és új sejtek születését sejtautomata szabályokkal fogjuk megadni. 256 féle ilyen szabályt vizsgálunk, mind más-más elemi sejtautomatát határoz meg. Az egyes sejt-generációkat jellemzően egymás alá rajzoljuk, így egy ábrán a szimuláció egész folyamatát megtekinthetjük.
A fentiek alapján az egymás fölé rajzolt generációknál egy új négyzet értékét a felette lévő három (balra egy, felette és jobbra egy) cella értéke alapján határozzuk meg. Minden cella két értéket vehet fel, és három cella határozza meg az új generációs négyzet értékét, így összesen \(2^3=8\) féle állapotot definiálunk. Nézzünk egy példát.
A nyolc féle állapot kimeneti értékét tetszőlegesen definiálhatjuk, így összesen \(2^8=256\) szabályrendszert tudunk felállítani az elemi sejtautomaták esetén. (A fenti a \(71=01000111_2\)-es szabály, amely a fehér=0 és fekete=1, kettes számrendszerben felírt számból származik.)
Most már el tudjuk készíteni egy adott sejtautomata állapot következő generációs képét, a hozzá tartozó szabály szerint. A fenti 71-es szabállyal megvizsgálunk egy véletlenszerűen összeállított kezdő állapotot és annak képét. (A széleken szereplő értékeket úgy kell kiszámítani, hogy a másik oldalról egy mezőt hozzáveszünk oldalról, mintha össze lenne ragasztva egy gyűrűvé a sor.) Az alábbi ábrán, például az új generáció \(1.\) elemét úgy kapjuk meg, hogy az előző generáció \(10-1-2\) helyen szereplő értékeit tekintjük eredeti állapotnak. A következőkben gyakran \(1,0\) értékeket fogunk használni a fekete-fehér jelölés helyett, illetve egy-egy sort összesítve kettes számrendszerbeli számként írjuk fel az egyes sejtek állapotának megfelelően.
Tekintsünk egy példát. Az új generáció első elemét, amelyet a második sorban sárgával jelöltünk, a felette lévő sorból a szintén sárgával jelölt sejtek, határozzák meg. A fenti \(71\)-es szabályrendszer \(3.\) eleme alapján fehér lesz az eredmény. Az \(5.\) fekete elemet a bordóval keretezett elemekből tudjuk meghatározni, a szabályrendszer \(6.\) tagja alapján.
Rend és káosz
A bevezetőben megismertük az elemi sejtautomaták működési elvét és láthattuk, hogy miért éppen \(256\) szabályrendszert használunk. A 256 szabály négy csoportba osztható, aszerint, hogy tetszőleges kiinduló állapotból hogyan viselkedik több generáció után.
  1. uniform – lényegében tetszőleges kiinduló állapotból, kevés lépés után homogén végállapotba kerül a rendszer. Minden véletlenszerűség eltűnik.
  2. oszcilláló – lényegében tetszőleges kezdőállapot, néhány lépés után stabilizálódik, vagy oszcilláló mintává válik. A kezdetei véletlenszerű mintákból némelyek eltűnnek, azonban néhány megmarad. A kezdeti értékek lokális módosítása lokális hatással van a teljes mintázat tekintetében.
  3. véletlen – lényegében tetszőleges kezdőállapot véletlenszerű vagy kaotikus mintázatot vesz fel. Bármilyen stabil minta hamar eltűnik a környező véletlenszerű “zajban”. A kezdeti értékek lokális módosítása hamar átterjed a teljes mintázatra, korlátok nélkül.
  4. komplex – lényegében tetszőleges kezdőállapot olyan mintázatot hoz létre, amely komplex módon viselkedik és kerül kapcsolatba a környezetével. A bonyolult struktúrák hosszan fennmaradnak, és esetenként a 2. csoportba tartozó oszcilláló viselkedésbe mennek át. A kezdeti értékek lokális módosítása átterjedhet a teljes mintázatra, korlátok nélkül.
A képeken egy-egy példát láthatunk az osztályokra. Néhány szabály kiemelt szerepet tölt be. Vizsgáljuk meg közelebbről a \(30\)-as, \(90\)-es, \(110\)-es és \(184\) es szabályokat. A \(30\)-as szabály kaotikus viselkedése miatt véletlenszám generátorként használható. A \(110\)-es szabály alapján működő elemi sejtautomata a 4. csoportba tartozik komplex viselkedése miatt, és a Conway-féle életjátékot adja. A \(110\)-es szabály nem teljesen véletlenszerű, de nem is tartalmaz ismétlődő motívumokat.
A \(90\)-es szabály a Sierpinski-háromszöget (fraktált) eredményez, ha a kiinduló állapot egy olyan sor, amelynek a közepén egy fekete négyzet szerepel a többi pedig fehér.
A \(184\)-es szabályt az egysávos autópálya modellezésére is használják. Ha egy autó előtt ál egy másik, akkor megáll, ellenkező esetben továbbhalad.
Sejtautomatákkal modellezhetjük a többsávos autópálya forgalmát, olyan esetekben is, ha valamely sáv elfogy, és be kell sorolni az autóknak, különböző szabályok alapján. Ezek feldolgozása meghaladja jelen összefoglaló célját, azonban egy másik egyszerű, látványos modellt nézzünk meg. Egy négyzet vagy téglalap alakú véges négyzethálóra véletlenszerűen felveszünk valamennyi kék és ugyanannyi piros pontot. A piros pontok csak jobbra léphetnek, a kékek pedig csak lefelé, de csak akkor ha a lépés irányába se kék, se piros pont nincs a szomszédjában. Ha nem tud lépni, akkor várakozik mindaddig, amik ki nem ürül előtte a tér. A pontok a forgalomban rész vevő egy-egy autót szimbolizálnak. Az oldalt “kilépő” pontok a másik oldalon belépnek a következő körben, így a struktúra nem változik az eltűnő “autók” miatt. A közlekedési helyzetet egy \(200×200\)-as négyzethálón modelleztük, az autók különböző sűrűsége mellett. A modell meglehetősen egyszerű, egy valóságos helyzethez képest, ennek ellenére érdekes jelenséget figyelhetünk meg. Talán nem okoz meglepetést, hogy kevés autó esetén nincs közlekedési dugó, sok autó esetén pedig gyakori, esetleg teljesen leállhat a forgalom. A modell szerint mindkét esetben további érdekességeket tapasztalhatunk. Kevés autó esetén a piros és kék pontok átlós sávokba rendeződnek, és megfelelő sok lépés után már minden autó megállás nélkül tud mozogni. Sok autó esetében egy idő után olyan torlaszok alakulnak ki, amelyek nem oldódnak fel, és teljesen leáll a forgalom. Ezek az állapotok függetlenek a véletlenszerűen kialakított induló helyzettől. Ezt a modellt Biham-Middleton-Levine közlekedés modellnek nevezzük, megalkotóik után. Az eddigi kutatások csekély támpontot adnak, hogy mennyi legyen a sok vagy a kevés autó a kiinduló állapotban. Az általunk vizsgált sejtautomatábban \(34-36\%\)-os kezdő kitöltöttség esetén fordul a forgalom dinamikája. Megfigyelhetünk azonban egy további érdekességet is. Az előző határok környékén, a mi esetünkben \(35\%\)-nál kialakul egy átmeneti állapot, amikor periodikus mozgás alakul ki. A szabad mozgás mintájára átlós sávokba rendeződnek az autók, de kisebb-nagyobb dugók alakulnak ki. Fontos eleme ennek az állapotnak, hogy a dugók miden esetben maguktól feloldódnak és nem lesz teljes leállás. Az esetek jó részében sok iterációs lépés szükséges, így mozgásban csak egy teljes esetet vizsgálunk meg, a többinél csak a végső állapotot mutatjuk be (az átmeneti állapot esetén \(4000\) iterációs lépésből az utolsó \(500\)-at.
\(31\%\)-os telítettség mellett, \(1000\) iterációs lépés után már látszik a sávokba rendeződés, és a szabad mozgás (egyre ritkulnak az apró dugók).
Állandósult dugó
\(55\%\)-os telítettség esetén, viszonylag hamar, kb. 600 lépés után minden autó dugóba került és megszűnik a mozgás (a szimuláció \(601.\) képkockája).
Átmeneti állapot
A legtöbb érdekességet hordozó átmeneti állapotot, esetünkben \(36\%\)-os telítettség mellett figyelhettük meg, amelyhez \(4000\) lépést modelleztünk (az utolsó \(500\) képkocka látható animálva). A Biham-Middleton-Levine modell egyszerű feltételezés alapul, amelyet még úgy is heréz általánosítani és gyakorlati alkalmazását tekinteni, ha egy nagyváros úthálózatán próbáljuk meg értelmezni. A modell alapfeltevései túl egyszerűek ahhoz, hogy gyakorlati problémára megoldást kínáljanak, azaz lesz dugó, ha sok az autó. A sejtautomata szabálya lényegében azt mondja, hogy csak egy lépésre gondolkodik előre, és megáll ha vannak előtte, függetlenül attól, hogy egyébként mennyire akadályozza a többieket. Ez nem csak ahhoz a kellemetlen helyzethez vezet nagy autó sűrűség esetén, hogy megáll a forgalom, hanem ahhoz is, hogy nem is lehet tovább indítani az adott szabályrendszerrel. Érdekes továbbfejlesztése lehet a modellnek, ha a mozgó részecskék több eseményt vesznek számításba, esetleg nagyobb távolságból is vesznek adatot, megtanulnak “udvariasan” viselkedni, vagy elsőbbséget adni. A modell mindenképpen továbbfejleszthető, ha a sejtautomata szabályrendszerébe olyanokat kódolunk, hogy pl. a piros autónak elsőbbsége van vagy ha találkoznak, és mindkettő megáll, akkor valamelyik visszalép egy mezőt, ha az üres, esetleg van mód manőverezésre, és megállás esetén a kijelölt iránytól eltérhetnek, és más irányba folytathatják útjukat, persze ha az szabad.
A közlekedést mikroszintű szabályok alapján is megközelítetjük, amelyek szintén modellezhetők sejtautomatákkal. Vegyük példaként egy autópálya forgalmát (ezen nincsenek kereszteződések). Minden sávra egy-egy sejtautomatát vezethetünk be oly módon, ha az úttestet felosztjuk olyan elemi szakaszokra, amely adott szempont szerint elfogadható. A leginkább kézenfekvő, hogy legyen az osztásköz egy autó hossza. Ez valószínűleg nem hagy túl sok mozgásteret, ezért kibővíthetjük oly módon, hogy az osztások legyenek akkorák mint az átlagos követési távolság. Az egyes tartományok értékét az adja, hogy van-e benne autó, vagy nincs. Készítsünk most szabályrendszert a fenti struktúrához. Ha szabad az út valamely autó előtt, akkor nem változtat a sebességén. Ha az előtte haladó lassít, akkor ő is lassít. Lehetőség van olyan szabály megalkotására is, hogy mi történjen a lassítás után, például sávot válthat, ha nem jönnek mögötte a mellette lévő sávban. Ezzel már egy komplex modellt írtunk le, és a sejtautomaták segítségével arra is van mód, hogy közlekedési szituációkat modellezzünk. Lehet baleset, lezárt sáv miatti átsorolás, új sáv megnyílása.
Egy-egy út vagy úthálózat közlekedési sajátosságait figyelembe véve alkothatunk meg olyan szabályokat, amelyek többé kevésbé állandóak és eredményük a gyakorlatba is átültethetők. A Biham-Middleton-Levine modell alapján egy primitív következtetést vonhatunk le: ne engedjünk a forgalomba \(35\%\)-nál több autót, különben végérvényesen dugóba kerülnek. Ebből is látszik, hogy a modell finomítására, komplexebb szabályrendszerre van szükség. Egy körültekintően elemzett közlekedési helyzet, a jól megválasztott (sejtautomata) modellel olyan eredményeket is produkálhat, amely a végeláthatatlan várakozás helyett például az ajánlott sebességről tájékoztatja az autópályán haladókat, annak érdekében, hogy ne alakuljon ki álló kocsioszlop. Ez fontos célja lehet a forgalomszervezésnek, ugyanis az álló kocsioszlop nem csak kellemetlen a benne ülőknek, de az óvatlan vezetők számára balesetveszélyes is.

Érdekességek

További alkalmazások

Kriptográfia

A nyílt kulcsú kriptográfia rendkívüli ütemben fejlődik, hogy lépést tudjon tartani a technológia és a biztonságos információ átadás és tárolás iránti igényeinkkel. Megfejteni lényegében lehetetlen.

Tovább olvasom »

Kombinatorika

Kombinatorika a gyakorlatban: 12 alapvető leszámolási eset a doboz-golyó modellel A kombinatorika egyik legismertebb problémaköre a dobozokba történő golyóelhelyezés, amely számtalan gyakorlati és elméleti kérdés alapja. Ezen az oldalon részletesen

Tovább olvasom »

Most kedvező áron az előkészítő csomag

2023 iFeladatok I.

Interaktív feladatok felvételire és emelt szintű érettségire
4.590 Ft 2022/23 tanévre
  • 20 iFeladat automatikus javítással
  • 19 témakör
  • 121 megoldási lépés
  • Megoldássegítő felépítés
  • 2,15 átlagos nehézség (1-3 skálán)
  • A tananyag 2023. június 30-ig érhető el

2023 Emelt szintű
matematika előkészítő

Kidolgozott feladatok felvételire és emelt szintű érettségire
59.900 Ft 2022/23 tanévre
  • 25 kidolgozott témakör
  • Több mint 200 kidolgozott példa
  • 13 interaktív feladatsor
  • 21 elméleti összefoglaló
  • Felkészülés folyamatos követése, naplózása
  • 2024-től érvényes követelményekkel kiegészítve
  • 25 szóbeli tétel - teljes tételsor
  • A tananyag 2023. június 30-ig érhető el

2023 Középszintű matematika kurzusok

Tananyag középszintű matematika felkészüléshez
1.750 Ft 2022/23 tanévre, kurzusonként
  • Témakörönkénti előfizetés
  • Megértést segítő magyarázat
  • Definíciók, tételek
  • Kidolgozott típuspéldák
  • Online feladatok, azonnali javítással
  • Felkészülés folyamatos követése, naplózása
  • 2024-től érvényes követelmények alapján
  • A tananyag 2023. június 30-ig érhető el