PDM_VI_GSVI_MPI.cpp

#include <stdio.h>
#include <time.h>
#include <conio.h>
#include <malloc.h>
#include <math.h>
#include <iostream>

//  Définition de la classe Classes_FC pour le calcul
// de la forme canonique de la matrice de transition
class VI_MDP{
    public:
    int nbr_etats;          // Nombre d'états
    float eps, alpha;
    float Prb[100][10][100];
    float gains[100][10];
    float *Vopt;
    int *nbr_actions;
    int *strategie;

    VI_MDP( int n );    //Constructeur
    void lire_nbr_actions( );
    void lire_gains();
    void lire_Piaj();
    void VI();
    void MPI(); //algorithme modifié d'itération de la politique
    void GSVI();
    void Affiche_strategie();
};

//Conxtructeur
VI_MDP::VI_MDP( int n ){
    nbr_etats=n;
    nbr_actions= new int[n];
    strategie= new int[n];
    Vopt= new float[n];
    eps=0.1;
    alpha=0.5;
}

//Lecture du nombre d'actions par etat
void VI_MDP::lire_nbr_actions(){
    for(int i=0; i<nbr_etats; i++){
        printf(" entrer le nombre d'actions dans l'etat %d :", i+1);
        scanf("%d", &nbr_actions[i]);
    }
}

//Lecture des recompenses
void VI_MDP::lire_gains(  ){
    for(int i=0; i<nbr_etats; i++){
        for(int a=0; a<nbr_actions[i]; a++){
            printf(" entrer R(%d,%d) :", i+1,a+1);
            scanf("%f", &gains[i][a]);
        }
    }
}

//Lecture des probabilites de transitions
void VI_MDP::lire_Piaj( ){
    for(int i=0; i<nbr_etats; i++){
        for(int a=0; a<nbr_actions[i]; a++){
            for(int j=0; j<nbr_etats; j++){
                printf(" entrer la proba P(%d,%d,%d):", i+1,a+1,j+1);
                scanf("%f", &Prb[i][a][j]);
            }
        }
    }
}

//L'algorithme d'iteration de la valeur
void VI_MDP::VI( ){
  float *Vt=new float[nbr_etats];
  float Maxv, tmpv, cv;
  int itr=0,argmax;
  for(int i=0; i<nbr_etats;i++)Vopt[i]=0;
  do{
    cv=0;itr++;
    for(int i=0; i<nbr_etats;i++){
        Maxv=gains[i][0];argmax=0;
        for(int j=0; j<nbr_etats;j++){
            Maxv += alpha*Prb[i][0][j]*Vopt[j];
        }
        for(int a=1; a<nbr_actions[i]; a++){
            tmpv=gains[i][a];
            for(int j=0; j<nbr_etats;j++){
                tmpv += alpha*Prb[i][a][j]*Vopt[j];
            }
            if( tmpv>Maxv){
                Maxv=tmpv; argmax=a;
            }
        }
        Vt[i]=Maxv;
        if( fabs(Vt[i]-Vopt[i])>cv)cv=fabs(Vt[i]-Vopt[i]);
        strategie[i]=argmax;
    }
    printf("\nVopt a l'iteration %d: ", itr);
    for(int i=0; i<nbr_etats;i++){
        Vopt[i]=Vt[i];
        printf("%f, ", Vopt[i]);
    }
  }while( cv>=eps);
}


//L'algorithme Gauss-seidel d'iteration de la valeur
void VI_MDP::GSVI( ){
  float *Vt=new float[nbr_etats];
  float Maxv, tmpv, cv;
  int itr=0,argmax;
  for(int i=0; i<nbr_etats;i++)Vopt[i]=0;
  do{
    cv=0;itr++;
    for(int i=0; i<nbr_etats;i++){
        Maxv=gains[i][0];argmax=0;
        for(int j=0; j<nbr_etats;j++){
            Maxv += alpha*Prb[i][0][j]*Vopt[j];
        }
        for(int a=1; a<nbr_actions[i]; a++){
            tmpv=gains[i][a];
            for(int j=0; j<nbr_etats;j++){
                tmpv += alpha*Prb[i][a][j]*Vopt[j];
            }
            if( tmpv>Maxv){
                Maxv=tmpv; argmax=a;
            }
        }
        Vt[i]=Maxv;
        if( fabs(Vt[i]-Vopt[i])>cv)cv=fabs(Vt[i]-Vopt[i]);
        strategie[i]=argmax;
        Vopt[i]=Vt[i];
    }
    printf("\nVopt a l'iteration %d: ", itr);
    for(int i=0; i<nbr_etats;i++){
        printf("%f, ", Vopt[i]);
    }
  }while( cv>=eps);
}

