Išplėstinė paieška
 
 
 
Pradžia>Informatika>Programavimas>Šakų ir ribų metodas
   
   
   
naudingas 0 / nenaudingas 0

Šakų ir ribų metodas

  
 
 
1234567891011121314151617181920212223
Aprašymas

Metodų maršrutui rasti trumpa apžvalga. Apėjimo maršruto suradimo metodų uždaviniai. Šakų ir ribų metodas. Atstumų matricos sudarymas. Viršūnių įvertinimas. Neperspektyvių kelių uždraudimas. Optimalaus maršruto atrinkimas. Metodo pavyzdys. Šakų ir ribų metodo algoritmas. Vartotojo instrukcija. Programos tekstas C++ Builder.

Ištrauka

Maršrutų suradimo metodus galima suskirstyti į dvi grupes: indeksinius ir matricinius. Be jų dar yra naudojami tinklų sintezės metodai.
Indeksiniai metodai leidžia surasti optimalius kelius tiek orientuotiems tiek ir neorientuotiems ryšio tinklo mazgams. Minimalus atstumas gali būti randamas bet kokiam orientuotam ar neorientuotam grafui, o maksimalus kelias naudojant indeksinį metodą gali būti rastas tik tinkliniam grafui neturinčiam kontūrų. Tais atvejais gali būti surastas kritinis kelias, kuris turi didelę reikšmę projektuojant ryšio tinklus.
Naudojant matricinius metodus optimalus kelias gali būti surastas taip pat tiek orientuotiems tiek neorientuotiems grafams su kontūrais ar be jų. Maksimalus kelias randamas tik orientuotiems grafams be kontūrų. Taip pat naudojant matricinius metodus dvi viršūnes turi jungti tik viena šaka. Jei viršūnes jungia daugiau kaip viena šaka tuomet reikalinga pertvarkyti tinklą. Tam pakanka iš keleto briaunų, jungiančių dvi bet kokias viršūnes viena kryptimi, palikti tik tą, kuri turi mažesnį svorį, jei reikia nustatyti min. ilgio kelią.
Matriciniuose metoduose skaičiavimo apimtis priklauso nuo grafo viršūnių skaičiaus. Naudojant matricinius metodus skaičiavimų apimtis auga kvadratine priklausomybe priklausomai nuo viršūnių skaičiaus. Indeksinių metodų skaičiavimo apimtis priklauso nuo lankų grafe. Todėl naudojant indeksinius metodus skaičiavimų apimtis nėra tokia didelė ir taip sparčiai neauga didėjant viršūnių skaičiui.
Visi indeksiniai metodai leidžia surasti optimalius kelius nuo vieno fiksuoto taško iki visų kitų. Naudojant matricinius metodus mes randame maršrutų atstumus tarp bet kurių dviejų viršūnių. Todėl matriciniais metodais gaunama galutinė informacija yra platesnė, suteikianti daugiau informacijos apie tinklą.
Lyginant su matriciniais, indeksiniai metodai paprastesni ir aiškiau galima matyti, kaip vykdomos atskiros operacijos. ...

Rašto darbo duomenys
Tinklalapyje paskelbta2006-05-11
DalykasProgramavimo praktikos ataskaita
KategorijaInformatika >  Programavimas
TipasPraktikos ataskaitos
Apimtis22 puslapiai 
Literatūros šaltiniai0
Dydis199.71 KB
AutoriusMarius
Viso autoriaus darbų8 darbai
Metai2006 m
Klasė/kursas4
Švietimo institucijaKauno Technologijos Universitetas
Failo pavadinimasMicrosoft Word Saku ir ribu metodas [speros.lt].doc
 

Komentarai

Komentuoti

 

 
[El. paštas nebus skelbiamas]

 
 
Ar šis darbas buvo naudingas?
Taip
Ne
0
0
Pasidalink su draugais
Pranešk apie klaidą