IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)
Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

Algorithmes et structures de données Discussion :

Aide en programmation dynamique


Sujet :

Algorithmes et structures de données

  1. #1
    Membre actif
    Inscrit en
    Février 2006
    Messages
    311
    Détails du profil
    Informations forums :
    Inscription : Février 2006
    Messages : 311
    Points : 253
    Points
    253
    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 émérite Avatar de vttman
    Homme Profil pro
    Développeur "couteau mosellan"
    Inscrit en
    Décembre 2002
    Messages
    1 140
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Moselle (Lorraine)

    Informations professionnelles :
    Activité : Développeur "couteau mosellan"
    Secteur : Industrie

    Informations forums :
    Inscription : Décembre 2002
    Messages : 1 140
    Points : 2 286
    Points
    2 286
    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 ( ... )
    {
    <div style="margin-left:40px">Si i = 1 {
    <div style="margin-left:40px">j'ordonne mon tableau</div>}
    Recherche dans mon tableau ordonné si j'ai quelque chose qui correspond en partant de l'indice de départ i 
    Si Ok {
    <div style="margin-left:40px">j'affiche mon résultat</div>} Sinon { 
    <div style="margin-left:40px">i=i+1
    max ( mon tableau (maintenant) ordonné , i+1 , 2 , 3)</div>}</div>}
    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 ...
    Emérite, émérite je ne pense pas ... plutôt dans le développement depuis FORT FORT longtemps, c'est mon job, ça oui
    A part ça ... Il ne pleut jamais en Moselle !

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

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

    Informations forums :
    Inscription : Décembre 2006
    Messages : 10 062
    Points : 16 081
    Points
    16 081
    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
    311
    Détails du profil
    Informations forums :
    Inscription : Février 2006
    Messages : 311
    Points : 253
    Points
    253
    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 ( ... )
    {
    <div style="margin-left:40px">Si i = 1 {
    <div style="margin-left:40px">j'ordonne mon tableau</div>}
    Recherche dans mon tableau ordonné si j'ai quelque chose qui correspond en partant de l'indice de départ i 
    Si Ok {
    <div style="margin-left:40px">j'affiche mon résultat</div>} Sinon { 
    <div style="margin-left:40px">i=i+1
    max ( mon tableau (maintenant) ordonné , i+1 , 2 , 3)</div>}</div>}
    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 062
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 51
    Localisation : France, Hérault (Languedoc Roussillon)

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

    Informations forums :
    Inscription : Décembre 2006
    Messages : 10 062
    Points : 16 081
    Points
    16 081
    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 émérite Avatar de vttman
    Homme Profil pro
    Développeur "couteau mosellan"
    Inscrit en
    Décembre 2002
    Messages
    1 140
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Moselle (Lorraine)

    Informations professionnelles :
    Activité : Développeur "couteau mosellan"
    Secteur : Industrie

    Informations forums :
    Inscription : Décembre 2002
    Messages : 1 140
    Points : 2 286
    Points
    2 286
    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) ...
    Emérite, émérite je ne pense pas ... plutôt dans le développement depuis FORT FORT longtemps, c'est mon job, ça oui
    A part ça ... Il ne pleut jamais en Moselle !

  7. #7
    Membre actif
    Inscrit en
    Février 2006
    Messages
    311
    Détails du profil
    Informations forums :
    Inscription : Février 2006
    Messages : 311
    Points : 253
    Points
    253
    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 062
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 51
    Localisation : France, Hérault (Languedoc Roussillon)

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

    Informations forums :
    Inscription : Décembre 2006
    Messages : 10 062
    Points : 16 081
    Points
    16 081
    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: 23/03/2007, 00h30
  2. besoin d'aide sur tableau dynamique
    Par littlesquall dans le forum C
    Réponses: 16
    Dernier message: 02/11/2005, 03h50
  3. aide petit programme pour débutant
    Par kartp0rqx dans le forum C
    Réponses: 16
    Dernier message: 14/10/2005, 20h31
  4. aide en programmation opengl:maillage 3d de visage
    Par lisser dans le forum OpenGL
    Réponses: 4
    Dernier message: 15/05/2004, 00h25

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