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?

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.

Pozdrawiam

do góry

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.

> 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...

Pozdrawiam,
Wit

do góry

W dniu 2010-07-07 08:30, Wit Jakuczun pisze:
> W dniu 2010-07-07 07:15, Maciej Pilichowski pisze:
>> 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.
>>
> Jak szukasz najmniej ryzykownego to tak.
>
Modulo sytuacja gdy wybierając zawsze te 15 minut po czasie znajdziesz
rozwiązanie :).

Pozdrawiam,
Wit

do góry

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

do góry

On Wed, 7 Jul 2010 01:52:50 -0700 (PDT), Mariusz Marszałkowski
<m...@g...com> wrote:

>Co to jest najmniej ryzykowny przejazd o najkrotszym czasie?

Jak widzisz z rozkladu jazdy, ze masz 1 minute na przesiadke, ale tez
wiesz, ze pociagi spozniaja sie w graniach <0,15> minut, to takie
polaczenie odpuszczasz, z tego wzgledu ze moze nie zostac
zrealizowane.

milego dnia, hej
--
Moja wyprzedaz wszystkiego: ksiazki, plyty, filmy.
http://www.garaz.pol.pl/

do góry