Determinare ruta intr-o retea de transport in comun

[Sim Master]

Trebuie sa implementez un algoritm care determina cel mai bun traseu dintr-un punct A intr-un punct B intr-o retea de trasnport in comun. Cel mai bun traseu este dat de durata pana la destinatie si de numarul de autobuze / tramvaie schimbate pe parcurs (ar mai fi si alti factori, dar in prima faza doar astea).

Problema este ca nu prea stiu exact cum si de unde sa incep. Am ceva cunostinte despre algoritmii pentru determinarea costului unui drum intr-un graf, dar ma cam depasesc urmatoarele probleme:

- cum ar trebui sa construiesc graful si drumurile dintre noduri (statii) astfel incat rezultatul sa nu contina un traseu in care se schimba mai mult de 3 autobuze?

- teoretic ar trebui ca fiecare nod sa aiba cate o muchie catre restul nodurilor pentru ca poti merge si pe jos intre statii, dar daca fac asta mi se pare ca ma complic foarte mult si ar aparea si alte probleme.

Nu stiu daca am formulat chiar corect sau inteligibil, dar si in capul meu e o varza acuma.

Ceva pareri sau idei legate de cum se poate rezolva problema si ce algoritm s-ar potrivi cel mai bine?

P.S.: nu se pune problema sa folosesc un api care ofera astfel de informatii. nu despre asta e vorba

[blech]

gandeste-te ce conditii trebuie sa indeplineasca ruta perfecta si de acolo incepi sa construiesti...

parerea mea care NU SUNT PROGRAMATOR este: o faci cu backtracking pentru ca nu sunt asa de multe variante de traseu si amesteci acolo si un arbore de cost minim (unde o sa ai problema pentru ca valorile pentru minim trebuie sa reflecte cumva si pretul si viteza cu care ajungi acolo)

daca citesti un manual de algoritmi sigur o sa-ti vina o idee mai buna decat a mea...

[tjt]

Dijkstra e algoritmul de a stabili costul minim de la un nod la altul si cred ca e cel mai bun mod de a rezolva problema ta.

[passfig]

Dijkstra e algoritmul de a stabili costul minim de la un nod la altul si cred ca e cel mai bun mod de a rezolva problema ta.

A* este mai bun. Avantajul pe care il are A* este ca se bazeaza pe o functie pe care o dai tu. Functia asta o faci in functie de cerintele pe care le ai in problema si ea va spune care cale este mai buna (care dintre arcele pe care le poti folosi este mai buna la un moment dat). Este si mai rapid in general.

Legat de conditiile pe care le impune problema. Cea cu 3 schimbari ar trebui sa fie simpla, daca este nevoie de un al 4-lea autobuz nu explorezi mai departe pe calea respectiva. Mersul pe jos strica putin treaba (adica nu ma prind acum de cum ai putea folosi A*), dar poti modela chestia asta fie cu backtracking fie cu algoritmul floyd-warshall. Floyd-Warshall iti gaseste cele mai rapide rute intre toate nodurile grafului. Poti considera ca intre doua noduri ai doua muchii: una cu autobuzul alta pe jos, aia pe jos are sa zicem un cost de 4 ori mai mare, dar uneori se poate sa fie mai buna, pe cazul asta cred ca F-W merge bine.

Backtrack are complexitate in cel mai bun caz 2^n adica cu vreo 20 de noduri deja te-ai dus nasol, poti sa optimizezi dar tot e nasol. F-W are N^3, deci ruleaza decent cu cateva sute de noduri (depinde in ce scri solutia).

Sper ca am inteles ce vrei si nu am spus balarii, corectati-ma daca am gresit. Iti recomand paginile astea:

A*

Floyd-Warshall

Edited July 19, 2015 by passfig

[Sim Master]

Din ce am mai cautat si eu pe net majoritatea raspunsurilor sunt in favoarea lui A* cand vine vorba de algoritmul potrivit.

@passfig Face sens ce ai scris acolo si cred ca o sa si incep sa scriu ceva cod pornind de la ideile tale. Urmeaza sa vad de ce ma mai lovesc.

Pana acum n-am inceput sa scriu nimic ca tot incercam sa-mi imaginez cum ar arata graful si conexiunile dintre noduri, iar problema cea mai mare o am la partea cu mersul pe jos. Cred ca trebuiesc luate in considerare urmatoarele cazuri cand generez graful:

- trebuie creata o muchie care sa uneasca nodul de start si nodul de finish (e ok pentru distantele foarte scurte in care nu are rost sa iei autobuzul, dar ineficient pentru distantele mari)

- pe langa muchiile care reprezinta drumul de la o statie la alta, ar mai trebui creata si cate o muchie de la o statie pana la nodul finish (asta pentru cazurile in care e mai convenabil sa te dai jos intr-un punct si sa mergi pe jos, in loc sa schimbi autobuzul sau sa continui cu el)

Is curios cat va dura sa calculeze toate treburile astea. Aplicatia trebuie sa fie una mobile si ma gandeam ca, din lejeritate, sa fac un web app cu phonegap iar tot algoritmul sa fie in javascript, dar cred ca pica ideea si o sa-l implementez in java.

[Sim Master]

Revin cu un update. Am progresat putin, cu toate ca nu-s inca la rezultatul pe care il vreau.

Am inceput prima oara cu algoritmul A* dar nu a fost potrivit pentru ce am nevoie. Modul lui de functionare este de a merge din aproape in aproape pana ajunge la nodul destinatie, ori mie imi trebuie sa parcurga toate rutele iar la sfarsit sa decida care e mai buna. Asa am ajuns sa folosesc Dijkstra pentru problema asta. Mi s-a parut mai potrivit, chiar daca e putin mai lent pentru ca parcurge toate combinatiile.

La implementare am modificat putin functia care genereaza costul dintre doua noduri spunandu-i sa mai creasca costul daca autobuzul a fost schimbat, sau sa returneze un cost infinit daca urmeaza sa treaca la un al treilea autobuz.

Cu toate ca rezultatul este cat de cat acceptabil, eu vreau ca la sfarsit sa am ruta care contine cele mai putine autobuze schimbate, chiar daca costul (timp sau distanta) este mai mare. Conditiile pe care le-am pus mai sus doar descurajeaza schimbarea mai multor autobuze, dar nu garanteaza faptul ca imi va returna ruta mai lunga dar in care se poate ajunge cu un singur autobuz.

Apreciez daca mai aveti si alte pareri sau idei.