[Algoritmo] Prova di esame
Il signor Marche va a Venezia
Il signor Marche si eì recato in vacanza a Venezia e ha scoperto, con suo disappunto, quanto e' cara
la famosa città veneta. Ora si trova nella condizione di dover attraversare un canale in gondola e,
guardando i prezzi sui volantini, gli e' preso un colpo. Questo canale, che puo essere percorso in
un'unica direzione, passa per n diversi porticcioli, che per comodita' numereremo da 1 a n. In ogni
porticciolo e' possibile imbarcarsi su una gondola e scendere lungo il canale verso porti successivi.
Il signor Marche si trova nel porto 1 e deve raggiungere il porto n. Il costo di imbarco dipende
dal porto di partenza e da quello di arrivo. Piu' precisamente, imbarcarsi nel porto i e scendere
nel porto j costa c(i; j) (i > j). Progettate un algoritmo di programmazione dinamica che aiuti il
signor Marche a raggiungere l'ultimo porto spendendo il meno possibile e appagando così, almeno in
parte, il suo proverbiale attaccamento ai soldi. L'algoritmo, che deve calcolare la miglior soluzione
prima del tramonto, deve avere complessità polinomiale nella dimensione dell'istanza.
Ragazzi mi date una mano non ho ben capito cosa la traccia intende per costo e come potrei calcolarla , inoltre ho pensato di fare le combinazioni i,j da 1 a n . Qualcuno che mi da un suo punto di vista?
Grazie
Il signor Marche si eì recato in vacanza a Venezia e ha scoperto, con suo disappunto, quanto e' cara
la famosa città veneta. Ora si trova nella condizione di dover attraversare un canale in gondola e,
guardando i prezzi sui volantini, gli e' preso un colpo. Questo canale, che puo essere percorso in
un'unica direzione, passa per n diversi porticcioli, che per comodita' numereremo da 1 a n. In ogni
porticciolo e' possibile imbarcarsi su una gondola e scendere lungo il canale verso porti successivi.
Il signor Marche si trova nel porto 1 e deve raggiungere il porto n. Il costo di imbarco dipende
dal porto di partenza e da quello di arrivo. Piu' precisamente, imbarcarsi nel porto i e scendere
nel porto j costa c(i; j) (i > j). Progettate un algoritmo di programmazione dinamica che aiuti il
signor Marche a raggiungere l'ultimo porto spendendo il meno possibile e appagando così, almeno in
parte, il suo proverbiale attaccamento ai soldi. L'algoritmo, che deve calcolare la miglior soluzione
prima del tramonto, deve avere complessità polinomiale nella dimensione dell'istanza.
Ragazzi mi date una mano non ho ben capito cosa la traccia intende per costo e come potrei calcolarla , inoltre ho pensato di fare le combinazioni i,j da 1 a n . Qualcuno che mi da un suo punto di vista?
Grazie
Risposte
Il costo è semplicemente la somma dei costi di ogni tratta. Se quindi il signor Marche decide di partire dal porto 1, arrivare al porto 5 e poi ripartire per il porto n il costo totale sarà c(1; 5) + c(5; n). Tu devi minimizzare questa somma totale. In che modo fare le combinazioni i, j da 1 a n dovrebbe aiutarti a risolvere il problema? Siccome ti chiede un algoritmo di programmazione dinamica.. Riesci a pensare ad un problema simile di cui conosci già la soluzione? Riesci a trovare dei sottoproblemi che puoi utilizzare per ottenere la soluzione ottimale?
In realtà non ho le idee molto chiare.
Se ho n=7 ad esempio per calcolare tutti i possibili tragitti e quindi i costi non dovrei fare le combinazioni? Ad ognuno associo un costo e poi ordino in base al costo per avere quello più basso. Avrò una procedura per individuare un cammino minino ed un altra per il costo che riceve i,j . Non so se sono sulla giusta strada
Se ho n=7 ad esempio per calcolare tutti i possibili tragitti e quindi i costi non dovrei fare le combinazioni? Ad ognuno associo un costo e poi ordino in base al costo per avere quello più basso. Avrò una procedura per individuare un cammino minino ed un altra per il costo che riceve i,j . Non so se sono sulla giusta strada
In un certo senso ogni tragitto corrisponde certamente ad una combinazione di \(n-2\) elementi (il primo e l'ultimo porto devono necessariamente far parte del cammino che ti interessa). Ma questa osservazione non descrive un algoritmo. Il numero totale di combinazioni è oltretutto esponenziale e non polinomiale..
Come giustamente sottolineato da apatriarca è impensabile a livello computazionale provare a scandire tutte le combinazioni (pur con tutte quelle che si possono scartare a priori).
Personalmente mi vengono in mente gli algoritmi per grafi per determinare i cammini minimi a sorgente singola. I costi per andare da un porto all'altro si possono esprimere mediante una normale matrice di adiacenza. Nella fattispecie trattandosi di pesi positivi l'algoritmo di Dijkstra si rivelerebbe anche più ottimale di quello di Bellman-Ford.
Personalmente mi vengono in mente gli algoritmi per grafi per determinare i cammini minimi a sorgente singola. I costi per andare da un porto all'altro si possono esprimere mediante una normale matrice di adiacenza. Nella fattispecie trattandosi di pesi positivi l'algoritmo di Dijkstra si rivelerebbe anche più ottimale di quello di Bellman-Ford.
Si dopo molti ragionamenti pensavo anche io a dijkstra. Provo a farlo 
Ok, facci sapere. In caso potrebbe essere (ma non ne sono sicurissimo al momento) che qualche piccolo aggiustamento/miglioria all'algoritmo possa contribuire a diminuirne ulteriormente la complessità e/o ad evitare controlli inutili. Ripeto: può darsi non sia così, è solo un'idea che mi viene al momento.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo