Termen de implementare software-ul de hârtie al algoritmului Dijkstra (construirea circuitelor de lungime minimă) -

Ministerul Educației și Științei din Ucraina

Kharkovsky UNIVERSITATEA NAȚIONALĂ DE Radioelectronică

Subiect: „Implementarea software a algoritmului Dijkstra (construirea de circuite de lungime minimă)“

privind disciplina „Programare“

Grupurile de elevi KI-05-4 Rudenko DA

Petrov O. V. Mashtalir SV

Notă la termen de hârtie explicativ: 23c. 5 Fig. Tabelul 1. 5 sectiuni, 3 aplicatii.

Obiectul de studiu - un grafic cu muchii ponderate.

Scopul lucrării - dezvoltarea unui program demonstrativ pentru utilizarea algoritmului Dijkstra.

Metoda de cercetare - studiul literaturii, compilarea și depanarea unui program de pe un calculator.

Puteți utiliza acest program pentru a găsi cea mai scurtă distanță între două puncte.

Programul este scris în C ++ în Microsoft Visual C ++ 6.0 mediu. Cuvinte cheie: Dijkstra, grafice, noduri, muchii, GREUTATI, Road, greutate, etichetă, Program, tip, operatori, funcții, bucle, matrice de adiacenta.

Datorită utilizării sale pe scară largă, teoria de a găsi cele mai scurte drumuri au fost în curs de dezvoltare intens.

Găsirea calea cea mai scurtă - este extrem de importantă și este folosit aproape peste tot, de la găsirea traseului optim între două obiecte pe sol (de exemplu, cel mai scurt drum de la domiciliu la Universitatea), sistemele pilot automat, în scopul de a găsi calea optimă în transport, de comutare, un pachet de informații pe internet, etc. n.

Cel mai scurt drum este considerat cu ajutorul unui obiect matematic numit un grafic.

Există trei dintre algoritmul cel mai eficient pentru a găsi calea cea mai scurtă:

· Dijkstra algoritm (folosit pentru a găsi o rută optimă între două noduri);

· Algoritmul Floyd (pentru găsirea traseului optim între toate perechile de noduri);

· Ian algoritm (pentru identificarea traseelor ​​k optime între două vârfuri).

Acești algoritmi sunt îndeplinite cu ușurință cu un număr mic de noduri în grafic. Prin creșterea numărului de sarcina lor de a căuta calea cea mai scurtă este complicată. Aici vine în ajutorul tehnologiei moderne

Facilitățile de calculatoare și tehnologia informației au crescut posibilitatea unei astfel de metode atotcuprinzătoare de învățare și de creație, ca modelarea obiectelor, fenomenelor și proceselor - cum ar fi cele care există în natură, precum și cele care sunt create în mod artificial de către om.

Numărul de obiecte este complicată a crescut, și modelare naturale (modele de clădiri) a devenit neprofitabilă, nerentabilă. Prin urmare, pentru a studia matematica aplicată a început. Folosind modele matematice - ecuații, inegalități, formule, și altele asemănătoare se numește modelare matematică pentru dezvoltare și adaptare, care sunt eficiente sunt necesare metode numerice.

Pentru a realiza un mare potențial de modelare matematică este imposibilă fără mijloace puternice de automatizare calcule, care sunt calculatoare. Datorită apariția calculatoarelor și a dezvoltării tehnologiei informației sunt metodele și mijloacele de simulare pe computer care pot rezolva probleme practice complexe, cum ar fi gestionarea sistemelor energetice mari, crearea de prognoză meteorologice sau de modelare a culturilor regionale și a sistemelor naționale, proiectarea de aeronave, nave și așa mai departe. N. Computer modelul - este plasat în calculator un set de instrumente care implementează conceptul de calcul.

Pentru a pune în aplicare modelul de calculator, marea valoare are direcția științifică de programare. Fără ea, computerul este pur și simplu un set de dispozitive, circuite, care nu pot fi utile.

Programe de mari dimensiuni, din cauza complexității sale conțin adesea erori care pot provoca pagube materiale și, uneori, amenință viața oamenilor (de exemplu, managementul aviapolotami). Ca rezultat al luptei cu problema codului de trei concepte de programare noi au fost dezvoltate:

a) o programare orientată-obiect (OOP);

b) Unified Modeling Language (UML);

c) instrumente de dezvoltare de software specializat;

Dintre toate C ++ orientat-obiect limbaj este folosit cel mai mult pe scară largă. Și cu ajutorul său în acest proiect curs este implementat algoritmul lui Dijkstra.

1 DECLARAȚIE PROBLEMEI ȘI DOMENIUL DE APLICARE AL ACESTEIA

Obiectivul principal al acestui proiect de curs este o implementare software a algoritmului găsi calea cea mai scurtă dintre oricare două noduri ale unui grafic.

Programul trebuie să funcționeze astfel încât utilizatorul a introdus numărul de noduri și lungimea marginilor a graficului, și calea cea mai scurtă, apoi prelucrarea acestor date este afișat între două noduri date și lungimea sa. Ar trebui să existe o varietate de rezultate de căutare, programul nu a dat erori și funcționează în mod corespunzător.

Acest program poate fi folosit în matematică discrete la studiul de grafice sau ca un ajutor vizual, arătând utilizarea algoritmului Dijkstra în practică.

2 TEORIE

2.1 Informații despre graficele

Grafic G (ris.2.1.1) definite de setul de puncte (noduri) x1, x2. xn. (Notată prin X) și o pluralitate de linii (muchii), a2 a1. AM. (Care este notat cu A) interconectarea toate sau unele dintre aceste puncte. Astfel, graficul G este complet determinat (și marcate) o pereche (X, A). Dacă marginile setului O focalizare care este de obicei indicată de săgeată, atunci ele sunt numite arce, iar contele cu astfel de coaste se numește un grafic direcționat.

