| 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 * |
#3 · Zasláno: 7. 10. 2017, 21:40:25
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 |
#5 · Zasláno: 8. 10. 2017, 14:25:10
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 |
#6 · Zasláno: 8. 10. 2017, 17:13:17
A jak to mám uplatnit v praxi? A stačilo by to i bez přestupů.
|
||
| juriad Profil |
#7 · Zasláno: 10. 10. 2017, 12:24:52
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. |
||
|
Časová prodleva: 7 let
|
|||
0