Autor Zpráva
danaceks
Profil
Dobrý den, rád bych si udělal vyhledávač spojení. Řekněme, že chci jet třeba ze zastávky Masarykova na Palackého. Ono mi to poté najde, že mám jet třeba linkou 1 na náměstí Míru a přestoupit na linku 5 a dojet na Palackého. Víte někdo, jak na to?

Díky
pcmanik
Profil
danaceks:
Je to problém obchodného cestujúceho a keďže sa musíš pýtať tak ti ani neodporúčam sa snažiť to implementovať :) Pretože vytvoriť skutočne fungujúci a zároveň rýchly algoritmus je celkom náročné.
A minimálne budeš mať asi problém so získaním grafikonu (časového poriadku), polohy zastávok atď. Väčšinou tie dáta nebývajú verejné.

A keď sa môžem spýtať načo to chceš vytvárať? Žiadne z existujúcich riešení ti nevyhovuje?
juriad_
Profil *
Pcmanik: TSP je neco jineho. Tady jde o docela jednoduche prohledani grafu. Ale jak rikas, sehnani dat muze byt slozite.

Danaceks: pokud jsi o grafovych algoritmech neslysel, nepocitej s tim, ze neco rozumneho vytvoris. Pouzij existujici reseni.
danaceks
Profil
Chci si to spíš vymyslet, tj. udělat vlastní zastávky a nevázat se na existující. Je to spíš experiment, než něco veřejného. Chtěl jsem to zkusit...


spojeni.dpp.cz
tfl.gov.uk
Alphard
Profil
danaceks:
Podívej se na procházení grafu do šířky a zamysli se nad uvedeným příkladem třeba tady - algoritmy.eu/zga/pruchod-grafu/bfs-hledani-nejkratsi-cesty.
Skok jezdcem po šachovnici je dobrý základní příklad. V další fázi je třeba představit si reálnou mapu jako takovouto matici vzdáleností, jednotlivé hrany (vzdálenosti mezi zastávkami) ohodnotit a uvažovat časy na přestupy.
danaceks
Profil
A jak to mám uplatnit v praxi? A stačilo by to i bez přestupů.
juriad
Profil
danaceks:
Když ti dáme řešení, nepochopíš jej a budeš žadonit o každou jeho úpravu. Jedinou možností je, že se o to pokusíš sám a postupem času začneš chápat, jak to má fungovat.

V podstatě musíš přijmout terminologii grafů jako reprezentace stanic (vrcholů) propojených linkami (hrany). Pak se naučíš základní grafové algoritmy (procházení do šířky, do hloubky) a následně můžeš začít hledat nejkratší cestu.

Samozřejmě můžeš řešení nahackovat: každá linka bude prostý seznam stanic a ty budeš hledat pomocí in_array, zda linka spojuje počáteční a koncový bod. Můžeš dokonce najít linky obsahující počáteční a koncový bod a pak nad seznamy provést array_intersect. To umožní hledat cesty s jedním přestupem. Cokoli lepšího (víc přestupů, nejrychlejší cesty) vyžaduje použít grafové algoritmy.

Vaše odpověď


Prosím používejte diakritiku a interpunkci.

Ochrana proti spamu. Napište prosím číslo dvě-sta čtyřicet-sedm: