Praktikos ataskaitos
Šakų ir ribų metodas
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.
Komivojažerio uždaviniai yra skirstomi į simetrinius ir nesimetrinius. Simetriniams priskiriami uždaviniai, kuriuose atstumai tarp bet kurių dviejų punktų i ir j yra lygus atstumui nuo j iki i, t.y. Cij = Cji. Kai ši sąlyga netenkinama, uždavinys yra nesimetrinis.
- kuris prasideda ir baigiasi nurodytoje viršūnėje;
- būtų aplankyti visi N - 1 mazgai ir tik po vieną kartą;
- bendras maršruto ilgis...
Šį darbą sudaro 4218 žodžiai, tikrai rasi tai, ko ieškai!
- 1. Metodų maršrutui rasti trumpa apžvalga 3
- 2. Apėjimo maršruto suradimo metodų uždaviniai 3
- 3. Šakų ir Ribų metodas 4
- 3.1 Atstumų matricos sudarymas 4
- 3.2 Viršūnių įvertinimas 4
- 3.3 Neperspektyvių kelių uždraudimas 5
- 3.4 Optimalaus maršruto atrinkimas 5
- 3.5 Metodo pavyzdys 6
- 4. Šakų ir ribų metodo algoritmas 11
- 5. Vartotojo instrukcija 12
- 6. Programos tekstas C++Builder 5 14
- 7. Programos algoritmas 25
- 8. Išvados 26
- 9. Literatūra 26
★ Klientai rekomenduoja
Šį rašto darbą rekomenduoja mūsų klientai. Ką tai reiškia?
Mūsų svetainėje pateikiama dešimtys tūkstančių skirtingų rašto darbų, kuriuos įkėlė daugybė moksleivių ir studentų su skirtingais gabumais. Būtent šis rašto darbas yra patikrintas specialistų ir rekomenduojamas kitų klientų, kurie po atsisiuntimo įvertino šį mokslo darbą teigiamai. Todėl galite būti tikri, kad šis pasirinkimas geriausias!
Norint atsisiųsti šį darbą spausk ☞ Peržiūrėti darbą mygtuką!
- Programavimo praktikos ataskaita
- 23 psl., (4218 ž.)
- Word failas 584 KB
- Lygis: Universitetinis
Atsisiųsti šią praktikos ataskaitą
Mūsų mokslo darbų bazėje yra daugybė įvairių mokslo darbų, todėl tikrai atrasi sau tinkamą!
Panašūs darbai
Kiti darbai
Privalumai
Darbo pakeitimo garantija
Atsisiuntei rašto darbą ir neradai jame reikalingos informacijos? Pakeisime jį kitu nemokamai.
Gauk 25% nuolaidą
Pirkdamas daugiau nei vieną darbą, nuo sekančių darbų gausi 25% nuolaidą.
Greitas aptarnavimas
Išsirink norimus rašto darbus ir gauk juos akimirksniu po sėkmingo apmokėjimo!
Atsiliepimai
