Razlika između inačica stranice »Problem trgovačkog putnika«
(Bot: Automatski unos stranica) |
m (bnz) |
||
| Redak 1: | Redak 1: | ||
Problem trgovačkog putnika''', [[logistika|logistički]] problem iz svakodnevnog života, rješava se u [[teorija grafova|teoriji grafova]]. Sličan je [[problem kineskog poštara|problemu kineskog poštara]].<ref name="E-math"/> | |||
Rješava ga se tako što se pokušava naći [[šetnja (teorija grafova)|šetnju]] kojom će se barem jednom proći kroz svaki [[vrh (teorija grafova)|vrh]] na grafu te se vratiti na početni vrh, učinivši to na najkraći mogući način, koristeći se [[usmjereni graf|usmjerenim]] ili [[neusmjereni graf|neusmjerenim grafom]]. Mogu biti zadane i udaljenosti među vrhovima, pa se traži i da je ukupna prijeđena udaljenost najmanja.<ref name="E-math">[http://e.math.hr/math_e_article/br14/fosner_kramberger math.e, hrvatski matematički elektronički časopis] Maja Fošner i Tomaž Kramberger: ''Teorija grafova i logistika'' br. 14, ISSN ISSN 1334-6083 (pristupljeno 23. prosinca 2019.)</ref> | Rješava ga se tako što se pokušava naći [[šetnja (teorija grafova)|šetnju]] kojom će se barem jednom proći kroz svaki [[vrh (teorija grafova)|vrh]] na grafu te se vratiti na početni vrh, učinivši to na najkraći mogući način, koristeći se [[usmjereni graf|usmjerenim]] ili [[neusmjereni graf|neusmjerenim grafom]]. Mogu biti zadane i udaljenosti među vrhovima, pa se traži i da je ukupna prijeđena udaljenost najmanja.<ref name="E-math">[http://e.math.hr/math_e_article/br14/fosner_kramberger math.e, hrvatski matematički elektronički časopis] Maja Fošner i Tomaž Kramberger: ''Teorija grafova i logistika'' br. 14, ISSN ISSN 1334-6083 (pristupljeno 23. prosinca 2019.)</ref> | ||
Trenutačna izmjena od 04:59, 24. ožujka 2022.
Problem trgovačkog putnika, logistički problem iz svakodnevnog života, rješava se u teoriji grafova. Sličan je problemu kineskog poštara.[1]
Rješava ga se tako što se pokušava naći šetnju kojom će se barem jednom proći kroz svaki vrh na grafu te se vratiti na početni vrh, učinivši to na najkraći mogući način, koristeći se usmjerenim ili neusmjerenim grafom. Mogu biti zadane i udaljenosti među vrhovima, pa se traži i da je ukupna prijeđena udaljenost najmanja.[1]
Usporedba je s poštarom koji se kreće ulicama (u matematičkom modelu to je graf) te ima zadaću dostaviti pošiljke u svaku kuću (vrhovi dotičnog grafa), u najkraćem veremenu te se vratiti u poštu (polaznu točku). Poštar želi potrošiti što manje vremena, truda i novca da bi izvršio svoju zadaću, upotrijebivši najkraću rutu.[1]
Primjena je npr. kod planiranja ruta i redoslijeda prijevoza robe od skladišta do trgovina.[1]
Izvori
- ↑ 1,0 1,1 1,2 1,3 math.e, hrvatski matematički elektronički časopis Maja Fošner i Tomaž Kramberger: Teorija grafova i logistika br. 14, ISSN ISSN 1334-6083 (pristupljeno 23. prosinca 2019.)