Pievienot darbus Atzīmētie0
Darbs ir veiksmīgi atzīmēts!

Atzīmētie darbi

Skatītie0

Skatītie darbi

Grozs0
Darbs ir sekmīgi pievienots grozam!

Grozs

Reģistrēties

interneta bibliotēka
Atlants.lv bibliotēka
3,49 € Ielikt grozā
Gribi lētāk?
Identifikators:538052
 
Autors:
Vērtējums:
Publicēts: 15.04.2009.
Valoda: Latviešu
Līmenis: Augstskolas
Literatūras saraksts: 4 vienības
Atsauces: Nav
Laikposms: 2000. - 2010. g.
SatursAizvērt
Nr. Sadaļas nosaukums  Lpp.
  ANOTĀCIJA    4
1.  UZDEVUMA NOSTĀDNE    4
2.  DARBA TEORĒTISKAIS PAMATOJUMS    5
2.1  Bināras attieksmes    5
2.2  Deikstra algoritma realizācija    6
3.  INFORMĀCIJA PROGRAMMAS LIETOTĀJAM    7
3.1.  Bināras attieksmes    7
3.2.  Deikstra algoritma realizācija    8
4.  KONTROLPIEMĒRS    10
4.1.  Bināras attieksmes    10
4.2.  Deikstra algoritma realizācija    11
5.  SECINĀUMI    14
6.  LITERATŪRAS SARAKSTS    15
7.  PIELIKUMS    16
Darba fragmentsAizvērt

Īsako ceļu meklēsanai grafā plaši pielieto Deikstras algoritmu. Deikstra algoritma uzdēvums ir orientetā, neorientetā vai jauktā grafā V atrst īsako ceļu no uzdotas vīrsotnes parejās virsotnēs.
Deikstra risinājums.(1959.g)
Algoritms lieto 3 masīvus no N (=grafu virsotņu skaitu) skaitļu katrs. Pirmais masīvs A satūr iezīmes ar divām vērtībam: 0(virsotne vel nav apskatīta) un 1(virsotne jau apskatīta); otrs masīvs B satūr attalumus – tekošo īsako attalumu no līdz blakus vīrsotnei; trešais masīvs satūr vīrsotņu numurus – k-tais elements l[k] ir priekšpedejas vīrsotnes numurs uz tēkoso visīsāko ceļuno Vi uz Vk. Attālumu matrica w[i,k] uzdod loku garumu w[i,k]; ja tādu loku nav, tad w[i,k] tiek piešķīrts lielais skaitlis B, kas vienads ar “tehnisko bezgalību”.
Lai izpildītu algoritmu vajag N reizes apskatīt masīvs B no N elementiem, tātād Deikstra algoritmam ir taisnstūra saražģitības pakāpe: O(n2). Piekām Deikstra algoritms ir efektīvs tikai pie pizitīviem svāriem w[i,k]0;
Sākotnējo iezīmju piešķiršana
1.solis l(a)=0 un tā ir konstante
l(k)=
via
p=a
Iezīmju maiņa
2.1solis Vi   (i)
l(k)=min
[l(k), l(i)+w[i,k]] (Visām virsotnēm kuras pieder i attēlam ar maināmām iezīmēm maina iezīmi saskaņā ar šo rindiņu)
Iezīmju pārvēršana konstantē
3.solis. Starp virsotnēm ar maināmam iezīmem atrast tāduvirsotni v* ,kurai spēkā ir nosacījums: l(v*)=min l(k) , uzskatot šo iezīmi par minimālo p=v*
4.solis. Pāriet uz 2 soli, ja vēl ir virsotnes ar maināmām iezīmēm. …

Autora komentārsAtvērt
Darbu komplekts:
IZDEVĪGI pirkt komplektā ietaupīsi −5,48 €
Materiālu komplekts Nr. 1133507
Parādīt vairāk līdzīgos ...

Atlants

Izvēlies autorizēšanās veidu

E-pasts + parole

E-pasts + parole

Norādīta nepareiza e-pasta adrese vai parole!
Ienākt

Aizmirsi paroli?

Draugiem.pase
Facebook

Neesi reģistrējies?

Reģistrējies un saņem bez maksas!

Lai saņemtu bezmaksas darbus no Atlants.lv, ir nepieciešams reģistrēties. Tas ir vienkārši un aizņems vien dažas sekundes.

Ja Tu jau esi reģistrējies, vari vienkārši un varēsi saņemt bezmaksas darbus.

Atcelt Reģistrēties