Számít az úthálózat és algoritmusok dolgozni velük
A matematikában úthálózat (közúti és egyéb) képviselte a súlyozott gráf. Helyek (vagy csomópontok) - a csúcsok, élek - út élek súlya - távolságok ezeken az utakon.
Mert súlyozott gráfok kínál sok algoritmus. Például egy népszerű Dijkstra algoritmus megtalálása a legrövidebb utat az egyik csúcspont a másikra. Mindezen algoritmusok közös elv (matematika) jellemző - ezek egyetemes, azaz sikeresen lehet használni a grafikonok bármilyen design. Különösen az egyes algoritmus ismert komplex - ez nagyjából megfelel a növekedés az algoritmus végrehajtási idő szerint a csúcsok száma. Mindez lehet olvasni részletesen, például a Wikipedia.
Térjünk vissza a gyakorlati problémákat. Road egy súlyozott gráf, de az út - ez nem minden gráf. Más szóval, nem lehet semmilyen gráf, hogy egy közúti hálózat. Ellentétben virtuális gráf, mint egy matematikai absztrakció, utak épülnek az emberek a tényleges anyag, és nagyon sok pénzt. Tehát megállapított nem véletlenszerűen, hanem aszerint, hogy az egyes gazdasági és gyakorlati szabályokat.
Nem tudjuk, a szabályok azonban dolgozik úthálózattal, akkor lehet használni algoritmusok, amelyek hatásosak utak grafikonok, amelyek azonban nem alkalmasak az univerzális és a grafikonok matematikai értelemben. Vegyünk két ilyen algoritmus.
Több fontos fogalmak és konvenciók
1. fogjuk használni a súlyozott irányítatlan gráf nem-negatív éle súlyok. Különösen az utak a régión belül (ország) képviseli éppen egy ilyen grafikont.
2. A mátrix legrövidebb távolságok (MKR) - ez kicsi és egyszerű példa megtalálható számos autóatlaszok. Ez a címke általában valami olyasmi, hogy „a távolság a legfontosabb városok”. Úgy tűnik, részeként a mátrix alatt vagy felett van a fő diagonális (a bal felső a jobb alsó), mert a másik oldalon a fő diagonális azonos számok, más szóval egy M elem (i, j) = M (j, i). Ez azért történik, mert a grafikonon, mint a matematikusok mondják, irányítatlan. A sorok és oszlopok a város (felső grafikon). A valóságban egy ilyen tábla sokkal nagyobb, mint a csúcs, kivéve a városok, magában foglalja az összes falvak és kereszteződésénél, de nyomtatni egy ilyen nagy asztal a atlasz, természetesen lehetetlen.
Az első lépés a jövőben is (mentálisan), hogy a tábla felső részén, megkapjuk MCR szimmetrikus fő diagonális, továbbra is szem előtt tartani, az alábbi táblázatban. Ebben az esetben az oszlop szám egyenlő néhány sort az azonos számú mindegy, néhány használt fogalmak. Az általunk használt valamit, a másik, hogy a határokon egymással.
A bigbag lehet: a) előre ismert, mert már számított ez a keresési módszereket MKP; b) nem tudjuk, hogy a CDM és határozza meg, soronként, ha szükséges. Row - ez azt jelenti, hogy a kívánt vonal számítjuk távolság csak a megfelelő vertex a többi csúcsok, például Dijkstra módszere.
3. Egy pár fogalmak. Az excentricitás a csomópont - a távolság a vertex a legtávolabbi tőle. Gróf Radius - a legkisebb különc minden csúcsot. Gróf Center - a legjobb, ami egyenlő a sugárral különcség.
Hogy néz ki a gyakorlatban. Központ az úthálózat - ez a város vagy a kereszteződést, a legkevésbé távol minden más pont a hálózat. Sugár - legnagyobb távolság a központi csomópontot a távoli.
4. fokozat csúcsok - a bordák száma, amely kapcsolódik a csúcsra.
A grafikonok az úthálózat, az átlagos mértéke az összes csúcsot területén található 2-től 4 Ez teljesen természetes - nehéz és drága építeni csomópontok sok feeder utak, nem kevésbé nehéz, akkor használja ezt a úthálózat. Grafikonok, alacsony átlagos mértéke a csúcs ritka, mint látjuk grafikonok úthálózatok csak úgy.
Probléma 1. grafikon keresési sugár és a középső mátrix legrövidebb távolságok
Megjegyezzük, hogy a gráf lehet több központok, de meg akarjuk találni ezek közül bármelyik.
Ez nem a leggyorsabb. Miért van szükség a gyorsabb, ha látszólag sugár és a grafika közepében található egyszer? Például vannak olyan feladatok és algoritmusok őket, ahol során mellszobor tetejét folyamatosan „pereobedinyayutsya” a csoportban, és a kritériumok minden csoportban a sugarát. Ebben az esetben a sugár újratervezi többször, és a sebesség a keresés nem válik egy fontos paraméter. Hogyan lehet megtalálni a sugara a gyorsan?
Lássuk, ami miatt azt megszerezte. Tekintsük az értékek egy-egy sorában MKP mátrix, más szóval, úgy a távolság egyik csúcsa az összes többi. Könnyen bizonyítani, hogy a sugár a gráf nem lehet nagyobb, mint a maximális érték ebben a sorban, és nem lehet kisebb, mint a minimális érték ezt a fonalat. Matematikailag szólva, találtunk egy felső és alsó a határ, és ha azok megegyeznek - meg fogjuk találni a számot.
Tegyük fel, hogy megtaláltuk a értéke mindössze két sorban az A és B Ebben az esetben a maximális érték a sorban A jelentése megegyezik a legkisebb érték a B sorban (ez az érték lesz a kereszteződésekben a oszlop az A és B sorban). Könnyen azt mutatják, hogy A - gróf Center, és talált érték - a sugarát. A probléma megoldódott.
Általában a szempontból a matematika, persze, nem ez a helyzet. Ez lehet építeni egy olyan elméleti grafikont, amelyben az igény, hogy egy csomó sort (szinte minden, kivéve A). Ez egyszerűen nem lehetséges, hogy egy igazi út ilyen hálózat - nincs elég pénz.
Ott volt az utolsó feladat. Hogyan lehet gyorsan megtalálni ezeket a sikeres vonalak B1, B2, stb Az igazi úthálózat grafikonok történik nagyon egyszerűen és gyorsan. Ez lesz a legtávolabb egymástól a felső, de nem feltétlenül a legtávolabbi (matematikai értelemben, azt látjuk, az átmérője a gráf nem szükséges). Vegye bármely csúcspont, azt találjuk, mert a legtávolabbi, az új hátsó a legtávolabbi, és így, amíg a tetején pár nem fog megjelenni legtávolabb egymástól.
Kaptunk pár csúcsok B1 és B2. Találunk egy vektor páros M, a fent leírtak szerint. Egy sor, amelyben találjuk min (M (i)) - egy versenyző a központtól, jelöli A. Ha az A oszlopban értéke min (M (i)) - a maximális, megtalálta a központ és a sugara. Ha nem, akkor a maximális értéket az A oszlopban annak a távolságnak felel a többi vertex (nem B1 és B2). Szóval van egy új B3 a lista tetején, hogy megtalálják a vektor M. Alternatív kereshet B3 és legtávolabbi felső és ha ez nem a B1 és B2, adja hozzá a B4. Ennélfogva, a növekvő listáját csúcsok B, míg a középső és a sugár nem lesz megtalálható.
2. feladat megtalálni a legrövidebb távolság mátrix
A legnépszerűbb keresési algoritmusok MKR (Floyd-Uorshella, például) van ismertetve. Mindegyik univerzális, és egyikük - Dijkstra algoritmus bináris kupac - lehetővé teszi, hogy egy ilyen dolog, mint egy ritka gráf. Azonban azt is nem használja a funkciókat az úthálózat.
Fogjuk használni őket, és egy teljesen más algoritmus és meglévő oszlopokat kell gyorsítani a tíz szeresére Dijkstra algoritmus. Meg kell jegyezni, hogy az azonnal jellemzője ennek az algoritmusnak az, hogy keres egy CDM, és minden egyszerre, és pontosan (azaz kb, nem heurisztikus).
Tekintsük az alapötlet az algoritmust. A lényege az, hogy távolítsa el vertex változatlan legrövidebb távolság a fennmaradó pontokat. Ha így teszünk, emlékezve arra, amit pont és milyen távolságra volt csatolva egy csúcsot, akkor távolítsa el az összes pontot, kivéve egyet, majd tedd vissza a gróf, de már kiszámított távolságok.
Kezdjük egy egyszerű, a felső fokú 1. Meg lehet távolítani egyébként. Ez nem megy át semmilyen legrövidebb utak, továbbá a módját, hogy a felső, hová mennek keresztül a felső, amelyhez kapcsolódnak eltávolítható felső.
Legyen A - csúcsból fok 2, és ez kapcsolódik a csúcsai a B1 és B2. Ha az útvonal a B1-A-B2 hosszabb vagy egyenlő, mint a szélén a B1-B2-től a pont nem adja át semmilyen útvonalak, amellett, hogy az útvonal A pont önmagában (az összes többi áthaladnak B1-B2). Tehát a lényeg A kivehető. Ellenkező esetben, vagyis a ha B1-A-B2 rövid B1-B2 és B1-B2 bordák nem, A csomópont lehet távolítani beállításával a súlya a B1-B2 bordák egyenlő a súlyok összege: | B1-A | + | A-B2 |. Útvonal A többi pont sem halad át a B1, B2 vagy, ismert lesz, ha a távolság a B1 és B2, A távolság olyan könnyen kiszámítható.
Ugyanez az elv lehet távolítani a tetején bármilyen mértékben, hogy ebben az esetben, amennyiben szükséges, Bi-A-Vj a Bi-Bj. Azonban meg kell érteni, hogy minél nagyobb fokú csúcsok, annál lehetséges, ellenőrizni kell a bordák. A csúcsok a foka n értéke egyenlő n (n-1) / 2.
Elméletileg így lehet eltávolítani az összes csúcsot bármely oszlop, de általában azt várják a baj növekedésével jár együtt az élek számát. Törlése esetén a csúcsok amelynek mértékben n, a mértéke csúcsok szomszédos egy eltávolítható, lehet: csökkenés -1, nincs változás, növeli az N-2. Ebből következik, hogy amikor törlése csúcsai fok 3 és magasabb fokú a maradék csúcsok, általában növekszik, a grafikon kevésbé kifinomult, és végül eltávolítjuk a tetejét alakulnak meglehetősen munkaigényes feladat. Az algoritmus általában rendkívül időigényes, és gyakorlatilag használhatatlan, de ez az általános esetben.
Számít az úthálózat egy különlegessége ennek fajtája: sok a felső lehet távolítani a nem csak a növekedés nélkül, hanem csökken a mértéke szomszédsági. Sőt, ha egy bizonyos csomópont lehet „sikeresen” eltávolították őt, akkor „sikeresen” később eltávolítható, miután megszűnt néhány szövetséges csúcstalálkozók.
Ennek megfelelően, csak ki kell választania a tetején minden lépését eltávolítjuk a jobb, kezdve azokkal, amelyeket el kell hagyni több „sikeres”.
Az algoritmus itt megtekinthető részletesebben. Ott van írva, hogyan kell törölni egy vertex, miközben a távolság és útvonal között maradt. Ezt a folyamatot nevezik szétszerelés. Elmondják, hogyan kell visszaállítani a gróf akkoriban, hogy vegye fel a fordított sorrendben, az egyik az, hogy számolni a CDM. Ezt a folyamatot nevezik szerelvény.
Is adott az eredménye az algoritmus grafikonok amerikai úthálózat link.
Ha figyelembe vesszük az úthálózat általánosságban a grafit, grafit és bizonyos speciális tulajdonságokkal, akkor létrehozhat és sikeresen használja a hatékonyabb algoritmusok számos gyakorlati problémát.