Pareigos
Donatas Domres
Užsakovas
Marius Tumėnas
Programuotojas
Gražina Gentvilaitė
Web programuotojas
Edita Ščerbaitė
Projektuotojas
Pakeitimų istorija
Data
Versija
Aprašymas
A utorius
2006-02-23
0.01
Matematinė analizė
Donatas Domres
Užduotis:
Artimiausio kaimyno grafo paieškos algoritmas.
Algoritmo tikslas:
Rasti:
Surasti maršrutą, kuriuo turi keliauti turistas, aplankant kiekvieną miestą tik po vieną kartą, kad jo nuvažiuotas kelias būtų trumpiausias.
Atvaizduoti:
Pavaizduoti trumpiausio kelio trajektoriją tarp esamų miestų.
Gauti:
Gauti trumpiausią atstumą pereinant visus miestus.
Parodyti:
Pavaizduoti grafiškai, trumpiausią kelią pereinant visus miestus.
Išspręsti:
Apskaičiuoti atstumą tarp kiekvieno miesto.
Matematinis sprendimas:
Metodo tikslas:
Surasti maršrutą, kuriuo turi keliauti turistas, aplankant kiekvieną miestą tik po vieną kartą, kad jo nuvažiuotas kelias būtų trumpiausias.
Duota:
Ne mažiau kaip du miestai, kurių vieta nurodyta dviem koordinatėmis.
Rasti:
Apskaičiuoti ir sudaryti atstumų tarp miestų matricą. Kurioje atsispindėtų atstumai tarp kiekvieno miesto.
Pavyzdžiai:
Norint apskaičiuoti ir rasti atstumą tarp kiekvieno miesto, sąlygoje turi būti duoti ne mažiau kaip du miestai, kurių kiekvieną apibūdintų dvi koordinatės. Šiuo atveju paimkime bet kokius tris miestus, kuriuos pažymėkime A (x1, y1), B (x2, y2), C (x3, y3). Atstumas tarp šių miestų A ir B sakykime lygus Sab, o atstumas tarp miestų A ir C lygus Sac, atitinkamai tarp B ir C miestų atstumas lygus Sbc. Taigi turėdami šiuos duomenis mes nesunkiai galime apskaičiuoti atstumą tarp kiekvieno miesto.
Tokiu būdu apskaičiavę atstumus tarp kiekvieno miesto sudarome atstumų matricą.
Trumpiausias maršrutas aplankant visus miestus tik po vieną kartą ir grįžtant namo randamas ieškant artimiausio miesto iki kurio būtų trumpiausias kelias. Kai jis randamas persikeliama į šį miestą ir ieškoma sekančio artimiausio šiam neaplankyto miesto. Kai taip aplankomi visi miestai, tada grįžtama į pradinį, o norint apskaičiuoti bendrą nukeliautą atstumą reikia kiekvieno persikėlimo metu susumuoti nueitą kelią, tai ir bus pats trumpiausias maršrutas, kuriuo galime aplankyti visus šiuos miestus.
Turistas atvažiavęs į Lietuvą nori aplankyti 5 didžiausius Lietuvos miestus. Vilnius, Kaunas, Klaipėda, Šiaulius ir Panevėžį, kuriuos vėliau tiesiog atitinkamai vadinsime miestais A, B, C, D ir E. Tačiau turistas nepažįsta Lietuvos, tik turi šių, norimų aplankyti miestų koordinates. A (5, 10), B (3, 11), C (9, 7), D (-5,...
Šį darbą sudaro 862 žodžiai, tikrai rasi tai, ko ieškai!
★ 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ą!
Mūsų mokslo darbų bazėje yra daugybė įvairių mokslo darbų, todėl tikrai atrasi sau tinkamą!
Panašūs darbai
Kiti darbai
Atsisiuntei rašto darbą ir neradai jame reikalingos informacijos? Pakeisime jį kitu nemokamai.
Pirkdamas daugiau nei vieną darbą, nuo sekančių darbų gausi 25% nuolaidą.
Išsirink norimus rašto darbus ir gauk juos akimirksniu po sėkmingo apmokėjimo!