Poszukuję programu do wyznaczania najkrótszej przez punkty


(Lukaszxp) #1

Witam,

poszukuję programu, czy może raczej strony internetowej, która po wrzuceniu do niej adresów wyznaczy mi najbardziej optymalną trasę aby osiągnąć po drodze każdy z nich. Muszę w jedno popołudnie dostać się do około 30 adresów w jednym mieście - może kurierzy korzystają z czegoś takiego?

Dzięki za pomoc

Pozdrawiam


(Pablo_Wawa) #2

A nawigacja samochodowa nie ma takiej funkcjonalności? Podajesz punkt początkowy i końcowy oraz punkty pośrednie i program powinien coś tam zaproponować. Może i są takie nawigacje na PC lub w internecie (Google Maps), które tak potrafią?


(floyd) #3

Tylko 30 adresów?

Zdecydowanie za dużo :slight_smile:

Problem który cię interesuje to tzw. problem komiwojażera znany od dawna.

Możesz na ten temat poczytać w sieci na wielu stronach.

Przykładowo np. tutaj:

http://edu.i-lo.tarnow.pl/inf/utils/002_roz/ol027.php


(Lukaszxp) #4

O kurcze, chyba nie przypomnę sobie C++ na tyle szybko, żeby napisać program do rozwiązania mojego problemu. W takim razie rozwiążę to empirycznie i na oko, dzięki za pomoc i przy okazji za ciekawostkę! :slight_smile:


(SilberPunkt) #5

Na targeo.pl możesz wyznaczać trasę przez punkty pośrednie ale chyba 30-tu się nie da dodać (nie próbowałem).

:roll:


(Pablo_Wawa) #6

Podziel trasę (miasta) na kila części (regionów) i dla nich (osobno) wyznacz taką optymalną trasę. A potem je samodzielnie połącz w całość - chyba nie musisz mieć najoptymalniejszej trasy dla tych 30 miast! Zrób kilka prób, zobacz jakie łączne odległości wychodzą, I pamiętaj, że trasa najkrótsza to nie znaczy najszybsza czy najtańsza.