Algoritmų sudarymas ir analizė. 2 laboratorinis darbas

Ištrauka

Algoritmų sudarymas ir analizė
2 laboratorinio darbo ataskaita

1. Laboratorinio darbo užduotis:
Naudojant programavimo algoritmų sudarymo metodą, atlikti laboratorinio darbo užduotį.
Laboratorinio darbo užduotis susideda iš dviejų dalių:
a) Naudojant dinaminio programavimo rekursiją (skaidant uždavinį į mažesnius uždavinius),
rasti trumpiausius kelius nuo visų grafo viršūnių iki nurodytos grafo viršūnės k. Grafe negali
būti neigiamų ciklų.
b) Pritaikyti a) varianto sprendimą 11.14 užduotyje nurodytam grafui, kuriame reikia rasti
trumpiausius kelius nuo visų grafo viršūnių iki 6-tosios grafo viršūnės.
2. Laboratorinio darbo realizacija:
Laboratoriniam darbui atlikti naudojama programavimo kalba – JAVA. Programavimo
aplinka – IntelliJ IDEA 15.0.3.
3. Užduoties analizė:
Kaip nurodyta užduotyje, užduoties sprendimui reikia naudoti dinaminio programavimo
principą – uždavinį skaidyti į mažesnius uždavinius. Kadangi šios užduoties esmė – trumpiausiojo
kelio paieška grafe, todėl visa užduotis, taikant dinaminio programavimo principą, sprendžiama
palaipsniui: pirmiausia skaičiuojami trumpiausių kelių trumpiausi atstumai, susidedadantys
daugiausiai iš vienos briaunos. Toliau ieškomi visi trumpiausi atstumai, susidedantys bent iš dviejų
briaunų ir t.t.