View Full Version : [C++] Minor cammino (semplice)
Salve a tutti. Il problema è semplice: dobbiamo attraversare un castello 5x5 stanze, ed ogni stanza ha un certo costo di attraversamento. Si parte sempre da quella più sud. La versione è semplice e di prestazioni scarse, senza quindi utilizzare programmazione dinamica e altri artefici.
#include <iostream>
using namespace std;
#define INF 1000000
int n=5;
int castle[5][5]={{6,7,4,7,8},{7,6,1,1,4},{3,5,7,8,2},{2,6,7,0,2},{7,3,5,6,1}};
int min(int n1, int n2, int n3)
{
int tmin=n1;
if (tmin > n2)
tmin = n2;
if (tmin > n3)
tmin = n3;
return tmin;
}
int minCost(int x, int y)
{
if (x < 0 || x >= n)
return INF;
else if (y == 0)
return castle[x][y];
else
return min(minCost(x-1, y-1), minCost(x, y-1), minCost(x+1, y-1)) + castle[x][y];
}
int main()
{
int x, y=4;
cout << "x da cui partire (0-4): "; cin >> x;
cout << minCost(x,y);
system("PAUSE");
}
Eppure il risultato è sempre sbagliato... Qualcuno mi sa dire perchè? Il codice è esattamente quello trovato su Wikipedia, alla seguente pagina
http://it.wikipedia.org/wiki/Programmazione_dinamica
e non è nulla di trascendentale... dove sbaglio?
yorkeiser
16-02-2007, 14:46
In che senso il risultato è sbagliato?
| 6 | 7 | 4 | 7 | 8 |
| 7 | 6 | 1 | 1 | 4 |
| 3 | 5 | 7 | 8 | 2 |
| 2 | 6 | 7 | 0 | 2 |
| 7 | 3 | 5 | 6 | 1 |
Questa è la matrice
Se parto dalla casella centrale (5), è evidente che il percorso più breve è:
5 + 0 + 2 + 1 + 4 = 12
Eppure mi restituisce 11. E la stessa cosa in altri casi
yorkeiser
16-02-2007, 15:35
Lo provo
Se provi addirittura a partire dall'ultimo (1) ti da 11, mentre è evidentemente 8...
Quello che hai utilizzato è un algoritmo greedy: in pratica scegli di spostarti sulla casella vicina che ha costo minore, ma non porta ad un cammino ottimale se non in rari casi.
Comunque ad occhio non vedo problemi...provo a guardarlo meglio.
Sicuro? Perchè cmq si richiama ricorsivamente sulle caselle successive, scegliendo quelle da cui parte il cammino più breve, e per farlo ripete la cosa su quelle successive ancora... E' molto inefficiente in termini di tempo, però dovrebbe portare alla soluzione ottimale...
E cmq resta il fatto che partendo dalla centrale mi da 11 e non 12, quindi il problema è che è TROPPO ottimale XD
Sicuro? Perchè cmq si richiama ricorsivamente sulle caselle successive, scegliendo quelle da cui parte il cammino più breve, e per farlo ripete la cosa su quelle successive ancora... E' molto inefficiente in termini di tempo, però dovrebbe portare alla soluzione ottimale...
Guarda questo:
00054
05432
05432
05432
00600
Partendo da quella centrale in basso il tuo farebbe: 6 + 5 + 0 + 0 + 0
Mentre il cammino minore ha costo nullo..
Questo perché permetti sempre e solo di salire di una riga...quando in teoria il cammino minimo potrebbe passare anche da una cella adiacente lateralmente.
C'è un algoritmo del cammino a costo minimo che si chiama Dijkstra...lo puoi adattare semplicemente al tuo algoritmo. Una implementazione dell'algoritmo si chiama Forward Search e la puoi realizzare staticamente e facilmente con due vettori di strutture da 25 elementi (in teoria si farebbe meglio con una lista, ma in questo modo non dove fare allocazione dinamica).
Si, conosco Dijsktra... cmq ripeto, questo è solo un adattamento del codice proposto alla pagina, mi servirebbe per arrivare poi a capire il passo successivo, non voglio risolvere il problema in modo ottimale, è chiaro che è una pessima via... Però non da il risultato che dovrebbe! Trovato nulla?
:D
#include <iostream>
const int INF = 1000000;
int n = 4;
int castle[5][5] = {{6,7,4,7,8},
{7,6,1,1,4},
{3,5,7,8,2},
{2,6,7,0,2},
{7,3,5,6,1}};
int min(int n1, int n2, int n3)
{
return (n1 < n2) ? ((n1 < n3) ? n1 : n3)
: ((n2 < n3) ? n2 : n3);
}
int minCost(int x, int y)
{
if (x < 0 || x > n)
return INF;
if (y == 0)
return castle[y][x];
return min(minCost(x-1, y-1),
minCost(x, y-1),
minCost(x+1, y-1)) + castle[y][x];
}
int main()
{
int x;
std::cout << "x da cui partire (0-4): ";
std::cin >> x;
std::cout << minCost(x, n) << std::endl;
}
? O.o"
Mi hai solo indentato il codice in modo diverso, o sbaglio?
Ti ha messo anche questo: if (x < 0 || x > n)
Però sinceramente non mi torna...perchè con x==5 questo fa la chiamata ricorsiva, ma accede a castle[y][5] che è fuori dallo spazio allocato.
| 6 | 7 | 4 | 7 | 8 |
| 7 | 6 | 1 | 1 | 4 |
| 3 | 5 | 7 | 8 | 2 |
| 2 | 6 | 7 | 0 | 2 |
| 7 | 3 | 5 | 6 | 1 |
Questa è la matrice
Se parto dalla casella centrale (5), è evidente che il percorso più breve è:
5 + 0 + 2 + 1 + 4 = 12
Eppure mi restituisce 11. E la stessa cosa in altri casi
Boh...a me restituiscono 12 entrambi i programmi !!!
A me 11, e partendo da altre caselle da risultati ugualmente sbagliati... Giuro, non vi sto prendendo in giro! Com'è possibile? ?_?
No mi torna 11, non mi aveva ricompilato :stordita:
[jcd@server tmp]$ ./camminomin
x da cui partire (0-4): 2
12
[jcd@server tmp]$ ./camminomin
x da cui partire (0-4): 4
8
[jcd@server tmp]$
Aguzzate la vista!
:D
Perchè a certi torna 11 ad altri 12?
Guarda che il mio e il tuo non sono uguali.
E la differenza (minima) è rilevante.
:D
Che idiota -.-" Devo invertire x e y...
per studiare l'algoritmo volevo sapere quale è la cella/stanza finale da raggiungere...
quella di partenza l'ho capita:
4-2 corrispone a:
int castle[5][5] = {{6,7,4,7,8},
{7,6,1,1,4},
{3,5,7,8,2},
{2,6,7,0,2},
{7,3,5*,6,1}};
ho contrassegnata la casella di partenza con lì* ovvero 4-2 corrisponde al peso 5.
mentre 2-3 corrisponde a:
int castle[5][5] = {{6,7,4,7,8},
{7,6,1,1,4},
{3,5,7,8*,2},
{2,6,7,0,2},
{7,3,5,6,1}};
ho contrassegnata la casella di partenza con lì* ovvero 2-3 corrisponde al peso 8.
Ora iniziando la ricerca dalla casella appunto contrassegnata vi domando in che casella deve finire la ricerca per il percorso da a
Credo che debba finire una volta uscito dalla prima riga da qualsiasi casella...almeno così sembra fare l'algoritmo sopra...
Credo che debba finire una volta uscito dalla prima riga da qualsiasi casella...almeno così sembra fare l'algoritmo sopra...
già...
si parte dalla 5 (x=4) si cerca in verticale la stanza con peso minore e ci si ferma alla riga (x=0) nella y con peso minore... okay.
ho letto il 3d e proprio tu cionci hai detto che non è proprio un metodo buono ma si potrebbe fare in altro modo.
Ho letto un pò "googlando" e mi interessa fare algoritmi di questo tipo hai qualche stralcio di code per iniziare.
questo sopra cosa ha che non ti piace in termini di efficienza.. tu passeresti anche nelle stanze accanto?... perchè?
Oppure: come modificarlo per avere un punto di partenza e un punto di arrivo e trovare il miglior percorso?... ecco si allora potrei andare da solo!
questo sopra cosa ha che non ti piace in termini di efficienza.. tu passeresti anche nelle stanze accanto?... perchè?
Qui ho fatto un esempio di un semplice cammino che necessità di passare per orizzontale: http://www.hwupgrade.it/forum/showpost.php?p=16009059&postcount=10
L'algoritmo di Dijkstra si usa per trovare il cammino di costo minimo fra tutti i nodi di un grafo, immaginati che ogni cella della matrice si un nodo del grafo e che ogni cella sia legata alle sue adiacenti tramite una arco del grafo.
http://it.wikipedia.org/wiki/Algoritmo_di_Dijkstra
Sicuramente c'è anche qualche altro algoritmo che permette di trovare il cammino minimo fra due nodi scelti (Dijkstra lo trova fra tutti i nodi del grafo), ma ora non mi viene in mente...
Qui ho fatto un esempio di un semplice cammino che necessità di passare per orizzontale: http://www.hwupgrade.it/forum/showpost.php?p=16009059&postcount=10
L'algoritmo di Dijkstra si usa per trovare il cammino di costo minimo fra tutti i nodi di un grafo, immaginati che ogni cella della matrice si un nodo del grafo e che ogni cella sia legata alle sue adiacenti tramite una arco del grafo.
http://it.wikipedia.org/wiki/Algoritmo_di_Dijkstra
Sicuramente c'è anche qualche altro algoritmo che permette di trovare il cammino minimo fra due nodi scelti (Dijkstra lo trova fra tutti i nodi del grafo), ma ora non mi viene in mente...
ho letto...
In pratica si definisce il punto di partenza e il punto di arrivo.
Poi si và a ritroso passando per il peso minore.
Ho solo un dubbio!
tornando a ritroso nell'esempio del tuo link è tutto ok.
Ma se il disegno/esercizio fosse differente come percorsi. intendo: non è possibile che prendendo la strada + breve puoi incappare in strade con percorso maggiore?
Ho quello che ho letto per risolvere l'esercizio non sbaglia mai?
No, non si va a ritroso. Si va dal nodo di partenza a quello di arrivo...
Funziona sempre perché vengono considerati sempre i percorsi alternativi...
No, non si va a ritroso. Si va dal nodo di partenza a quello di arrivo...
Funziona sempre perché vengono considerati sempre i percorsi alternativi...
ok.
Mi metto a svilupparlo una cosa però (senza che mi ci scervello su come inizializzare):
Scelta del punto di partenza:
for i=0 to 10 diciamo.
posso iniziare dall'i = 0 come punto di partenza aggiornando tutti i punti che vanno da 0 a 9 punto di arrivo e questo va bene oppure se nella rete scelgo come punto di partenza i=5 e devo arrivare a i=1 ??
che faccio aggiorno di nuovo i percorsi da 1 a 5?? tenendo presente solo le strade che contattano questi?
spero che mi hai capito... e niente liste!
Edit: mi servono + matrici da 10 una ponendo a 1 le strade da considerare giusto?
for i=0 10
cons[i]=1// considero tutte le strade
diciamo le strade da considerare
for i 0 10
if(consBool[i])
cons[i]=1:
hai altre matrici da inserire per i controlli che ne sò: per il punto di partenza e di arrivo ecc ecc.
Guarda qui, magari si capisce meglio lo pseudocodice: http://en.wikipedia.org/wiki/Dijkstras_Algorithm#Description_of_the_algorithm
vBulletin® v3.6.4, Copyright ©2000-2025, Jelsoft Enterprises Ltd.