[C] ricorsione - calcolo con minimo

[GreenLink]

Ciao,
avrei bisogno di scrivere in maniera ricorsiva un'istruzione di questo tipo:
$$ f(k,x) = min_{\{y \in X \setminus x \}} [f(k-1,y) + c(y,x) ]$$
dove $x,y$ appartengono ad un insieme finito indici $X$ , $c$ è una matrice e $k$ è la variabile intera su cui farei la ricorsione.
I casi base della ricorsione sarebbero i valori $f(0,x)$ che so calcolare senza bisogno di coinvolgere dei minimi.
Non mi è chiaro se è possibile scrivere in linguaggio C una funzione ricorsiva che mi calcoli $f(n,\bar{x})$, dove $n$ e $\bar{x}$ sono dei parametri noti. Anche una piccola idea è apprezzata.
Grazie a tutti.

[Giova411]

Perdonami, hai altre indicazioni?
Non so aiutarti poiché penso sia programmazione dinamica se non sbaglio
Cioé hai quella "formula/ricorrenza" e vuoi tradurla in codice C/pseudocodice

[GreenLink]

Esatto, è un problema di programmazione dinamica (di cui sono un neofita).
L'ho tradotta in C senza fare uso di ricorsione: fissato $k$ e fissato $x$ ho fatto un for sulle y in modo da calcolarmi tutti i valori $[f(k-1,y)+c(y,x)]$ e poi in $f(k,x)$ metto il valore minimo.
Così l'algoritmo è corretto ma lento e per velocizzarlo avevo pensato alla ricorsione, ma non saprei come impostarla.
E' più chiaro o è meglio che posto il codice?

[Giova411]

Sì per la programmazione dinamica serve un percorso di scuola Zen....
Metti il codice CERTO!!!

Devi metterti a scrivere in "modo creativo" e saper bene la ricorsione!

Aspetta che tornino dalle vacanze Apa, Hamming, Vict, Only
(Io ancora sono Neofita peggio di te e con la N grande...)

Vedrai che qualcosa verrà fuori.

[GreenLink]

Bene lo pulisco un po' e poi lo posto, intanto grazie!

[apatriarca]

Non sono ancora andato in vacanza.. Non vedo come la ricorsione possa ridurre i tempi di calcolo. È anzi probabilmente poco utile in un problema come questo. Mostra piuttosto il codice e vediamo cosa si può fare.

[Giova411]

Non vedo come la ricorsione possa ridurre i tempi di calcolo.

Come non detto
Intendevo "imparare a pensare in maniera ricorsiva"
Rimango osservatore del post

[GreenLink]

Ecco il codice che calcola $f[ncount-1][0]$.

Codice:

#include <stdio.h>
#include <time.h>
#include <math.h>
#define maxN 50
#define MAXCOST 1000000
double distmatrix[maxN][maxN];
double dist(int i, int j);
void dist_read (char *in);
int ncount;
double f[maxN][maxN];
double val;

int main (int ac, char **av)
{
   int stage,k;
   int x,y;
   double min;
   double temp;
   if (ac != 2) {
   printf ("Usage: %s distance_matrix\n", *av); return 1;
   }
   dist_read(av[1]);
   
   for (stage=1;stage<ncount;stage++)
   {
      for (x=1; x<ncount;x++)
      {
         k=stage-1;
         if (stage==1){
            f[k][x]=dist(0,x);
         }
         else
         {
            min=MAXCOST;
            for (y=1;y<x;y++)
            {
               val=f[k-1][y]+dist(y,x);
               if (val<min) min= val;
            }
            //y non può valere x
            for (y=x+1;y<ncount;y++)
            {
               val=f[k-1][y]+dist(y,x);
               if (val<min) min= val;
            }
            f[k][x]=min;
         }
      }
   }
   
        min=MAXCOST;
   stage=ncount;
        x=0;k=stage-1;
   for (y=1;y<ncount;y++){
      val=f[k-1][y]+dist(y,x);
      if (val<min) min= val;
   }
   f[ncount-1][0]=min;   
   printf("%f\n",f[ncount-1][0]);      

}

void dist_read (char *in)
{
   FILE *fin = fopen (in, "r");
   int i, j;//, k;
   double k;
   fscanf (fin, "%d", &ncount);
   for (i = 0; i < ncount; i++) {
   for (j = 0; j <= i; j++) {
   fscanf (fin, "%lf", &k);
   distmatrix[i][j] = distmatrix[j][i] = k;
}
}
}

double dist(int i, int j)
{
   return distmatrix[i][j];
}


[apatriarca]

Per prima cosa: il codice funziona? Un algoritmo ricorsivo per risolvere lo stesso problema sarebbe ancora peggio di quello che hai scritto. La lentezza è però principalmente dovuta alla complessità dell'algoritmo da scelto per risolvere questo problema. Se vuoi ottenere qualcosa di più efficiente devi analizzare il problema diversamente in modo da trovare qualche idea alternativa per arrivare alla soluzione.

[GreenLink]

Si, il codice funziona.