Minimo percorso

Il cliente che si chiama Tom di nome e Tom di cognome ci chiede l'analisi funzionale ed un preventivo per la realizzazione di un'applicazione web che:

  1. Conservi in un data base l'elenco dei più di 8.000 comuni d'Italia, con capacità di raggrupparli per provincia e per regione
  2. Di ciascun comune conosca i comuni limitrofi e le rispettive distanze chilometriche tra di essi
  3. Dati due comuni a piacere, sia capace di calcolare il minimo percorso per andare da uno all'altro, attraversando comuni intermedi. Il calcolo del minimo percorso va realizzato implementando l'Algoritmo di Dijkstra.
grafo minimo percorso
In prima release si ritiene accettabile che il data base possa contenere soltanto i 41 comuni della provincia di Bari ed i 10 comuni della provincia di Barletta-Andria-Trani.

Il progetto ci interessa perché ci consente un percorso interdisciplinare tra le materie:
  • Informatica (analisi del data base ed implementazione dell'algoritmo, applicabilità nell'ambito del turismo e della logistica)
  • Sistemi per l'elaborazione e la trasmissione delle informazioni (l'instradamento dei pacchetti su internet utilizza algoritmi simili?)
  • Calcolo delle probabilità, statistica e ricerca operativa (è un problema bellino di ricerca operativa)
sfruttabile anche in sede di prova orale.

Complessità media (poche pagine, ma cazzuto l'algoritmo).

Motto:

Per andare dove dobbiamo andare, per dove dobbiamo andare?


Chi della ditta 5IB si offre per dare una mano a Totò e Peppino?


Pubblico il grafo di prova con cinque località ed i dati reali, utile per il test.

Commenti

  1. Ciao a tutti,
    sono Giovanni Caputo, ex alunno del Marconi(sez. B).
    Volevo segnalare a chi fosse interessato a questo progetto che su internete potete trovare maggiori info e varie versioni di questo algoritmo. Inoltre, volevo segnalarvi delle dispense abbastanza semplici, con esempi, dove è applicato l'algoritmo per la creazione delle tabelle di routing

    http://www.di.uniba.it/~reti/dispense/liv_rete.pdf

    Buon lavoro a tutti!

    RispondiElimina
  2. a me piacerebbe fare questo progetto però mi spaventa 1 po' l'algoritmo dell'instradamento :-)

    RispondiElimina
  3. Nell'a.s. 2007/2008 per gli allenamenti alla gara nazionale delle Olimpiadi di Informatica, l'ex alunno Vincenzo Lucente ha studiato diversi tipi astratti di dati e i relativi principali algoritmi, tra i quali i grafi e la ricerca del cammino minimo.
    Vincenzo ha studiato l'algoritmo generale ed implementato l'algoritmo di Bellman-Ford-Moore.
    Questo si distingue da quello di Dijkstra per la struttura utilizzata per mantenere l'elenco dei nodi da visitare: in quello di BFM si utilizza una coda, in quello di D una coda con priorità realizzata con una lista non ordinata.

    L'algoritmo in sè non è particolarmente complesso, una volta acquisita una certa familiarità di strutture come liste, alberi, grafi e code con priorità.

    Sono molti gli aspetti che si possono affrontare e approfondire "per colpa" di questo algoritmo, oltre quelli già presentati da Pierangelo: dal punto di vista della programmazione, i tipi astratti di dato (ADT), la definizione di un'algebra per ogni ADT, differenti realizzazioni per lo stesso ADT, algoritmi di visita, programmazione orientata agli oggetti, studio della complessità dei problemi (perchè l'algoritmo di Dijkstra è più veloce di quello di BFM?), sotto quali condizioni si può usare un algortimo (quando non posso usare Dijkstra e quindi devo usare BFM?),...

    Il lavoro degli allenamenti è pubblicato nel sito dedicato alle OII, nella sezione e-learning del sito del Marconi:
    http://www.marconibari.it/corsi/course/view.php?id=32

    In particolare, segnalo la tesina presentata da Vincenzo agli esami di Stato 2008: "E-learning: apprendimento online di strutture dati e tecniche di programmazione per le Olimpiadi di Informatica", cap. 3 e 4, su alberi e grafi e il nostro algoritmo. Il cap. 5 è incompleto, in realtà si parla solo di heap, una possibile struttura per la realizzazione di una coda con priorità:
    http://www.marconibari.it/corsi/mod/resource/view.php?id=317

    RispondiElimina
  4. Ho trovato l'algoritmo, sviluppato in linguaggio C, qui.

    E' l'approccio che cercavo perché lavora su una matrice di input che è come me l'ero immaginata.

    Compitino:
    Preparare matrice Bari, Giovinazzo, Bitonto, Molfetta, Terlizzi
    Provare il programma

    Se va bene, tradurre i commenti in italiano

    Tradurre il C in PHP

    Buon lavoro!

    RispondiElimina
  5. Su Dijkstra, consiglio a tutti la lettura di questo brano autobiografico: "Un umile programmatore".

    RispondiElimina

Posta un commento

Post più popolari