Strumenti Utente

Strumenti Sito


matematica:asd:asd_19:progetto_19

Progetto di ASD, anno accademico 2019/20

Questo progetto sostituisce l'esame scritto del corso. Utilizza i dati dei trasporti locali della città di Parigi e chiede di realizzare un “city route planner”, che permette di stabilire il percorso tra due fermate fornite come interrogazione. I passi concettuali sono i seguenti:

  1. utilizzare i dati per la città di Parigi [dettagli di seguito];
  2. scegliere un giorno della settimana;
  3. prendere i mezzi di trasporto disponibili quel giorno per muoversi in città;
  4. interrogare i dati con input: due qualunque fermate A e B, un orario P di partenza da A, un tempo limite T massimo di percorrenza;
  5. stimare l'orario di arrivo in B partendo da A al tempo P, purché sia rispettato il tempo limite P+T
  6. elencare i mezzi per arrivare in orario (come stimato nel punto 5)

I dati per Parigi possono essere scaricati accedendo alle pagine di Microsoft Teams per il corso, nella sezione “files”, c'è il folder denominato “Progetto_ASD_2019_2020”.

La descrizione dei campi utilizzati in tali dati si trova nel seguente articolo, a partire dalla pagina 10: Kujala, R., Weckström, C., Darst, R. et al. A collection of public transport network data sets for 25 cities. Sci Data 5, 180089 (2018).

I dati forniti sono presi da un data set reale e non sono tutti strettamente necessari allo svolgimento del progetto. Occorre quindi procedere per gradi (che poi sono anche i criteri di valutazione del progetto):

  • definire chiaramente l’obiettivo
  • capire quali sono i dati rilevanti per raggiungere l’obiettivo
  • costruire un opportuno grafo basandosi su tali dati
  • proporre e implementare una soluzione per il problema algoritmico su grafi che naturalmente emerge

Si noti che il progetto va svolto modellando il problema come un problema su grafi (orientati o meno) in cui i nodi e gli archi sono etichettati.

Nota. Nella soluzione proposta è sempre possibile camminare tra due fermate, come alternativa agli altri mezzi, alla velocità di 5km all'ora.

Nota sul formato dei file. I file che terminano in *.csv (textual comma separated values), sono utilizzati come formato semplice di scambio: ogni riga testuale rappresenta un “record” i cui campi sono separati da un punto e virgola nel nostro caso. Occorre quindi leggere una linea alla volta di ciascun file e separare i campi. Per esempio, possiamo reindirizzare l'input da tastiera in modo che il comando di lettura cin legga da file invece che da tastiera, usando il comando:

freopen("file.csv", "r", stdin);

A questo punto possiamo leggere ogni riga di file.csv come stringa C++ ed estrarne i campi separati dal delimitatore ';'. Iterando più volte sulla riga, possiamo ottenere tutti i campi.

using namespace std;
string s;
cin >> s;
string delimitatore = “;”;
string campo = s.substr(0, s.find(delimitatore)); 
matematica/asd/asd_19/progetto_19.txt · Ultima modifica: 24/06/2020 alle 06:58 (16 mesi fa) da Roberto Grossi