STUDIJU DARBS MĀCĪBU PRIEKŠMETĀ
‘DISKRĒTĀS STRUKTURAS DATORZINĀTNĒS’
Programmas rakstīta valodā Borland Pascal 7.01 un domāta DOS operētājsistēmām. Apraksts rakstīts Word 97. Kursa darbā ietilpst programmas apraksts, darba teorētiskais pamatojums, paskaidrojumi tās lietotājiem, kontrolpiemērs, secinājumi un semestra laikā veiktie laboratorijas darbi. Kursa darba apraksts satur 9 lapaspuses.
Programmas rakstītas divos failos. Pirmajā daļā iespējams apskatīs šādas grafa pieraksta formas:
•blakusvirsotņu matricu;
•sarakstu struktūra (ar attslēgmasīvu) ieejošiem lokiem.
Otrajā daļā – Dejkstras algoritma realizācija (īsākā ceļa meklēšana starp grafa virsotnēm).
1.Titullapa1
2.Anotācija2
3.Satura rādītājs3
4.Uzdevuma nostādne4
5.Darba teorētiskais pamatojums4
6.Paskaidrojumi programmas lietotājiem5
7.Kontrolpiemērs6
8.Secinājumi8
9.Literatūras saraksts9
1.Parādīt šādas grafa pieraksta formas:
- blakusvirsotņu matricu;
- sarakstu struktūra (ar attslēgmasīvu) izejošiem lokiem.
2.Īsākā ceļa atrašana ar Dejkstras algoritmu.
Blakus virsotņu matrica.
Blakus virsotņu matrica A ir tāda matrica, kura elementi var pieņemt divas vērtības.
Matrica ir kvadrātiska. Izmērs ir kopas |V|x|V|. Orientētiem grafiem ir divas lokālās pakāpes:
A=
•Ieejošā -
•Izejošā -
A=
Ja A ir blakus virsotņu matrica grafam G, tad elements (i,j) matricā Ak ir vienāds ar dažādu ceļu skaitu, kas ved no i-tās virsotnes uz j-to virsotni.
Loku saraksts ir kopa, kurā katrs loks ir aprakstīts ar virsotnes pāri.
Šis algoritms izmanto maināmo iezīmju piešķiršanas tehniku. Algoritma izpildes gaitā katrai virsotnei tiek piešķirta iezīme. Iezīme norāda īsāko ceļu no fiksētās sākuma virsotnes uz apskatāmo virsotni – augošo robežu, un algoritms ir iteratīvs. Katrā iterācijā tikai viena iezīme kļūst konstanta un šī iezīme norāda īsākā ceļa garumu.
Slēgts grafs, kur lokiem ir uzlikti svari (piešķirtas skaitliskās vērtības). Svari – var būt kilometri, izmaksas, laiks u.t.t. Svariem ir jābut pozitīviem, nedrīkst būt loki ar negatīvo svaru: Wij>=0.
Dots: l (Vi), Wij>=0
1. solisl (a)=0; l (Vi)= ; Vi a; p=a
2. solisVi T (p)
Visām Vi, kurām mainās iezīmes, maina tās.
l (Vi)=min[l (Vi), l (p)+ W (p,Vi)]
3. solisl (V*)=min[l (Vi)]
Izvēlas no visām iezīmēm vismazāko, un to pārvērš par konstanti.
4. solisl (V*), p=V* (uzskata par konstanti)
5. solisPāriet uz 2.soli, ja ir virsotnes ar maināmām iezīmem. Pretējā gadijumā algoritms tiek beigts.
l (Vi’) + W (Vi ’,Vi) = l (Vi)
Īsākā ceļa atrašana, kāpjoties pa vienai virsotnei atpakaļ.
SVBVM.EXE (izveidot blakusvirsotņu matricu un noteikt lokālās pakāpes):
No sākuma jāievada virsotņu skaits no 8 līdz 12 un loku skaits no 10 līdz 15. Tālāk tiek ievadīti dati, aiz katra ievaddata spiežot <ENTER>. Kad ievadīti visi dati, automatiski parādās vēlamais gala rezultāts. Lai turpināt darbu, jānospiež jebkurš taustiņš.
DEJEXTRA.EXE (īsākā ceļu meklēšana)
No sākuma jāievada virsotņu skaits no 8 līdz 12 un loku skaits no 10 līdz 15. Tālāk tiek ievadīti dati, aiz katra ievaddata spiežot <ENTER>. Kad ievadīti visi dati, automatiski parādās vēlamais gala rezultāts. Lai turpinātu darbu, jānospiež jebkurš taustiņš.
Lai varētu izpildīt pirmo uzdevumu jāpalaiž fails ‘svbvm.exe’. No sākuma jāievada virsotņu skaits [8-12] un loku skaits [10-15]. Un tad jāsāk ievadīt ievaddati no kuras virsotnes, uz kuru.
Virsotņu skaits? [8..12]: 8
Loku skaits? [10..15]: 10
Uz: 1 2 3 4 5 6 7 1 4 2
No: 2 3 4 5 6 7 8 5 8 5
Blakusvirotņu matrīca:
0 1 0 0 1 0 0 0
0 0 1 0 1 0 0 0
0 0 0 1 0 0 0 0
0 0 0 0 1 0 0 1
0 0 0 0 0 1 0 0
0 0 0 0 0 0 1 0
0 0 0 0 0 0 0 1
0 0 0 0 0 0 0 0
Srakstu struktūra ar atslёgmasīvu ieejošiem lokiem:
AM: 2 4 5 7 8 9 10 10
M: 2 5 3 5 4 5 8 6 7 8
Lai varētu izpildīt otro uzdevumu jāpalaiž fails ‘dejexstra.exe’ Sākumā ievada virsotņu un loku skaitu, un tad sāk ievadīt ievaddatus (izejošās, ieejošās virsotnes un svaru). Beigās parādās īsākais ceļš un šā ceļa garums.
Ievadīt virsotņu skaitu [8..15]: 8
Ievadīt loku skaitu [10..15]: 10
Sākuma virsotne Beigu virsotne Svars
1. 1 2 3
2. 2 3 4
3. 3 4 5
4. 4 5 6
5. 5 6 7
6. 6 7 7
7. 7 8 4
8. 8 3 2
9. 4 7 1
10. 8 3 10
Īsākais ceļš: 1 - 2 - 3 - 8
Ceļa garums: 17
SECINĀJUMI.
Abas programmas pilda uzdevuma prasības, protams, pie korektiem ieejas datiem. Tās ir diezgan ērtas lietošanā. Programmu “Svbvm.exe” var izmantot grafa pieraksta formas apskatīšanai. Programmu “Dejextra.exe” var izmantot īsāko ceļu noteikšanai starp virsotnem grafā.
Prof. Grundspeņķa lekcijas pieraksti – ’97.
