Calculând căile cele mai scurte cu datele extrase dintr-o bază de date

Așadar, trebuie să creez un serviciu web care să comunice cu Androidul meu cerere. În aplicația mea Android clientul alege două puncte de pornire și sosire acest punct de două vor fi trimise la serviciul meu web pentru a găsi autobuzul care are cea mai scurtă cale între ele. Am o problemă cu web-ul service.

Am încercat să folosesc algoritmul lui Dijkstra pentru a găsi calea cea mai scurtă între două puncte. Pentru a testa algoritmul Dijkstra, trebuie să extrag datele de la un Baza de date MySQL și nu mi-a pus corect în algoritmul meu. Nu știu cum pot totuși să fac asta.

În baza mea de date am două tabele care conțin ruta autobuzului (numărul autobuzului) cod (cod stație), pt_arret (nume stație). Există un alt tabel care conține codul locației (stația id), latitudinea și longitudinea și distanță (este distanța dintre o stație și o stație care precede.

0
(Îmi pare rău pentru mistacke de ortografie, pentru că eu nu vorbesc engleza foarte fluent)
adăugat autor olfa, sursa
Vă rugăm să aveți timp să formatați, să vă valorificați și să puneți punctua întrebarea corectă. Mulțumiri.
adăugat autor NPE, sursa

1 răspunsuri

Trebuie să creați o structură care vă va permite să utilizați algoritmul lui Dijkstra. Pentru a face acest lucru, trebuie să citiți toate datele relevante din baza de date. Trecerea de la date relaționale la orientare obiect este întotdeauna dificilă.

În mod ideal, doriți să utilizați un singur SQL simplu selectați pe tabel pentru a obține datele. Optimizarea este dificilă. O singură instrucțiune selectă poate să apuce un milion de rânduri aproape la fel de repede cum poate să apucă un rând; un select va primi un milion de rânduri mai repede decât 10 selectează va apuca 10 rânduri (în experiența mea). Însă recrutarea prea multor rânduri neefectuate ar putea dura prea mult dacă conexiunea DB este lentă (are o lățime de bandă îngustă).

Utilizați Hărți (TreeMap sau HashMap) pentru a urmări ce ați citit, astfel încât să puteți găsi obiecte "staționare" care au fost deja citite și plasate în structura dvs. și adăugați conexiuni la ele.

Odată ce structura de date este configurată în memorie, încercați să o păstrați cât mai mult timp posibil pentru a limita întârzierile de a revedea baza de date.

Fii atent la memoria și calendarul tău. Sunteți în pericolul de a alerga prea lent pentru utilizatorii dvs. sau de a scăpa de memorie. Trebuie să acordați atenție performanței (care nu pare a fi o necesitate comună în aceste zile). Am făcut câteva sugestii, dar nu știu cu adevărat ce se va întâmpla cu hardware-ul și cu datele dvs. (De exemplu, citirea DB nu poate fi la fel de lentă cum suspectez.)

Sper că acest lucru vă ajută. Dacă nu ați mai făcut așa ceva înainte, aveți mult de lucru și învățați înainte de voi. Am lucrat la un program important de genul acesta (dar, de asemenea, am scris la DB), și m-am simțit ca și cum am înota în amonte tot drumul.

Adăugarea:

Ceea ce doriți în memorie este un set de stații (obiecte de clasă de stație) și rute (obiecte de clasă rute). Fiecare stație ar avea toate datele de care aveți nevoie pentru a descrie o stație, inclusiv locații. Din punct de vedere critic, ar fi nevoie și de o identitate. Stațiile ar trebui să meargă într-un TreeMap folosind ID-ul ca cheie. (Aceasta este prejudica mea, mulți oameni ar folosi un HashMap.)

Fiecare traseu va avea referințe la cele două stații pe care le leagă, o distanță sau un timp de călătorie și orice alte informații necesare.

Fiecare post de radio va de asemenea conține o listă de rute care o referă. Aș recomanda un LinkedList pentru flexibilitate. (În acest caz, ArrayList este capabil să piardă o mulțime de spațiu cu elemente de matrice neutilizate.) Veți dori să citiți posturile din db, apoi citiți informațiile despre traseu. Pe măsură ce citiți informațiile fiecărei rute, creați obiectul Route, localizați cele două stații, adăugați referințe la acestea pe Route, apoi adăugați listele de rute pentru ambele posturi.

Acum, pentru fiecare stație puteți vedea toate rutele care o părăsesc și apoi puteți vedea toate stațiile pe care le puteți ajunge cu o singură călătorie cu autobuzul. De la aceste stații, puteți lucra pe tot parcursul rețelei. Această structură este într-adevăr o "rețea restrânsă", dacă doriți să vă gândiți la ea în acest fel.

Aplicarea algoritmului lui Dijkstra - sau orice alt algoritm - este destul de simplă. Veți dori diferite steaguri pe stații și rute (câmpurile din clasele Stație și Rută) pentru a urmări care noduri (posturi) și conexiuni (rute) pe care le-ați utilizat deja în diverse scopuri. S-ar putea ajuta să desenați hartă (începeți cu una mică!) Pe o foaie de hârtie pentru a urmări ceea ce face codul dvs. Experiența mea a fost că este nevoie de un cod foarte mic pentru a face toate acestea, dar este nevoie de o gândire atentă.

0
adăugat
Îmi pare rău, dar vreau să știu: să creez acest lucru care sunt clasele și funcțiile de care am nevoie. pentru că este prima mea experiență, și nu știu cum să analizez această problemă.
adăugat autor olfa, sursa
există cineva care ma sfătuit să fac așa:
adăugat autor olfa, sursa
Tres este unul care ma sfatuit sa fac asa: Pentru a folosi algoritmul lui Dijkstra trebuie sa pregatim o matrice de distanta. Este o gamă bidimensională de distanțe între toate stațiile. Soluția preferată este: 1. încărcarea ambelor tabele în memorie ca obiecte de date POCO. 2. Calculați distanța matrice (dacă puteți - creați o matrice de sparce pentru a evita utilizarea memoriei mari). 3. apelați algoritmul lui Dijkstra .... deci unde ar trebui să extrageți datele din MySQL (în ce clasă)? Îmi pare rău, dar am nevoie de ajutor :(
adăugat autor olfa, sursa
vă mulțumesc foarte mult pentru sfatul dvs. :) Voi încerca să-l traducă în cod, dar vă rugăm să știți dacă un tutorial care mă poate ajuta să nu hésitate să-mi trimită url, pentru că eu sunt începător și nu știu dacă am o pot construi de la zero. oricum, voi încerca să vă mulțumesc din nou :)
adăugat autor olfa, sursa
vă mulțumesc foarte mult pentru ajutorul dvs. :) Sper că găsesc o soluție cât mai curând posibil pentru că am pierdut o mulțime de timp în cercetare și raportul după 11 zile: ((.... vă mulțumesc din nou :)
adăugat autor olfa, sursa
@olfa: Cu ce ​​zonă aveți nevoie de ajutor? Nu cunosc serviciile web și Android suficient de bine pentru a vă ajuta. Aș putea fi un pic mai specific despre SQL, Java și implementarea algoritmului lui Dijkstra.
adăugat autor RalphChapin, sursa
@olfa: Îmi pare rău, dar nu te înțeleg.
adăugat autor RalphChapin, sursa
@olfa: Sfat util. Am adăugat interpretarea mea la răspunsul meu. Ar trebui să vă aducă un pic mai departe.
adăugat autor RalphChapin, sursa
@olfa: Nu știu cu adevărat orice tutoriale. Pentru un exemplu, puteți să vă uitați la acest lucru: ( binpress.com/app/roadgraph/316). Este un site comercial, dar puteți descărca codul "RoadGraph" gratuit pentru uzul propriu. Este mod mai complicat decât orice ai nevoie, dar cu un efort puteți găsi nodurile și a vedea cum sunt legate.
adăugat autor RalphChapin, sursa