Jecko
08-02-2010, 21:51
Salve a tutti, ho già scritto non troppo tempo fa chiedendovi qualche dritta sulla progettazione delle funzioni ricorsive... Ebbene ho fatto passi avanti ma ora sono davvero nella m**** con questo tema d'esame (http://img704.imageshack.us/img704/2801/esamea.jpg). Sono riuscito a far funzionare perfettamente tutto tranne l'ultima funzione ricorsiva che chiede di restituire il valore ottimo del percorso da effettuare per massimizzare il punteggio. Continua a restituirmi dei valori inesatti. Ad esempio su questo file di prova:
6 10 3
Torino
Milano
Genova
Bologna
Venezia
Firenze
Torino Milano 5
Bologna Torino -1
Bologna Milano 6
Milano Bologna -4
Venezia Milano -7
Bologna Venezia 8
Genova Bologna -6
Firenze Genova -2
Bologna Firenze -9
Torino Genova -12
Genova Rosso 9
Venezia Verde 12
Milano Rosso 8
Genova Blu 7
Venezia Rosso 4
Bologna Rosso 5
in 5 mosse invece che restituirmi 34 mi restituisce 13. Il codice che ho scritto per questa funzione ricorsiva è il seguente
int max_score(grafo *G, int vertice, int *cat, int punteggio, int mossa)
{
int i,j,k,flag;
int max=0, rimasti=0, new_punteggio, fg_new_cat=0;
node *ptr;
if(mossa == MAX_MOSSE)
{
for(i=0;i<n_cat;i++)
if(cat[i]!=1)
flag=0;
if(flag)
punteggio*=2;
if(punteggio>=score)
{
score=punteggio;
return 1;
}
return 0;
}
for(i=0;i<n_cat;i++)
{
if(G->adj[vertice].premi[i]!=0)
{
if(G->adj[vertice].premi[i]>max || cat[i]==-1)
{
if(cat[i]==-1)
{
punteggio+=G->adj[vertice].premi[i];
cat[i]=G->adj[vertice].premi[i];
G->adj[vertice].premi[i]=0;
rimasti++;
fg_new_cat=1;
break;
}
max=G->adj[vertice].premi[i];
k=i;
}
rimasti++;
}
}
if(!rimasti)
G->adj[vertice].visitato=VISITATO;
if( !fg_new_cat && max!=0)
{
punteggio+=max;
G->adj[vertice].premi[k]=0;
}
ptr=G->adj[vertice].next;
for(j=0; j<G->adj[vertice].n_citta; j++, ptr=ptr->next)
{
if(G->adj[ptr->v].visitato==NON_VISITATO)
{
new_punteggio=punteggio+(ptr->wt);
if(new_punteggio>=0)
if(max_score(G,ptr->v,cat,new_punteggio,mossa+1))
return 1;
}
}
// Backtrack sul premio acquisito all'n-esima mossa
if(fg_new_cat==1)
{
punteggio-=G->adj[vertice].premi[i];
G->adj[vertice].premi[i]=cat[i];
cat[i]=-1;
}
else
if( !fg_new_cat && max!=0)
{
punteggio-=max;
G->adj[vertice].premi[k]=max;
}
G->adj[vertice].visitato=NON_VISITATO;
return 0;
}
Vi spiego qui sotto bene la struttura dati usata e l'intenzione del mio algoritmo:
Strutture dati
Per la realizzazione del grafo orientato si è scelta una rappresentazione a liste di adiacenza.
In particolare, essendo noto dalla prima riga del file il numero di vertici del grafo, è stato allocato un vettore di puntatori. Per semplificare le operazioni di ricerca è stata utilizzata una tabella di simboli che indicizzasse le stringhe dei vertici (variabile globale citta) ed un'altra che indicizzasse le categorie di premio (variabile globale categorie).
E' stato utilizzato lo stesso tipo node sia per i vertici che per gli archi del grafo. Le differenze consistono nell'utilizzo o meno di alcuni campi:
i vertici utilizzano i campi: v (indice del vertice), vettore premi, n_citta (numero di archi del nodo), visitato (flag utilizzato nell'ultima funzione ricorsiva), next (puntatore alla testa della lista degli archi);
gli archi utilizzano i campi: v (indice del vertice di destinazione dell'arco), wt (peso dell'arco), next (puntatore all'arco successivo);
Supponendo poi che non potessero esserci più premi della stessa categoria in uno stesso nodo, per la rappresentazione dei premi contenuti nei nodi si è utilizzato un vettore di interi (allocato runtime) le cui celle contengono -1 nel caso il premio dell'i-esima categoria non sia presente nel vertice, il valore del premio altrimenti.
Algoritmo dell'ultima funzione:
La sua condizione di terminazione coincide con il raggiungimento del massimo numero di mosse effettuabili. Il successivo blocco di istruzioni cerca se nel vertice corrente sono presenti premi di una categoria ancora non presa. In questo caso marca il premio ponendolo a zero, marca la categoria corrispondente e marca un flag indicante che il ciclo è terminato perchè è stato scelto un premio di una nuova categoria. Nel caso in cui invece non ci siano premi di una nuova categoria l'algoritmo procede cercando il massimo tra quelli disponibili nel nodo. Se non trova nessun premio di nessun tipo disponibile segna il nodo come visitato. La funzione ricorre poi sugli archi del vertice attuale che puntano a vertici non ancora visitati o che hanno ancora premi che possono essere raccolti. Il backtrack avviene in maniera differente a seconda della modalità di selezione del premio all'attuale livello ricorsivo. Se il premio è stato scelto perchè appartenente ad una nuova categoria smarca la categoria, ripristina il valore del premio e del punteggio. Se il premio è stato scelto perchè massimo tra quelli disponibili, viene ripristinato il valore del premio e del punteggio.
So che potrebbe non essere proprio immediato leggersi tutta la pappardella, ma se qualche anima pia mi desse una mano a risolvere l'arcano gliene sarei grato infinitamente!!! Ciao :) :)
6 10 3
Torino
Milano
Genova
Bologna
Venezia
Firenze
Torino Milano 5
Bologna Torino -1
Bologna Milano 6
Milano Bologna -4
Venezia Milano -7
Bologna Venezia 8
Genova Bologna -6
Firenze Genova -2
Bologna Firenze -9
Torino Genova -12
Genova Rosso 9
Venezia Verde 12
Milano Rosso 8
Genova Blu 7
Venezia Rosso 4
Bologna Rosso 5
in 5 mosse invece che restituirmi 34 mi restituisce 13. Il codice che ho scritto per questa funzione ricorsiva è il seguente
int max_score(grafo *G, int vertice, int *cat, int punteggio, int mossa)
{
int i,j,k,flag;
int max=0, rimasti=0, new_punteggio, fg_new_cat=0;
node *ptr;
if(mossa == MAX_MOSSE)
{
for(i=0;i<n_cat;i++)
if(cat[i]!=1)
flag=0;
if(flag)
punteggio*=2;
if(punteggio>=score)
{
score=punteggio;
return 1;
}
return 0;
}
for(i=0;i<n_cat;i++)
{
if(G->adj[vertice].premi[i]!=0)
{
if(G->adj[vertice].premi[i]>max || cat[i]==-1)
{
if(cat[i]==-1)
{
punteggio+=G->adj[vertice].premi[i];
cat[i]=G->adj[vertice].premi[i];
G->adj[vertice].premi[i]=0;
rimasti++;
fg_new_cat=1;
break;
}
max=G->adj[vertice].premi[i];
k=i;
}
rimasti++;
}
}
if(!rimasti)
G->adj[vertice].visitato=VISITATO;
if( !fg_new_cat && max!=0)
{
punteggio+=max;
G->adj[vertice].premi[k]=0;
}
ptr=G->adj[vertice].next;
for(j=0; j<G->adj[vertice].n_citta; j++, ptr=ptr->next)
{
if(G->adj[ptr->v].visitato==NON_VISITATO)
{
new_punteggio=punteggio+(ptr->wt);
if(new_punteggio>=0)
if(max_score(G,ptr->v,cat,new_punteggio,mossa+1))
return 1;
}
}
// Backtrack sul premio acquisito all'n-esima mossa
if(fg_new_cat==1)
{
punteggio-=G->adj[vertice].premi[i];
G->adj[vertice].premi[i]=cat[i];
cat[i]=-1;
}
else
if( !fg_new_cat && max!=0)
{
punteggio-=max;
G->adj[vertice].premi[k]=max;
}
G->adj[vertice].visitato=NON_VISITATO;
return 0;
}
Vi spiego qui sotto bene la struttura dati usata e l'intenzione del mio algoritmo:
Strutture dati
Per la realizzazione del grafo orientato si è scelta una rappresentazione a liste di adiacenza.
In particolare, essendo noto dalla prima riga del file il numero di vertici del grafo, è stato allocato un vettore di puntatori. Per semplificare le operazioni di ricerca è stata utilizzata una tabella di simboli che indicizzasse le stringhe dei vertici (variabile globale citta) ed un'altra che indicizzasse le categorie di premio (variabile globale categorie).
E' stato utilizzato lo stesso tipo node sia per i vertici che per gli archi del grafo. Le differenze consistono nell'utilizzo o meno di alcuni campi:
i vertici utilizzano i campi: v (indice del vertice), vettore premi, n_citta (numero di archi del nodo), visitato (flag utilizzato nell'ultima funzione ricorsiva), next (puntatore alla testa della lista degli archi);
gli archi utilizzano i campi: v (indice del vertice di destinazione dell'arco), wt (peso dell'arco), next (puntatore all'arco successivo);
Supponendo poi che non potessero esserci più premi della stessa categoria in uno stesso nodo, per la rappresentazione dei premi contenuti nei nodi si è utilizzato un vettore di interi (allocato runtime) le cui celle contengono -1 nel caso il premio dell'i-esima categoria non sia presente nel vertice, il valore del premio altrimenti.
Algoritmo dell'ultima funzione:
La sua condizione di terminazione coincide con il raggiungimento del massimo numero di mosse effettuabili. Il successivo blocco di istruzioni cerca se nel vertice corrente sono presenti premi di una categoria ancora non presa. In questo caso marca il premio ponendolo a zero, marca la categoria corrispondente e marca un flag indicante che il ciclo è terminato perchè è stato scelto un premio di una nuova categoria. Nel caso in cui invece non ci siano premi di una nuova categoria l'algoritmo procede cercando il massimo tra quelli disponibili nel nodo. Se non trova nessun premio di nessun tipo disponibile segna il nodo come visitato. La funzione ricorre poi sugli archi del vertice attuale che puntano a vertici non ancora visitati o che hanno ancora premi che possono essere raccolti. Il backtrack avviene in maniera differente a seconda della modalità di selezione del premio all'attuale livello ricorsivo. Se il premio è stato scelto perchè appartenente ad una nuova categoria smarca la categoria, ripristina il valore del premio e del punteggio. Se il premio è stato scelto perchè massimo tra quelli disponibili, viene ripristinato il valore del premio e del punteggio.
So che potrebbe non essere proprio immediato leggersi tutta la pappardella, ma se qualche anima pia mi desse una mano a risolvere l'arcano gliene sarei grato infinitamente!!! Ciao :) :)