NOVINKA - Online rekvalifikační kurz Python programátor. Oblíbená a studenty ověřená rekvalifikace - nyní i online.
Hledáme nové posily do ITnetwork týmu. Podívej se na volné pozice a přidej se do nejagilnější firmy na trhu - Více informací.

Diskuze: Vyhledání spojení v MHD

V předchozím kvízu, Test znalostí C# .NET online, jsme si ověřili nabyté zkušenosti z kurzu.

Aktivity
Avatar
kotenl
Člen
Avatar
kotenl:2.11.2012 3:46

Zdravim, mám pár dotazů ke své aplikaci na které hodlám začít dělat.
Má aplikace by měla být určena pro Win Phone případně Desktop a měla by být shopna vyhledat optimální zastávku (z hlediska času, vzdálenosti) pro start a cíl v síti MHD mezi zadanými geografickými pozicemi Pardubického kraje. K dispozici bych měl mít kompletní jízdní řády.

Představuji si to tak, že uživatel zadá výchozí a cílovou polohu a aplikační logika spočítá a vyhodnotí nejlepší spoj a uživateli nabídne optimální zastávku pro nástup.
Má hlavní otázka se týká mapových podkladů. K dispozici mám ShapeFile všech komunikací Pardubického kraje, otázka je, jak tam nějak kloudně nacpat pozice zastávek(které ani neznám). Zda by pro tyto účely nebylo lepší využít nějakých offline upravovatelných mapových podkladů.

Dále je nutno zohledňovat případně i zobrazovat cestu uživatele k vyhledané optimální zastávce - mezi uživatelem a optimální zastávkou by mohla existovat například řeka a uživatel by ji byl logicky nucen obcházet, čímž by se optimální stala nějaká bližší. Bude tedy potřeba podle algoritmu vyhledat minimální cestu od uživatele k zastávce (a zároveň od cílové zastávky do cílové polohy).

Potřeboval bych nějakým směrem nakopnout, je to jako začarovaný kruh.

 
Odpovědět
2.11.2012 3:46
Avatar
David Hartinger
Vlastník
Avatar
Odpovídá na kotenl
David Hartinger:2.11.2012 13:01

Grafové algoritmy jsou obecně docela husté a je za tím dost matematiky. Existují již vymyšlené a popsané algoritmy, které určitě vygooglíš. Projekt mi ale přijde trochu nereálný, zaprvé existuje idos.cz, zadruhé je to práce pro tým lidí.

Nahoru Odpovědět
2.11.2012 13:01
New kid back on the block with a R.I.P
Avatar
matesax
Tvůrce
Avatar
Odpovídá na kotenl
matesax:2.11.2012 13:44

No já tu vidím další příspěvek na UI... :)

 
Nahoru Odpovědět
2.11.2012 13:44
Avatar
kotenl
Člen
Avatar
kotenl:2.11.2012 13:47

Díky za reakci :) Grafové algoritmy řeší obor teorie grafů, konkrétně v tomto případě se jedná o hledání minimální cesty orientovaným grafem (midifikace Dijkrstrova algoritmu), v tom by snad nebyl až zas takový problém.
Jedná se o projekt do školy (případná bakalářka), rozhodně nechci konkurovat idosu :) Projekt mi přijde vhodný například pro geocaching (známe cílovou polohu keše a chci se sockou dostat co nejblíže). Na druhou stranu bych se nerad do něčeho pustil a po dvou měsících zjistil, že problém je mnohem obtížnější než jsem si myslel.

 
Nahoru Odpovědět
2.11.2012 13:47
Avatar
David Hartinger
Vlastník
Avatar
Odpovídá na kotenl
David Hartinger:2.11.2012 14:13

S nějakou elementární teorií ohledně grafů jsem obeznámen, Dijkrstr mi také něco říká. No pokud to máš do školy, tak by to určitě šlo. Celý problém je asi jen o zpracování existujících dat (nevím, v jakém to je formátu) a napsáním algoritmu, co by hledal cestu. Zastávky bys tam nějak doklikal, to by byla práce na odpoledne, ne?

