On 7 Lip, 12:19, Wit Jakuczun <w...@g...com> wrote:
> W dniu 2010-07-07 10:52, Mariusz Marszałkowski pisze:> On 7 Lip, 07:15, Maciej
Pilichowski
> > <P...@g...com>  wrote:
> >> On Tue, 06 Jul 2010 08:11:34 +0200, Wit Jakuczun
>
> >> <w...@g...com>  wrote:
> >>> Dopuszczając możliwość przyjechania w przedziale czasowym (np. rozkład
> >>> +/- 15min) problem staje się NP-Complete.
>
> >> Ale wtedy sie szukac czegos innego -- najmniej ryzykownego przejazdu o
> >> najkrotszym czasie. I wtedy zakladasz, ze przyjezdzasz te 15 minut po
> >> czasie.
>
> > Co to jest najmniej ryzykowny przejazd o najkrotszym czasie?
>
> Ja to zrozumiałem tak, że najmniej ryzykowny to taki, w którym zakładasz
> maksymalne spóźnienie. Stąd sugestia wzięcia max z każdego przedziału.

No tak, ciekawy dodatkowy parametr do uwzglednienia.

> > Jesli trzeba dotrzec w jakims przedziale czasowym, to ja bym
> > zalozyl ze koszt czasu spedzonego w podrozy jest znacznie
> > wiekszy niz czas przed jej rozpoczeciem i zakonczeniem. Wtedy
> > wystarczy wziac  najmniej kosztowne polaczenia poczawszy
> > od kazdego dopuszczalnego startu podrozy i z nich wybrac
> > optymalne.
>
> Nie zrozumiałem...

Mamy graf G w ktorym chcemy podrozowac. Rozszerzamy go o
dwa wierzcholki: przed_poczatek i po_koniec. Przed_poczatek
symbolizuje etap przed odbyciem podrozy, a po_koniec etap
po odbytej podrozy. Przed_poczatek to zwykle dosc komfortowy
etap, np. oczekiwanie w domu na autobus, wiec krawędzie łączące
go ze stacjami maja maly koszt, albo wrecz zerowy. Po_koniec
to sytuacja mniej komfortowa, gdyz oczekujemy i tracimy czas na
spotkanie, wiec krawedzie laczace ostatnia stacje z po_koniec
powinny cechowac sie jakims kosztem. Jednak czas spedzony
w podrozy jest najbardziej kosztowny, gdyz zarowno tracimy
czas i placimy za srodek transportu. Taka znaczna przewaga
kosztu podrozowania nad kosztem oczekiwania chyba pozwala
zadanie sprowadzic do takiego czegos:
1) Budujemy liste najmniej kosztownych tras dla kazdego mozliwego
rozpoczecia podrozy. Budujemy ta liste bez uwzglednienia
weirzcholkow przed_poczatek i po_koniec. Budowanie przerywamy
jesli poczatek podrozy jest po terminie w jakim chemy dotrzec.
2) Kazda utworzona trase zwiekszamy o koszt oczekiwania po
obu stronach
3) Podajemy trase o najmniejszym koszcie.

Chodzi o to, ze moze nie byc potrzeby analizowania wszystkich
tras ktore gwarantuja dotarcie w okreslonym przedziale. Pokonywanie
trasy jest kosztowne i chyba wystarczy z tras optymalnych wybrac takie
ktore mieszcza sie w przedziale.

Pozdrawiam