Diskrētās struktūras datorzinātnes (1997)

Autors: KONSTANTĪNS GUSEVS

 

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).

SATURA RĀDĪTĀJS.

1.    Titullapa                                                               1

2.    Anotācija                                                              2

3.    Satura rādītājs                                                      3

4.    Uzdevuma nostādne                                            4

5.    Darba teorētiskais pamatojums                          4

6.    Paskaidrojumi programmas lietotājiem             5

7.    Kontrolpiemērs                                                    6

8.    Secinājumi                                                           8

9.    Literatūras saraksts                                              9

UZDEVUMA  NOSTĀDNE.

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.

DARBA  TEORĒTISKAIS  PAMATOJUMS.

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šā -

Neorientētā grafā matrica vienmēr ir simetriska attiecībā pret galveno diogonāli.

 

A=

Ja A ir blakus virsotņu matrica grafam G, tad elements (i,j) matricā A^k 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.

Dejkstras algoritms.

Š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: W_ij>=0.

Algoritmiska forma.

Dots: l  (Vi), W_ij>=0

1. solis             l (a)=0; l (Vi)=; Via; p=a

2. solis             ViT (p)

                        Visām Vi, kurām mainās iezīmes, maina tās.

                        l (Vi)=min[l (Vi), l (p)+ W (p,Vi)]

3. solis             l (V*)=min[l (Vi)]

                        Izvēlas no visām iezīmēm vismazāko, un to pārvērš par konstanti.

4. solis             l (V*), p=V* (uzskata par konstanti)

5. solis             Pā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ļ.

PASKAIDROJUMI PROGRAMMAS LIETOTĀJIEM

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 . 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 . Kad ievadīti visi dati, automatiski parādās vēlamais gala rezultāts. Lai turpinātu darbu, jānospiež jebkurš taustiņš.

KONTROLPIEMĒRS

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

Pēc pēdējā ievaddata automātiski parādās gala rezultāts.

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 pabeigt darbu, jānospiež jebkurš taustiņš.

            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ā.

LITERATŪRAS SRAKSTS.

Prof. Grundspeņķa lekcijas pieraksti – ’97.