1. #1
    Membre actif
    Inscrit en
    février 2006
    Messages
    307
    Détails du profil
    Informations forums :
    Inscription : février 2006
    Messages : 307
    Points : 230
    Points
    230

    Par défaut Aide en programmation dynamique

    Bonjour ,

    J'essaye de résoudre ce type de problème à l'aide de la programmation dynamique mais je n'y parviens pas totalement.

    Si quelqu'un aurait une aide afin que je parviens à trouver la solution ?

    Merci d'avance pour toute aide.

    Cordialement.

  2. #2
    Membre expérimenté Avatar de vttman
    Homme Profil pro
    Mainframe et le WE (CSS, PHP, JS et MYSQL)
    Inscrit en
    décembre 2002
    Messages
    805
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Moselle (Lorraine)

    Informations professionnelles :
    Activité : Mainframe et le WE (CSS, PHP, JS et MYSQL)
    Secteur : Industrie

    Informations forums :
    Inscription : décembre 2002
    Messages : 805
    Points : 1 529
    Points
    1 529

    Par défaut

    Merci d'avance pour toute aide.
    En passant

    Perso j'aurais déja ordonné le tableau
    puis passé en fonction le tableau , un indice de départ (i), nombre , distance)

    ex avec nombre = 2 et distance 3

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    i = 1
    
    Appel de max ( mon tableau , i, 2, 3)
    
    
    Fonction max ( ... )
    {
    
    Si i = 1 {
    j'ordonne mon tableau
    } Recherche dans mon tableau ordonné si j'ai quelque chose qui correspond en partant de l'indice de départ i Si Ok {
    j'affiche mon résultat
    } Sinon {
    i=i+1 max ( mon tableau (maintenant) ordonné , i+1 , 2 , 3)
    }
    }
    Ainsi je traite 9 8 7 7 6 5 5 si rien 8 7 7 6 5 5 si rien 7 7 6 5 5 etc ...
    Je suis sympa comme tout Mosellan mais ...
    ... (m')aider ou (me) mettre sur la voie c'est une chose
    ... tout (me) faire de A à Z, c'est pas ma conception du rôle d'un forum X ou Y
    Si vous n'êtes pas satisfait de mes réponses, n'hésitez pas à me le faire savoir Merci !

  3. #3
    Rédacteur
    Avatar de pseudocode
    Homme Profil pro
    Architecte système
    Inscrit en
    décembre 2006
    Messages
    10 052
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 45
    Localisation : France, Hérault (Languedoc Roussillon)

    Informations professionnelles :
    Activité : Architecte système
    Secteur : Industrie

    Informations forums :
    Inscription : décembre 2006
    Messages : 10 052
    Points : 15 717
    Points
    15 717

    Par défaut

    Citation Envoyé par vttman Voir le message
    Perso j'aurais déja ordonné le tableau
    Le problème d'ordonner le tableau c'est que ca complexifie énormément la gestion de la distance minimale entre les éléments, ce qui est une contrainte du problème.
    Sans compter que l'algo proposé devient alors une énumération des solutions possibles avec sortie au plus tôt (la première rencontrée étant la meilleure).

    La solution purement dynamique que je vois c'est une variation du "Longest increasing subsequence problem", avec un historique des "d" derniers choix.
    => on maintien en mémoire "d" sommes partielles, suivant qu'on a sélectionné (ou pas) l'un des "d" derniers éléments.

    Exemple pour d=3

    si on a au rang k:
    sum_00 = meilleure somme dans laquelle on n'a sélectionné ni a[k-2], ni a[k-1]
    sum_01 = meilleure somme dans laquelle on a sélectionné a[k-1]
    sum_10 = meilleure somme dans laquelle on a sélectionné a[k-2]

    alors on aura au rang k+1:
    new_sum_00 = max(sum_10 , sum_00) // meilleure somme dans laquelle on n'a sélectionné ni a[k-1], ni a[k]
    new_sum_01 = sum_00 + a[k] // meilleure somme dans laquelle on a sélectionné a[k]
    new_sum_10 = sum_01 // meilleure somme dans laquelle on a sélectionné a[k-1]
    ALGORITHME (n.m.): Méthode complexe de résolution d'un problème simple.

  4. #4
    Membre actif
    Inscrit en
    février 2006
    Messages
    307
    Détails du profil
    Informations forums :
    Inscription : février 2006
    Messages : 307
    Points : 230
    Points
    230

    Par défaut

    Citation Envoyé par vttman Voir le message
    En passant

    Perso j'aurais déja ordonné le tableau
    puis passé en fonction le tableau , un indice de départ (i), nombre , distance)

    ex avec nombre = 2 et distance 3

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    i = 1
    
    Appel de max ( mon tableau , i, 2, 3)
    
    
    Fonction max ( ... )
    {
    
    Si i = 1 {
    j'ordonne mon tableau
    } Recherche dans mon tableau ordonné si j'ai quelque chose qui correspond en partant de l'indice de départ i Si Ok {
    j'affiche mon résultat
    } Sinon {
    i=i+1 max ( mon tableau (maintenant) ordonné , i+1 , 2 , 3)
    }
    }
    Ainsi je traite 9 8 7 7 6 5 5 si rien 8 7 7 6 5 5 si rien 7 7 6 5 5 etc ...
    Effectivement j'avais envisagée cette possibilité qui me permet de résoudre ce problème.

    Mais , le but ici c'est de comprendre la technique algorithmique de la programmation dynamique.

    Cette approche commence par une approche descendante par récursion avec mémoisation qui est pas si évidente.

    Citation Envoyé par pseudocode Voir le message
    Le problème d'ordonner le tableau c'est que ca complexifie énormément la gestion de la distance minimale entre les éléments, ce qui est une contrainte du problème.
    Sans compter que l'algo proposé devient alors une énumération des solutions possibles avec sortie au plus tôt (la première rencontrée étant la meilleure).

    La solution purement dynamique que je vois c'est une variation du "Longest increasing subsequence problem", avec un historique des "d" derniers choix.
    => on maintien en mémoire "d" sommes partielles, suivant qu'on a sélectionné (ou pas) l'un des "d" derniers éléments.

    Exemple pour d=3

    si on a au rang k:
    sum_00 = meilleure somme dans laquelle on n'a sélectionné ni a[k-2], ni a[k-1]
    sum_01 = meilleure somme dans laquelle on a sélectionné a[k-1]
    sum_10 = meilleure somme dans laquelle on a sélectionné a[k-2]

    alors on aura au rang k+1:
    new_sum_00 = max(sum_10 , sum_00) // meilleure somme dans laquelle on n'a sélectionné ni a[k-1], ni a[k]
    new_sum_01 = sum_00 + a[k] // meilleure somme dans laquelle on a sélectionné a[k]
    new_sum_10 = sum_01 // meilleure somme dans laquelle on a sélectionné a[k-1]
    J'essaye de comprendre ton raisonnement que veut dire a au rang k ?

  5. #5
    Rédacteur
    Avatar de pseudocode
    Homme Profil pro
    Architecte système
    Inscrit en
    décembre 2006
    Messages
    10 052
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 45
    Localisation : France, Hérault (Languedoc Roussillon)

    Informations professionnelles :
    Activité : Architecte système
    Secteur : Industrie

    Informations forums :
    Inscription : décembre 2006
    Messages : 10 052
    Points : 15 717
    Points
    15 717

    Par défaut

    Citation Envoyé par Johnny P. Voir le message
    J'essaye de comprendre ton raisonnement que veut dire a au rang k ?
    Ca signifie qu'on a traité les "k" premiers éléments du tableau = résolu le sous-problème de taille "k".

    Le principe de la programmation dynamique c'est d'utiliser les solutions des sous-problèmes (calculées précédemment) pour résoudre le problème actuel.

    Mettons que j'ai déjà résolu les sous-problèmes:

    {n=2 ; d=3 ; a=[4, 5, 7, 4]}
    {n=2 ; d=3 ; a=[4, 5, 7, 4, 5]}
    {n=2 ; d=3 ; a=[4, 5, 7, 4, 5, 6]}
    {n=2 ; d=3 ; a=[4, 5, 7, 4, 5, 6, 4]}
    et
    {n=3 ; d=3 ; a=[4, 5, 7, 4, 5, 6, 4]}

    Comment je pourrais m'en servir pour résoudre le problème général:

    {n=3 ; d=3 ; a=[4, 5, 7, 4, 5, 6, 4, 1]}

    Réponse:
    A = j'ajoute la dernière valeur (1) à la solution du sous-problème {n=2 ; d=3 ; a=[4, 5, 7, 4, 5]}
    B = je conserve la solution du sous-problème {n=3 ; d=3 ; a=[4, 5, 7, 4, 5, 6, 4]}
    la solution du problème général est max(A,B)


    Si vous êtes fans des méthodes récursives:
    Code java : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    int solution(int n, int d, int[]a, int k) {
      if (n==0) return 0;
      if (k>=a.length) return -INF;
     
      int s0 = solution(n-1, d, a, k+d);
      int s1 = solution(n,   d, a, k+1);
     
      if (s0==-INF) return s1; else return Math.max(a[k]+s0,s1);
    }
     
    int[] a = {4, 5, 7, 4, 5, 6, 4, 1}; int n=3, d=3;
    int max = solution(n,d,a,0);
    //
    ALGORITHME (n.m.): Méthode complexe de résolution d'un problème simple.

  6. #6
    Membre expérimenté Avatar de vttman
    Homme Profil pro
    Mainframe et le WE (CSS, PHP, JS et MYSQL)
    Inscrit en
    décembre 2002
    Messages
    805
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Moselle (Lorraine)

    Informations professionnelles :
    Activité : Mainframe et le WE (CSS, PHP, JS et MYSQL)
    Secteur : Industrie

    Informations forums :
    Inscription : décembre 2002
    Messages : 805
    Points : 1 529
    Points
    1 529

    Par défaut

    Effectivement Pseudocode ...
    Pour du code concis ça l'est !
    =>
    BRAVO

    Une remarque cependant... pour n = 3 et d = 3, ton code Java me renvoie 12 ?
    Sauf erreur de ma part (une des dernières sans doute sur 2017), je m'attendais à 15 (7+4+4) ...
    Je suis sympa comme tout Mosellan mais ...
    ... (m')aider ou (me) mettre sur la voie c'est une chose
    ... tout (me) faire de A à Z, c'est pas ma conception du rôle d'un forum X ou Y
    Si vous n'êtes pas satisfait de mes réponses, n'hésitez pas à me le faire savoir Merci !

  7. #7
    Membre actif
    Inscrit en
    février 2006
    Messages
    307
    Détails du profil
    Informations forums :
    Inscription : février 2006
    Messages : 307
    Points : 230
    Points
    230

    Par défaut

    Merci pseudocode ton code fonctionne et ce pour tous les cas , il me faudrait beaucoup d'entrainements pour arriver à trouver une solution si élégante...
    ton code est plus compacte.

    As-tu des conseils pour arriver à maitriser cette technique , livre à me conseiller etc...? car elle me semble assez complexe et encore ce type de problème n'était pas des plus difficiles.

  8. #8
    Rédacteur
    Avatar de pseudocode
    Homme Profil pro
    Architecte système
    Inscrit en
    décembre 2006
    Messages
    10 052
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 45
    Localisation : France, Hérault (Languedoc Roussillon)

    Informations professionnelles :
    Activité : Architecte système
    Secteur : Industrie

    Informations forums :
    Inscription : décembre 2006
    Messages : 10 052
    Points : 15 717
    Points
    15 717

    Par défaut

    Citation Envoyé par vttman Voir le message
    Une remarque cependant... pour n = 3 et d = 3, ton code Java me renvoie 12 ?
    Sauf erreur de ma part (une des dernières sans doute sur 2017), je m'attendais à 15 (7+4+4) ...
    7+4+4 ne respecte pas la contrainte "les éléments doivent être espacés de 3 cases" dans le tableau 4, 5, 7, 4, 5, 6, 4, 1


    Citation Envoyé par Johnny P. Voir le message
    Merci pseudocode ton code fonctionne et ce pour tous les cas , il me faudrait beaucoup d'entrainements pour arriver à trouver une solution si élégante...
    ton code est plus compacte.

    As-tu des conseils pour arriver à maitriser cette technique , livre à me conseiller etc...? car elle me semble assez complexe et encore ce type de problème n'était pas des plus difficiles.
    Il faut partir du principe qu'on a déjà résolu tous les problèmes de dimensions inférieures et ce demander comment on pourrait utiliser ces solutions pour résoudre le problème de dimension immédiatement supérieure.

    Pour ce problème, les dimensions qu'on a sont:
    - n = le nombre d'éléments a sélectionner
    - k = la taille de la liste

    la distance min entre 2 éléments (d) est davantage une contrainte pour la sélection des éléments qu'une dimension du problème.
    En tous cas, je n'ai pas vu de relation évidente entre un problème pour d=1,2 et le même problème pour d=3.

    Maintenant, il faut construire les solutions des sous-problèmes.
    C'est peut être plus simple si on représente cela comme un tableau qu'il faut remplir (Tableau à 2 dimensions n et k) :

    Données:
    int[] a = {4, 5, 7, 4, 5, 6, 4, 1}; 
    d=3
    
    tableau des solution des sous-problèmes n,k:
    
      k=  1 2 3 4 5 6 7 8
    ----------------------
    n=0 | ? ? ? ? ? ? ? ? 
    n=1 | ? ? ? ? ? ? ? ?
    n=2 | ? ? ? ? ? ? ? ?
    n=3 | ? ? ? ? ? ? ? X 
    Notre objectif c'est de trouver la valeur X (n=3 et liste complète = taille 8).

    Si la relation de récurrence n'est pas évidente dés le départ, on a toujours la méthode basique:
    on commence avec les dimensions les plus faibles = on remplit progressivement le tableau de (0,0) jusqu'a (3,8).

    si n=0, aucun élément à sélectionner, la solution est donc toujours 0.
    si n=1, un seul élément à sélectionner => la solution est l'élément max dans la sous-liste de taille k

      k=  1 2 3 4 5 6 7 8
    ----------------------
    n=0 | 0 0 0 0 0 0 0 0
    n=1 | 4 5 7 7 7 7 7 7
    n=2 | ? ? ? ? ? ? ? ?
    n=3 | ? ? ? ? ? ? ? X  
    si n=2... aie! la contrainte de sélection (d=3) apparait => on ne peut pas choisir 2 éléments espacés de 3 cases tant que la sous-liste fait moins de 4

      k=  1 2 3 4 5 6 7 8
    ----------------------
    n=0 | 0 0 0 0 0 0 0 0
    n=1 | 4 5 7 7 7 7 7 7
    n=2 | - - - ? ? ? ? ?
    n=3 | ? ? ? ? ? ? ? X  
    A partir de là, il nous faut une solution basée sur les cases déjà remplies du tableau.
    Qu'est ce que nous apporte le nouvel élément de la sous-liste (a[4]) pour le sous-problème de sélection de n=2 éléments dans une sous-liste de taille 4 ?

    1. Rien. Ca ne va pas améliorer solution précédente => on va garder la solution pour n=2, k=3 (bon vu que c'est -infini, ca serait étonnant )

    2. Ca nous permet de construire une meilleure solution => a[4] + un autre élément.
    Cet autre élément doit être la "meilleure" sélection de 1 élément dans une sous-sous-liste dont tous les éléments sont à une distance minimum de d=3 par rapport à a[4].
    => c'est la solution d'un sous-problème connu: la sélection de n=1 élément dans la sous-liste de taille k=4-3=1 => la case n=1,k=1 du tableau

    Et voila, on a l'esquisse de la relation de récurrence:

    sol[2][4] = max( sol[2][3] , a[4] + sol[1][1] )

    (reste à gérer proprement dans le code les cas où il n'y a pas de solution, c-a-d sol[i[j]=-infini, sinon l'addition va être fausse)

      k=  1 2 3 4 5 6 7 8
    ----------------------
    n=0 | 0 0 0 0 0 0 0 0
    n=1 | 4 5 7 7 7 7 7 7
    n=2 | - - - 8 ? ? ? ?
    n=3 | ? ? ? ? ? ? ? X  
    relation de récurrence qu'on peut généraliser en:

    sol[n][k] = max( sol[n][k-1] , a[k] + sol[n-1][k-d] )

      k=  1 2 3 4  5  6  7  8
    -------------------------
    n=0 | 0 0 0 0  0  0  0  0
    n=1 | 4 5 7 7  7  7  7  7
    n=2 | - - - 8 10 13 13 13
    n=3 | - - - -  -  - 12 12 
    ALGORITHME (n.m.): Méthode complexe de résolution d'un problème simple.

+ Répondre à la discussion
Cette discussion est résolue.

Discussions similaires

  1. Liens : Aide à la programmation avec DirectX
    Par djbed dans le forum DirectX
    Réponses: 11
    Dernier message: 22/03/2007, 23h30
  2. besoin d'aide sur tableau dynamique
    Par littlesquall dans le forum C
    Réponses: 16
    Dernier message: 02/11/2005, 02h50
  3. aide petit programme pour débutant
    Par kartp0rqx dans le forum C
    Réponses: 16
    Dernier message: 14/10/2005, 19h31
  4. aide en programmation opengl:maillage 3d de visage
    Par lisser dans le forum OpenGL
    Réponses: 4
    Dernier message: 14/05/2004, 23h25

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo