[C] Calcolo itinerari

[agosteeno]

Salve a tutti, posto questo messaggio per chiedervi qualche consiglio riguardo un progettino che devo svolgere. Sostanzialmente devo scrivere (in c come da titolo) un modulo che, data un orario, una data, un origine e una destinazione calcoli un (in realta' vari) itinerario che colleghi questi luoghi tramite mezzi pubblici a partire dalla data e dall'orario specificati. Gli orari e le tratte sono contenuti in opportuni file di testo, dal quale il modulo deve attingere per fare i calcoli.
Io pensavo di inizare cercando l'origine considerata tra i vari file e considerare le possibili destinazioni e, contemporaneamente, cercare la destinazione tra i file e considerare le possibili origini. A questo punto, in maniera "ricorsiva" continuare con i risultati di queste operazioni fino a quando non si incontrano origine e destinazione.
Quello che mi rende perplesso e' che il costo puo' essere spropositato sia in termini di memoria che di tempo di elaborazione, anche se i file dai quali attingere fossere piccoli.
Vi ringrazio in anticipo per l'eventuale collaborazione, accetto qualsiasi tipo di consiglio...

[british]

prova a guardare:

http://en.wikipedia.org/wiki/Dijkstra's_algorithm

http://en.wikipedia.org/wiki/Bellman-Ford_algorithm

potrebbero fare al caso tuo.

ciao!

british

[agosteeno]

Grazie per la risposta. Naturalmente avevo gia' preso in considerazione questi algoritmi. Sopratutto quello di Dijkstra, in quando prevedo di nn avere costi negativi nel grafo, rendendo quindi inutile usare quello di Bellman-Ford.
Il problema che maggiormente mi preoccupa e' il costo computazionale: infatti il programma potenzialmente potrebbe ricevere centinaia se nn migliaia possibili "archi". Infatti potrebbe ricevere il percorso di tutti i treni, i pullman, le navi e gli aerei d'italia. A questo proposito pensavo infatti di fare la ricerca sia dal punto di partenza che, al contrario diciamo, dal punto di origine, in modo da poter bloccare il tutto quando si incrociano i risultati.
Inoltre con Dijkstra trovo i cammini minimi nel grafo, ma nn e' necessariamente questo il criterio che piu' mi interesserebbe. Potrei sia cercare il cammino piu' breve (inteso come orario) che quello con meno scambi, ma potrei anche restituire itinerari simili, senza particolari differenze di costo, giusto per dare un'alternativa (per intenderci: origine Firenze, destinazione alghero: it1: firenze-olbia aereo, olbia-alghero treno... it2: firenze-pisa treno, pisa-alghero aereo).

[WarDuck]

Prova a dare un'occhiata all'algoritmo A*.

[agosteeno]

Nn mi e' ben chiaro come funziona. In particolare nn ho capito cosa si intende per stima euristica. In pratica mi viene chiesto di stimare la distanza fino alla destinazione. Ma nn riesco a capire come poter implementare questa cosa nel mio problema. Attualmente mi sembra piu' semplice da implementare l'algoritmo di Dijkstra...

[gugoXX]

Originariamente inviato da agosteeno

Salve a tutti, posto questo messaggio per chiedervi qualche consiglio riguardo un progettino che devo svolgere. Sostanzialmente devo scrivere (in c come da titolo) un modulo che, data un orario, una data, un origine e una destinazione calcoli un (in realta' vari) itinerario che colleghi questi luoghi tramite mezzi pubblici a partire dalla data e dall'orario specificati. Gli orari e le tratte sono contenuti in opportuni file di testo, dal quale il modulo deve attingere per fare i calcoli.
Io pensavo di inizare cercando l'origine considerata tra i vari file e considerare le possibili destinazioni e, contemporaneamente, cercare la destinazione tra i file e considerare le possibili origini. A questo punto, in maniera "ricorsiva" continuare con i risultati di queste operazioni fino a quando non si incontrano origine e destinazione.
Quello che mi rende perplesso e' che il costo puo' essere spropositato sia in termini di memoria che di tempo di elaborazione, anche se i file dai quali attingere fossere piccoli.
Vi ringrazio in anticipo per l'eventuale collaborazione, accetto qualsiasi tipo di consiglio...

Costruisici la matrice delle adiacenze e poi passi tutto a Dijkstra.
Poiche' immagino che tu non sappia cosa siano, ti consiglio di leggere bene, anche solo su Wikipedia, di cosa si tratta.

[agosteeno]

Mmm. Sostanzialmente era quello che volevo fare io anche se effettivamente nn avevo pensato di metterlo come matrice di adiacenza. Infatti anche se so' di cosa si tratta, nn le ho mai usate in pratica, quindi nn mi e' venuta in mente. Grazie per il consiglio. Inizio a lavorare e se ho altri dubbi vi ricontattero'.

[agosteeno]

Salve di nuovo a tutti. Siccome alla fine era agosto ed ero in vacanza nn ho piu' fatto nulla. Ora pero' le vacanze sono finite e quindi mi rimetto a lavoro. Ora che ci ho pensato su' un po' meglio, nn posso risolvere il problema con le matrici di adiacenza: infatti la matrice potrebbe risultare troppo grande. Gia' se dovessi considerare solo i treni e tutte le possibili destinazioni risulterebbe dell'ordine delle decine di migliaia... L'unico approccio che mi viene in mente e' di costruire un grafico volta per volta e scegliere in qualche modo come costruire la parte successiva...

[fracarro]

Originariamente inviato da agosteeno

Salve di nuovo a tutti. Siccome alla fine era agosto ed ero in vacanza nn ho piu' fatto nulla. Ora pero' le vacanze sono finite e quindi mi rimetto a lavoro. Ora che ci ho pensato su' un po' meglio, nn posso risolvere il problema con le matrici di adiacenza: infatti la matrice potrebbe risultare troppo grande. Gia' se dovessi considerare solo i treni e tutte le possibili destinazioni risulterebbe dell'ordine delle decine di migliaia... L'unico approccio che mi viene in mente e' di costruire un grafico volta per volta e scegliere in qualche modo come costruire la parte successiva...

Riguardo la dimensione della matrice, hai problemi di memoria? Pur avendo milioni di celle non dovrebbe occupare molto spazio in memoria.

L'algoritmo di Dijkstra può essere implementato in diversi modi (la chiave sta nella struttura dati utilizzata per implementare la coda a priorità). Ad ogni modo l'algoritmo è in grado di risolvere in pochi secondi problemi su grafi contenenti anche milioni di nodi.

[agosteeno]

Ho capito quale era il problema. Io ero convinto di dover scorrere i file con gli orari ogni volta che dovevo effettuare una computazione. Come ben capite in questo modo sarebbe uscito un grafo esageratamente grande ogni volta, specie se si considerano i treni, gli autobus, aerei ecc di tutta italia se nn d'europa!!! In realta' devo "costruire" il grafo una volta per tutte all'avvio e poi usare sempre quello, quasi come fosse un database... ora il problema si riduce di molto. Penso si possa realizzare senza troppi problemi con un algoritmo classico... grazie per l'aiuto cmq...

ah, anche se l'algoritmo usato dovrebbe essere veloce, la struttura uscirebbe molto molto grande... andrebbe ad essere potenzialmente infinita... in ogni caso dovrei anche considerare che queste operazioni nn siano effettuate una alla volta, ma potrebbero essere parecchie contemporaneamente... infatti questo programma e' pensato come il nucleo di un'applicazione web o cose simili, alla quale possono essere fatte tante richieste...

[banryu79]

Originariamente inviato da agosteeno

ah, anche se l'algoritmo usato dovrebbe essere veloce, la struttura uscirebbe molto molto grande... andrebbe ad essere potenzialmente infinita... in ogni caso dovrei anche considerare che queste operazioni nn siano effettuate una alla volta, ma potrebbero essere parecchie contemporaneamente... infatti questo programma e' pensato come il nucleo di un'applicazione web o cose simili, alla quale possono essere fatte tante richieste...

Non sono un eseperto, ma rifelttendonci penso siano due cose distinte (l'esecuzione dell' algoritmo con prduzione di un output e la gestione di un servizio che soddisfi richieste da più client).

Cioè io qui vedo un'entità software che è il tuo algoritmo.
Prende un input, elabora, sputa un output.

Poi vedo un'altro strato/entità software, che usa il tuo algoritmo ma il cui scopo è ricevere le richieste dei client e usare la migliore strategia/politica di gestione per rispondere a tutti nel modo più veloce.
Possono esserci diversi modi; sicuramente dovrai gestire l'accodamento delle richieste da soddisfare, ma potrebbe essere anche il caso di eseguire il caching dei risultati già calcolati per non doverli ripetere (con quale criterio non lo so, è tutto da decidere in base al contesto).

[agosteeno]

mi sono spiegato male... nn devo produrre tutto il lavoro, ma solo il modulo interno diciamo, quello che fa' la computazione vera e propria. Solo che siccome questo verra' usato in maniera intensiva, devo curare particolarmente l'aspetto della velocita' della computazione (e naturalmente anche lo spazio utilizzato)...