Nahoru Odpovědět
2.11.2012 14:13
New kid back on the block with a R.I.P
Avatar
kotenl
Člen
Avatar
kotenl:2.11.2012 14:57

Těch zastávek je tušim něco okolo 1500 :)) Zkusim se zeptat na dopravním podniku, snad budou mít jejich pozice.
Jinak ty jízdní řády budou nejspíš v textové formě a mapy mám ve formátu ShapeFile, což je asi ten největší problém, protože s tim vůbec neumim pracovat.
Jdu se probrat v anglické dokumentaci. Zatim díky moc za snahu.

 
Nahoru Odpovědět
2.11.2012 14:57
Avatar
Lunil
Člen
Avatar
Lunil:2.11.2012 15:37

Dalsia alternativa algoritmu by mohla byt matica najkratsich vzialenosti. Nieco take sme mali aj my v skole a dalo sa to pomerne pohode zvladnut. Algoritmus uz len podla urcitych pravidiel prehladaval 2rozmerne matice, to je pohodicka.
Co sa tyka zobrazenie, mozno by si mohol vyuzit googlemaps. Ale to len za podmienok, ze by si riesil aplikaciu on-line. Tam podla bodov cesty (co by si mohol mat tiez zapisane v suboroch(zeme­pisnych sirok a dlzok), cize trasa spoja HMD) vytvoril pozliepanu ciaru kadial by ten spoj isiel.

Nahoru Odpovědět
2.11.2012 15:37
Neustalym resetovanim pocitaca ho dovedieme do pozadovaneho stavu. O:-)
Avatar
kotenl
Člen
Avatar
kotenl:3.11.2012 7:28

Problém matice vzdáleností je v tom, že se musí spočítat vzdálenost mezi všemi vrcholy grafu. No a když mám přes 75000 hran a okolo 50000 vrcholů, tak si nedovedu představit jak by asi taková matice vypadala :D Navíc taková matice nám neříká nic o tom přes jaké vrcholy nejkratší cesta vede.
Částečně(pro zobrazení cesty) by ta aplikace klidně online být mohla.

 
Nahoru Odpovědět
3.11.2012 7:28
Avatar
David Hartinger
Vlastník
Avatar
Odpovídá na kotenl
David Hartinger:3.11.2012 11:34

Aha. A co si zadání ulehčit aby byly vrcholy grafu jen zastávky? Vidím jako hodně velký problém hledat nejbližší zastávku z libovolného bodu na mapě, přesně třeba kvůli té řece. To už pak není algoritmus co hledá mezi vrcholy, ani nevím, jak by se to dělalo, neznám nic k teorii motion-planningu v nematicové ploše.

Editováno 3.11.2012 11:34
Nahoru Odpovědět
3.11.2012 11:34
New kid back on the block with a R.I.P
Avatar
Kit
Tvůrce
Avatar
Odpovídá na David Hartinger
Kit:3.11.2012 11:42

V nematicové ploše se to dělá přes R-stromy.

Nahoru Odpovědět
3.11.2012 11:42
Vlastnosti objektů by neměly být veřejné. A to ani prostřednictvím getterů/setterů.
Avatar
kotenl
Člen
Avatar
kotenl:17.3.2014 21:08

Ahoj, už je to nějaký ten čas co jsem práci zdárně dokončil.
Jen uvedu že samotný algoritmus vyhledávání spojení je založený na myšlence vyhledávání minimální cesty v hranově ohodnoceném, orientovaném grafu. Jedná se o silnou modifikaci Dijkstrova algoritmu s prvky heuristiky - modifikace se týká zejména v nutnosti zahrnout do výpočtu případné přestupy a pěší přesuny na sousední spoje.

 
Nahoru Odpovědět
17.3.2014 21:08
Děláme co je v našich silách, aby byly zdejší diskuze co nejkvalitnější. Proto do nich také mohou přispívat pouze registrovaní členové. Pro zapojení do diskuze se přihlas. Pokud ještě nemáš účet, zaregistruj se, je to zdarma.

Zobrazeno 11 zpráv z 11.