Newsgroup: it.comp.programmare
Titolo: Algoritmo "route finder"

Salve a tutti,
sto progettando un programmino per trovare la via più breve tra due
fermate di autobus.
Nel caso le fermate appartengano alla stessa linea, il problema è di una
semplicità assurda.
Ma... nel caso le fermate appartengano a diverse linee? Due, tre o
quattro linee?
Al momento sto costruendo un database delle fermate possibili: ad ogni
fermata faccio corrispondere un array contenente le linee passanti per
quella fermata.
Come avrete ben capito... il problema è nell'algoritmo da utilizzare. Ci
ho pensato a lungo, avevo pensato di utilizzare un algoritmo "shortest
path" (tipo Dijkstra), ma non ne vengo a capo, e dovrei modificare il
database...
Comunque mi basta solo una "spinta" verso la giusta direzione...
suggestions / comments are welcome!
Grazie a tutti.
David Paleino
-- 
Linux Registered User #334216
Get FireFox! >> 
http://www.spreadfirefox.com/?q=affiliates&id=48183&t=1
Staff >> 
http://www.debianizzati.org
 <<


Premessa:sono un quasi ingegnere dei trasporti,ma appassionato di
informatica....
Ciao, sempre della famiglia degli algoritmi di ricerca del percorso c'è
ldeque, che dicono sia più efficente di dijkstra e più facile da
realizzare....e poi perchè dovresti cambiare il database?Ad occhio un
database dove ogni fermata è una tabella ed ogni record rappresenta la linea
alla quale essa è connessa mi sembra un'ottima rappresentazione di una rete
di trasporto!

 di trasporto!
Ecco, appunto, il database non lo sto facendo così :)
Il database ha due tabelle (probabilmente ne aggiungerò altre dopo...
che so, con gli orari di partenza dai capolinea...):
mysql> show tables;
+--------------------+
| Tables_in_findabus |
+--------------------+
| tblFermate         |
| tblLinee           |
+--------------------+
2 rows in set (0.00 sec)
mysql> describe tblFermate;
+--------------+--------------+------+-----+---------+----------------+
| Field        | Type         | Null | Key | Default | Extra          |
+--------------+--------------+------+-----+---------+----------------+
| id           | int(3)       | NO   | PRI | NULL    | auto_increment |
| linee        | varchar(100) | YES  |     | NULL    |                |
| fermata      | varchar(100) | NO   |     |         |                |
| obbligatoria | tinyint(1)   | YES  |     | NULL    |                |
+--------------+--------------+------+-----+---------+----------------+
4 rows in set (0.02 sec)
mysql> describe tblLinee;
+---------+--------+------+-----+---------+----------------+
| Field   | Type   | Null | Key | Default | Extra          |
+---------+--------+------+-----+---------+----------------+
| id      | int(2) | NO   | PRI | NULL    | auto_increment |
| linea   | int(3) | NO   |     |         |                |
| inizio  | int(3) | NO   |     |         |                |
| fine    | int(3) | NO   |     |         |                |
| fermate | int(2) | NO   |     |         |                |
+---------+--------+------+-----+---------+----------------+
5 rows in set (0.00 sec)
mysql>
Il campo `tblFermate`.`linee` dovrebbe contenere un array con le linee
passanti per quel punto. Che so, una cosa del tipo (100,101,102,103) che
poi vado a "parsare" (che termine brutto) da PHP...
Mi suggerisci di creare il database come dici tu? Ossia una tabella per
ogni fermata? Mi pare un po' una cosa esagerata... considerando che ci
sono circa 100 linee (
www.amat.pa.it
), considerando che ogni linea ha
almeno una fermata "univoca" (cioè per cui solo quella linea passa...
alcune linee non ne hanno neppure una, altre ne hanno molte...), avrò un
database con almeno 100 tabelle... Oo
Al limite, un'altra idea che mi sta venendo proprio adesso, è fare una
tabella per ogni linea... così si mantiene "piccolo" (sì, si fa per
dire) il numero (~100)... e ogni record rappresenta una fermata, con un
campo per gli eventuali "incroci" su quella fermata.
Saluti,
David


