IDOS a veci souvisejici

[Martin.Postulka at cerge.cuni.cz]

Pavel Satrapa napsal:
>Presto si neodpustim revolucni poznamku. Mne onehdy napadlo, ze by
>pravdepodobne on-line hledani ani nemuselo byt nutne. Pocitam, ze rozsah
>zeleznicni site a pocet vlaku bude takovy, ze by se to dalo pri vhodne
>datove reprezentaci vsechno predpocitat predem a pri on-line "hledani"
>pak uz jen sahnout do odpovidajiciho souboru, vybrat z nej prislusnou
>informaci a zformatovat do podoby WWW stranky.

Na prvni pohled to pusobi jako pitomost, ale to byva pruvodnim jevem mnoha
genialnich napadu. :-))

Spis to mozna neni nejpresnejsi a nejpruhlednejsi formulace. Jak jste si
to vlastne presne predstavoval? Jestli jste mel na mysli, ze trasa (respektive
mnozina tras) muze byt statickou funkci dvojice koncovych stanic, tudiz
lze vysledky ulozit a indexovat je temito dvojicemi, pak verim,
ze by to bylo mozne a zvlaste pokud vysledky budou n-tice pouzitych trati
(ve smyslu jizdniho radu) (viz nize odpoved Vaclavu Cernemu) mohlo by to byt
i relativne nenarocne. (kdovi, jestli si nejakou takovou iterpretaci topologie
ten algoritmus nepomaha?)
Podstatne mene jasno mam u tech vlaku a casu. Tusim sice, ze by se zase
dalo indexovat podle casovych intervalu, ale nevidim zadnou vyhodu zvlast
u frekventovanejsich trati. Zda se mi rezie srovnatelna, respektive algoritmy,
ktere si dovedu pro obe reseni predstavit, napadne podobne.

Mozna by to bylo jasnejsi, kdybyste popsal, jak si predstavujete praci
algoritmu pri tom predpocitavani.

Hlavne mi asi uplne uniklo, v cem vidite vyhody statickeho reseni, respektive
podle ceho posoudit, kdy a proc je staticke reseni vhodne. Nebo bych to aspon
rad slysel explicitne a podrobneji. :-)
U te cache si posouzeni funkcnosti dokazu predstavit lip, ale v podstate ani
u jednoho nevim, jak s jistotou urcit, ze to vyhodne bude, dokud se to nespusti.


Vladislav Cerny napsal:
>nyni zahrnuje IDOS 7726 stanic a 18603 vlaku.
>Jiste se tady najde nejaky odbornik pres kombinatoriku,
>aby Vam dostatecne zduvodnil, ze pri zahrnuti i ostatnich
>parametru spojeni (datum, cas, prestupy, typy vlaku, apod.)
>se dojde k tak astronomickemu poctu predpocitanych souboru,

Pripustme, ze u tech vlaku to treba opravdu nepujde, ale nabizena kontrola
pres kombinatoriku nas jednoduse a presne dostane nejvys k nejnepriznivejsi
variante pri pouziti nejhloupejsiho mozneho reseni.

Myslim, pokud jsem pozorne cetl, ze slo o predpocitana data, nikoli o
predgenerovane stranky. Tedy o castecne mezivysledky, jestli to tak muzu
nazvat. Aspon doufam. Jinak mi to nedava smysl. :-)

V takovem pripade vase cisla nerikaji vubec nic o realne slozitosti,
protoze jiste uznate, ze 7726*7725 tras bude zobrazeno do podstatne
mensiho kartezskeho soucinu trati.

I ten hrozivy pocet vlaku se podstatne snizi, kdyz kombinujete jen vlaky,
ktere prislusnou trati jedou.

Bylo by to samozrejme podstatne slozitejsi spocitat. Nedokazu odhadnout
(a nevim jestli stoji za to se o to pokouset) jestli bychom takto
dosli k splnitelnym narokum, ale vase puvodni odhady jsou extremne
nadsazene.

Martin Postulka