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

Izdevīgi: šodien akcijas cena!

Parastā cena:
3,49
Ietaupījums:
0,38 (11%)
Cena ar atlaidi*:
3,11
Pirkt
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: 2004.g. - 2005.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 −4,49 €
Materiālu komplekts Nr. 1133507
Parādīt vairāk līdzīgos ...

Nosūtīt darbu e-pastā

Tavs vārds:

E-pasta adrese, uz kuru nosūtīt darba saiti:

Sveiks!
{Tavs vārds} iesaka Tev apskatīties interneta bibliotēkas Atlants.lv darbu par tēmu „Diskrētās struktūras datorzinātnēs. Bināras attieksmes un ceļu meklēšana grafā”.

Saite uz darbu:
https://www.atlants.lv/w/538052

Sūtīt

E-pasts ir nosūtīts.

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
Twitter

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