Term papír program végrehajtásának Dijkstra algoritmus (az építési áramkörök minimális hosszúságú) -
Az Oktatási Minisztérium és a Tudományos Ukrajna
Kharkovsky Nemzeti Egyetem rádióelektronikai
Tárgy: „A szoftver alkalmazása az algoritmus Dijkstra (az építési áramkörök minimális hosszúságú)”
fegyelem „Programozás”
Student csoportok KI-05-4 Rudenko DA
Petrov O. V. Mashtalir SV
Megjegyzés a magyarázó lejáratú papírok: 23c. 5 ábra. 1. táblázat. 5 szakaszok, 3 alkalmazások.
A vizsgálat tárgya - egy grafikon a súlyozott élek.
A cél a munka - a fejlesztés egy demonstrációs program használatáért Dijkstra algoritmus.
kutatás módszere - az irodalom, a fordítás és hibakeresés egy programot a számítógépen.
Akkor használja ezt a programot, hogy megtalálják a legrövidebb távolság két pont között.
A program C ++ Microsoft Visual C ++ 6.0 környezetben. Kulcsszavak: Dijkstra, grafikonok, csúcsok, élek, SÚLYOK, út, súly, címke, programot, írja, műveleteket, hurkok, szomszédsági mátrix.
Köszönhetően annak széles körű használata, az elmélet a megállapítás a legrövidebb utak régóta dolgoznak intenzíven.
Megtaláljuk a legrövidebb út - rendkívül fontos, és használják szinte mindenütt, az optimális útvonalat között két tárgy a földre (például a legrövidebb út az otthontól a University), robotpilóta rendszerek, annak érdekében, hogy megtalálják az optimális útvonalat a közlekedési, kapcsoló, egy információs csomagot az interneten, stb n.
A legrövidebb út tartják révén egy matematikai objektum neve grafikon.
Három leghatékonyabb algoritmus megtalálása a legrövidebb utat:
· Dijkstra algoritmus (használják, hogy megtalálják az optimális útvonalat két csomópont között);
· Floyd algoritmus (megtalálásához az optimális útvonalat között az összes pár csúcsot);
· Ian algoritmus (megtalálásához k-optimális útvonal két csúcs között).
Ezek az algoritmusok könnyen teljesíthető kis pontok számát a grafikonon. Számának növelésével feladatuk keresi a legrövidebb utat bonyolult. Itt jön a modern technológia eszközei
Számítógépes szolgáltatások és az információs technológia növelték a lehetőséget az ilyen mindenre kiterjedő tanulási módszer és a teremtés, mint a modellezés tárgyak, jelenségek és folyamatok - például azok, amelyek a természetben létezik, és azokat, amelyek mesterségesen létrehozott ember.
Az objektumok száma bonyolult nőtt, és a természetes modellezés (modellek épületek) lett veszteséges, gazdaságtalan. Ezért tanulni alkalmazott matematika kezdődött. Matematikai modellek segítségével - egyenletek, egyenlőtlenségek, képletek és hasonlók nevezik matematikai modell fejlesztése és adaptálása, amelyek hatékonyak numerikus módszerek kidolgozására van szükség.
Ahhoz, hogy a nagy lehetőséget a matematikai modellezés nélkül lehetetlen hatékony eszköze számítások automatizálását, amelyek a számítógépek. Hála a számítógépek megjelenésével és az információs technológia fejlődése azok a módszerek és számítógépes szimuláció, amely képes megoldani komplex gyakorlati problémák, mint például a vezetés a nagy energetikai rendszerek létrehozását, megbízható időjárás-előrejelzés vagy a növény modellezés regionális és a nemzeti rendszerek tervezése repülőgépek, hajók és így tovább. N. Computer modell - kerül a számítógép egy sor eszközt, hogy koncepció megvalósítása a számítástechnika.
Ahhoz, hogy hajtsák végre a számítógépes modell, a nagy értékű az a tudományos irányú programozás. Enélkül a számítógép egyszerűen olyan eszközök, áramkörök, amelyek nem lehetnek hasznosak.
A nagyobb programok annak összetettsége miatt gyakran tartalmaznak hibákat okozhat anyagi kárt és néha veszélyezteti az emberek életét (például aviapolotami kezelése). Ennek eredményeként a harc a problémát a kód három új programozási fogalmak fejlesztettek:
a) egy objektum-orientált programozás (OOP);
b) Unified Modelling Language (UML);
c) speciális szoftver eszközök;
Az összes objektum-orientált C ++ nyelv a legelterjedtebb. És segítségével ebben természetesen projekt megvalósítása Dijkstra algoritmus.
1 NYILATKOZAT a problémát, és hatókörét
A fő cél ennek a képzésnek a projekt egy szoftver alkalmazása az algoritmus megtalálják a legrövidebb út van bármely két pont között a grafikonon.
A program kell működniük annak érdekében, hogy a felhasználó által megadott csúcsok száma és hossza élek a grafikon, majd feldolgozza ezeket az adatokat mutatja legrövidebb út két adott csomópont és annak hosszát. Ott kell lennie a különböző keresési eredmények, a program nem ad hibát, és megfelelően működik.
Ez a program is használható diszkrét matematika tanulmányozása grafikonokat vagy vizuális támogatás, amely bemutatja a használatát Dijkstra algoritmus a gyakorlatban.
2 ELMÉLET
2.1 Információk a grafikonok
G gráf (ris.2.1.1) által meghatározott pontok halmaza (csúcsok) x1, x2. xn. (X-szel jelölt), és amely több vezetéket (élek) a1, a2. AM. (Ami val jelölt), amely összekapcsolja az összes vagy néhány ilyen pont. Így, a G gráf teljesen meghatározni (és jelölt) egy pár (X, A). Ha a széleit a halmaz hangsúly, hogy általában nyíl által mutatott, akkor nevezzük ívek, és a Count ilyen bordákkal nevezzük egy irányított gráf.
Például, ha az út nem a két, egyirányú forgalom irányát és ezt a mozgást a nyíl által mutatott.
Ha az élek nem a tájékozódás, a gráf irányítatlan, (kétirányú forgalom).
A irányított gráf ív jelöljük rendezett pár, amely egy kezdő és befejező csúcsok, annak irányát feltételezzük, hogy kell adni az első csúcspont a második.
A (vagy orientált útvonalat) irányított gráf sorozata ívek, ahol a terminális csúcsa bármely ív, más, mint az utolsó, az elsődleges csúcs következő.
Például, ábrán. 2.1.2 útvonalak ívek szekvenciája:
A6, A5, A9, A8 és A4. (1)
A1, A6, A5, A9, A10, A6 és A4. (3)
Orientált lánc (ortsepyu) egy útvonal, amelyben az egyes ív nem egynél többször használják.
Egyszerű ortsepyu úgynevezett útvonal, ahol minden csúcs nem használják többször. Például, az út (2).
Az útvonal irányítatlan „kettős” az utat, és ez a fogalom tekinthető olyan esetekben, amikor tudjuk figyelmen kívül orientált íveket a grafikonon. Így, az útvonal egy sorozata élek ä1 ä2. äq, amelyben minden él AI, kivéve az első és az utolsó bordák, kapcsolódó bordák ai-1, ai + 1, és annak vége csúcsait. Sequence ívek:
ä2 ä4 ä8 ä10 (4)
ä2 ä7 ä8 ä4 ä3 (5)
ä10. ä7. ä4. ä8. ä7. ä2. (6)
a grafikonon ábrán látható. 2.1.2 olyan útvonalak; két pont az íven szimbólum azt jelzi, hogy orientációja elhanyagolt, azaz az ív tekinthető, mint egy nem-orientált szélét. Továbbá, az út vagy útvonal lehet sorozata által ábrázolt csúcsok. Például, az út (1) a következő: X2, X5, x4, x3, x5, x6. Néha az íveket a grafikon rendelt számok, az úgynevezett a tömeg, költség vagy az ív hosszát. Ebben az esetben, a grafikon nevezzük gráf súlyozott élek. És ha a súlyt tulajdonított az a gráf, akkor kapunk egy gráf súlyozott csúcsot. Ha a súllyal az oszlopra, és az íveket és csúcsokat, akkor egyszerűen hívják körültekintő. Ha figyelembe vesszük, hogyan ji sorozata által ábrázolt ívek (ä1 ä2. äq), súlya veszik a szám l (μ), egyenlő a súlyainak összegét az összes ívek M, azaz,
2.2 Dijkstra algoritmusa
Dijkstra algoritmus épít a legrövidebb utat, ami a forrás vertex a másik a gráf (ha van ilyen).
A működés során az algoritmus egymás jelölt megfontoltabb csúcs. A vertex jelölt az utolsó (most) közelebb van a tetején az eredeti, mint az összes jelöletlen, de több, mint bármi jelölve.
Első jelölt kezdeti csúcs; A következő valószínűleg kell jelölni a csúcs legközelebb a forrást, és mellett is.
Tegyük fel, hogy egy bizonyos szakaszában van jelölve néhány csúcs. Ismert legrövidebb út vezet a forrástól a felső jelzett. Minden jelzetlen csúcsok tegye a következőket:
1. Tekintsük ívek vezet a jelölt csúcsok egy jelöletlen. Minden arc az utolsó ív az út a kezdeti csúcs a jelöletlen.
2. Ezekből legrövidebb út. Majd válassza ki a legrövidebb köztük az összes jelöletlen csúcsok és címke a felső, amelyhez vezet.
Az algoritmus leáll, ha az összes elérhető csúcsok vannak jelölve.
Ennek eredményeként a Dijkstra algoritmus épít egy fa legrövidebb út.
3 JELLEMZŐI munkaközegnek
Írásakor egy programot a Microsoft környezetben Visual C ++ 6.0. Ez a környezet lehetővé teszi, hogy alkalmazásokat írni nyelvén C ++.
Ennek során az írás a programot, mind az üzemeltetők és hivatalos nyelve a C ++ kiemelve a különböző színű megkülönböztetni őket a változó által meghatározott programozó. A Microsoft Visual C ++ 6.0 környezet tartalmaz egy beépített fordítóval.
A programot azért hozták létre a konzol mód - a mód, amely nem rendelkezik a grafikus felületen.
4 szoftver megvalósítása
4.1 Az algoritmus és a program tervezése
A program megjeleníti a legrövidebb utat a két csúcsot a grafikonon, és a hossza.
Amikor elkezdi a programot a képernyőn megjelenített adnunk a súlyok élek a vizsgált gráf. Az adatokat a felhasználó által beírt jelennek formájában a szomszédsági mátrix, ahol is az élek nem léteznek zérussal jelöltük. Miután a megadott bordák beállítása 65535, amely feltételezi, hogy végtelen.
A következő szakaszban a program felszólítja, hogy adja meg a számát a vertex, amelyek között meg kell tudni, hogy az utat. Ha a kezdő és záró csúcsot egyezik, akkor egy üzenet jelenik meg, és a program működése leáll. Ellenkező esetben a Dijkstra algoritmus közvetlenül, akinek rendszer látható B. függelék
Az eredmény a program megjeleníti a vertex, amelyen keresztül a minimális utat, valamint a kimeneti útvonal hosszát. Ha az elérési út két pont között a nem léteznek - egy üzenet jelenik meg.
4.2 Leírás használt szoftver
Táblázat 4.2.1 változók meghatározása