De exemplu, în cazul în care drumul nu este un trafic de două, într-o direcție și direcția acestei mișcări este arătată de săgeată.

Dacă marginile nu sunt orientarea, graficul este neorientat, (trafic în ambele sensuri).

Arcul grafic direcționat notat pereche comandat constând dintr-un început și de sfârșit nodurile, direcția sa se presupune a fi dat de la vârful primul la al doilea.

Prin (sau traseu orientat) direcționat grafic este o secvență de arce, în care nodul terminal al oricărui arc, altul decât ultimul, este nodul primar următor.

De exemplu, în Fig. 2.1.2 căi sunt arce de secvență:

A6, A5, A9, A8 și A4. (1)

A1, A6, A5, A9, A10, A6 și A4. (3)

lanț Oriented (ortsepyu) este o cale în care fiecare arc nu este folosit mai mult decât o dată.

ortsepyu simplu numit o cale în care fiecare nod nu este folosit mai mult de o dată. De exemplu, calea (2).

Traseul a neorientate „dubla“ calea, iar acest concept este luat în considerare în cazul în care ne putem neglija arcelor orientate în grafic. Astfel, traseul este o secvență de muchii ä1 ä2. äq, în care fiecare muchie AI, cu excepția primei și ultimei coaste, conectate cu nervuri ai-1, ai + 1 și nodurile sale de capăt. Secvența de arce:

ä2 ä4 ä8 ä10 (4)

ä2 ä7 ä8 ä4 ä3 (5)

ä10. ä7. ä4. ä8. ä7. ä2. (6)

în graficul prezentat în Fig. 2.1.2 sunt rute; două puncte de pe simbolul arc indică faptul că orientarea sa este neglijată, și anume, arcul este privit ca o muchie neorientate. De asemenea, calea sau traseul poate fi reprezentat printr-o secvență de noduri. De exemplu, calea (1), este după cum urmează: x2, x5, x4, x3, x5, x6. Uneori arcele graficului sunt atribuite numere, numit greutatea, costul sau lungimea arcului. În acest caz, graficul este numit un grafic cu muchii ponderate. Și în cazul în care greutatea atribuită vârfurile graficului, atunci vom obține un grafic cu noduri ponderate. În cazul în care greutatea atribuită coloanei și arcele și nodurile, atunci este pur și simplu numit prudent. Când căile considerând p reprezentat printr-o secvență de arce (ä1 ä2. äq), greutatea sa este luat numărul l (μ), egală cu suma greutăților tuturor arcelor din M, adică,

2.2 Algoritmul lui Dijkstra

Algoritmul lui Dijkstra construiește cel mai scurt calea care duce de la vârful sursă la alte vârfuri ale graficului (dacă este cazul).

În timpul funcționării, secvențial algoritmul marcat vârfuri examinate. Vârful a marcat ultimul (pentru moment) este situat mai aproape de partea de sus a originalului decât toate nemarcat, dar mai mult decât orice marcat.

marcat prima vârf inițial; următorul este probabil să fie marcat de vârful cel mai apropiat de sursa, și adiacente acesteia.

Să presupunem că la un moment dat a marcat mai multe vârfuri. drumul cel mai scurt Cunoscut lider de la sursa la început etichetate. Pentru fiecare dintre nodurile nemarcate face următoarele:

1. Luați în considerare toate arcele de conducere din nodurile marcate într-un singur nemarcată. Fiecare arc este ultimul arc de calea de la nodul inițial la nemarcați.

2. Din aceste căi mai scurte. Și apoi selectați cea mai scurtă dintre ele toate nodurile neetichetate și eticheta de sus, la care conduce.

Algoritmul se va opri atunci când toate nodurile sunt marcate accesibil.

Ca rezultat al algoritmului Dijkstra construiește un arbore de trasee mai scurte.

3 CARACTERISTICI DE LUCRU MEDIU

Când scrieți un program pentru a utiliza un mediu Microsoft Visual C ++ 6.0. Acest mediu vă permite să scrie aplicații în limbajul C ++.

Pe parcursul scrierii programului, toți operatorii și limbă oficială a C ++ evidențiate într-o culoare diferită pentru a le distinge de variabile definite de programator. Microsoft Visual C ++ 6.0 mediu conține un compilator încorporat.

Programul a fost creat în modul consolă - în modul care nu are o interfață grafică.

4 SOFTWARE IMPLEMENTARE

4.1 Descrierea algoritmului de proiectare și de program

Programul afișează calea cea mai scurtă dintre cele două vârfuri în grafic și lungimea acestuia.

Când porniți programul afișat pe ecran vi se solicită să introduceți greutățile de marginile graficului de încercare. Datele introduse de utilizator sunt afișate sub forma matricei adiacenta, în care muchiile nu există sunt notate cu zerouri. După coaste specificat este setat la 65535, care se presupune a fi infinit.

Următoarea etapă a programului se solicită să introduceți numărul de vârful, între care este necesar să se cunoască modul. Dacă butonul de pornire și de sfârșit nodurile coincid, un mesaj este afișat și funcționarea programului se încheie. În caz contrar, un Dijkstra algoritm direct, a cărui schemă este prezentată în Anexa B.

Rezultatul programului este de a afișa vârful prin care calea minimă, precum și producția de lungimea traseului. În cazul în care traseul dintre punctele date nu există - este afișat un mesaj.

4.2 Descrierea software-ului utilizat

Tabelul 4.2.1 Definirea variabilelor