Šakų ir ribų metodas

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.

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