poi vado a "parsare" (che termine brutto) da PHP...
Ma cosě per sapere come si va dalla fermata X alla fermata Y diventi matto,
posto che sia possibile (manca, mi pare, qualunque informazione sulla
topologia).
Mi sembra che ti serva, almeno, una tabella delle tratte:
tratte
+-----------+--------+------+-----+---------+----------------+
| Field     | Type   | Null | Key | Default | Extra          |
+-----------+--------+------+-----+---------+----------------+
| id        | int(2) | NO   | PRI | NULL    | auto_increment |
| linea     | int(3) | NO   |     |         |                |
| n° tratta | int(3) | NO   |     |         |                |
| da_fermata| int(3) | NO   |     |         |                |
| a_fermata | int(3) | NO   |     |         |                |
|...        |        |      |     |         |                |
|...        |        |      |     |         |                |
+-----------+--------+------+-----+---------+----------------+
Inoltre, il concetto di "via piů breve" presuppone una qualche metrica: Km,
minuti, numero di fermate... in qualche modo devi attribuire un peso ad
ogni tratta.
Ciao.

 Ciao.
Grazie.


 che so, con gli orari di partenza dai capolinea...):
Di solito per rappresentare una rete si usa un metodo detto "grafo", fatto
da nodi e archi (risp. pallini e linee). Un nodo rappresenta una fermata, un
arco è il collegamento tra due nodi.
In questo modo con due tabelle rappresenti tutta la rete, ovvero una che
contiene i nodi e una che contiene gli archi...la prima idea che mi viene in
mente:
Nodi(NomeNodo)
Archi(NodoIn,NodoOut,Costo,ID)
    Foreign Key (NodoIn,NodoOut)-->Nodi(NomeNodo)
Linee(NomeLinea,Nodo)
    Foreign Key (Nodo)-->Nodi(NomeNOdo)
Così associ ad ogni linea le sue fermate, e ad ogni fermata le linee che ci
fermano...
Se sei agli inizzi con il db, allora ti consiglio di cercarne uno schema più
semplice da usare con i vari algoritmi di ricerca del percorso, se invece
sei già a buon punto con i dati....magari con qualche query riesci a
ricostruirti i dati come ti servono....per quanto ne so comunque per gli
algoritmi di ricerca del percorso serve una rappresentazione della rete come
insieme di archi-nodi.....in che linguaggio stai programmando?

 in che linguaggio stai programmando?
Vorrei fare il tutto in PHP + MySQL, sia perché mi trovo molto a mio
agio col PHP, sia perché credo sia una soluzione molto portabile.
L'unica cosa che non mi piace di questa soluzione è l'installazione di
un webserver, php e mysql e la loro configurazione...
Un'altra soluzione potrebbe essere c# e sqlite...



Azz, php lo conosco molto molto poco....
guardando il sito dell amat, ho visto che le pagine delle linee sono ben
formattate, quindi potresti far fare a un programmino tipo c# il parsing
della pagina e fargli riempire a lui il db....se vuoi ho una cosa simile in
java

il concetto di "tratta"... se è come l'ho inteso io, ovvio.
Se non sai quanto pesa un arco o (secondo la metrica scelta) quanti archi
ci sono tra A e B, come fai a calcolare quanto pesa l'intero percorso tra A
e B? il "concetto di tratta" c'è per forza fin dall'inizio nel tuo
ragionamento, quello che mancava (o non era soddisfacentee) era la
*rappresentazione* del concetto.
Ciao.

 Ciao.
Ciao,


 quattro linee?
Se hai tempo e voglia ti consiglio questa lettura:
http://en.wikipedia.org/wiki/Graph_theory
Riguarda la teoria dei grafi nella quale puoi trovare la soluzione
oppure una chiave di lettura dei software in circolazione.
Ciao
Oreste