[C++] Minor cammino (semplice)

[Mesh89]

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?

[Mesh89]

Nessuno? é.è

[yorkeiser]

In che senso il risultato è sbagliato?

[Mesh89]

 | 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]

Lo provo

[Mesh89]

Se provi addirittura a partire dall'ultimo (1) ti da 11, mentre è evidentemente 8...

[cionci]

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.

[Mesh89]

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...

[Mesh89]

E cmq resta il fatto che partendo dalla centrale mi da 11 e non 12, quindi il problema è che è TROPPO ottimale XD

[cionci]

Originariamente inviato da Mesh89

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).

[Mesh89]

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?

[Qu@ker]

#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;
}

[Mesh89]

? O.o"
Mi hai solo indentato il codice in modo diverso, o sbaglio?

[cionci]

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.

[cionci]

Ah...ha portato n a 4

[cionci]

Originariamente inviato da Mesh89

 | 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 !!!

[Mesh89]

A me 11, e partendo da altre caselle da risultati ugualmente sbagliati... Giuro, non vi sto prendendo in giro! Com'è possibile? ?_?

[cionci]

No mi torna 11, non mi aveva ricompilato

[Qu@ker]

[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!

[Mesh89]

Perchè a certi torna 11 ad altri 12?