//Affichage de la strategie
void VI_MDP::Affiche_strategie(){
    printf("\nStrategie =  ");
    for( int i=0; i<nbr_etats; i++){
        printf("%d, ",strategie[i]+1 );
    }
}


void VI_MDP::MPI( ){
 float *Vt=new float[nbr_etats];
 float Maxv, tmpv;
 int argmax;
 int *St0=new int[nbr_etats]; //pour l'initialisation de la strategie
 for(int i=0; i<nbr_etats; i++)St0[i]=0;//initialisation de la strategie

    printf("\n strategie initiale est :" );
    for(int i=0; i<nbr_etats;i++){
        printf("%d, ", St0[i]+1);
    }

 bool cv1=false;
 float cv2;
 int nbr_itr=0;
 do{
    nbr_itr++;
    cv1=true;

    //Calcul du vecteur gain pour la startegie St0[]
    for(int i=0; i<nbr_etats;i++)Vopt[i]=0; //initialisation du vecteur
    //Calcul jusqu'au convergence
    do{
        cv2=0;
        for(int i=0; i<nbr_etats;i++){
            Vt[i]=gains[i][St0[i]];
            for(int j=0; j<nbr_etats;j++){
             Vt[i]+= alpha*Prb[i][St0[i]][j]*Vopt[j];
            }
            if( fabs(Vt[i]-Vopt[i])>cv2) cv2=fabs(Vt[i]-Vopt[i]);
            Vopt[i]=Vt[i];
        }
    }while( cv2>=eps);

    printf("\n Vecteur gain a l'iteration %d est:",nbr_itr );
    for(int i=0; i<nbr_etats;i++){
        printf("%f, ", Vopt[i]);
    }
    //Calcul de la strategie argmax du vecteur Vopt[]
    for(int i=0; i<nbr_etats;i++){

        Maxv=gains[i][0];argmax=0;
        for(int j=0; j<nbr_etats;j++){
            Maxv += alpha*Prb[i][0][j]*Vopt[j];
        }

        for(int a=1; a<nbr_actions[i]; a++){
            tmpv=gains[i][a];
            for(int j=0; j<nbr_etats;j++){
                tmpv += alpha*Prb[i][a][j]*Vopt[j];
            }
            if( tmpv>Maxv){Maxv=tmpv; argmax=a;}
        }
        strategie[i]=argmax;
        if(strategie[i] != St0[i])cv1=false;
    }
    printf("\n strategie a l'iteration %d est:",nbr_itr );
    for(int i=0; i<nbr_etats;i++){
        St0[i]=strategie[i];
        printf("%d, ", St0[i]+1);
    }

 }while(cv1==false);

}


int main (){
    int n;
    printf("entrer le nombre d'etats :");
    scanf("%d",&n);
    VI_MDP MDP(n); //constructeur
    MDP.lire_nbr_actions();
    printf("********* Faite attention a la saisie des donnees*********\n:");
    MDP.lire_gains();
    printf("********* Faite attention a la saisie des donnees*********\n:");
    MDP.lire_Piaj();
    etq:
    printf("\n\nq-   quitter\n");
    printf("1-   L'algorithme d'iteration de la valeur\n");
    printf("2-   L'algorithme d'iteration de la valeur de Gauss-seidel\n");
    printf("3-   L'algorithme modifier d'iteration de la politique\n");
    printf("         votre choix : ? ");
    char c=getch();
    switch (c){
        case '1':  MDP.VI();
            MDP.Affiche_strategie();
            break;
        case '2':
            MDP.GSVI();
            MDP.Affiche_strategie();
            break;
        case '3':
            MDP.MPI();
            MDP.Affiche_strategie();
            break;
    }

    if( (c != 'q') && (c !='Q') )goto etq;
    getch();
}