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 :

Demande d'info sur optimisation sac-a-dos en prog dynamique


Sujet :

Algorithmes et structures de données

Vue hybride

Message précédent Message précédent   Message suivant Message suivant
  1. #1
    Membre expérimenté
    Profil pro
    Étudiant
    Inscrit en
    Août 2005
    Messages
    161
    Détails du profil
    Informations personnelles :
    Âge : 42
    Localisation : France, Maine et Loire (Pays de la Loire)

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : Août 2005
    Messages : 161
    Par défaut Demande d'info sur optimisation sac-a-dos en prog dynamique
    Bonsoir developpeur, developpeuses.

    Alors voilà je travaille sur la résolution du problème de sac à dos à l'aide de la programmation dynamique.
    J'ai trouvé l'algorithme classique sur wikipedia (http://fr.wikipedia.org/wiki/Probl%C...tion_dynamique) et je l'ai implémenté.

    Cependant j'aimerais l'optimiser en réduisant la consommation mémoire en O(n+W), n étant le nombre d'objets et W la capacité du sac (c'est aussi sur la page wikipedia que j'ai entendu parler de cette optimisation).
    J'ai réfléchi a peu près deux jours sur ce problème sans rien trouver puis googlé deux autres jours toujours sans succès.

    Ma question est simple, connaissez vous cet algorithme qui n'utilise que deux tableaux à une dimension, qui peut calculer le gain optimal et retrouver les objets utilisés pour atteindre ce gain ?

    Dernière chose, l'optimisation mémoire en O(W) ne m'intéresse pas car je dois retrouver les objets mis dans le sac une fois le gain maximal calculé.

    Merci.

  2. #2
    Membre chevronné
    Profil pro
    Directeur Scientifique
    Inscrit en
    Avril 2005
    Messages
    419
    Détails du profil
    Informations personnelles :
    Âge : 52
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : Directeur Scientifique

    Informations forums :
    Inscription : Avril 2005
    Messages : 419
    Par défaut
    Tu peux regarder ce livre téléchargeable (chaptre 2.6 surtout)
    mais je ne suis pas sûr qu'il y a la réponse.
    http://www.or.deis.unibo.it/knapsack.html

  3. #3
    Membre confirmé
    Profil pro
    Inscrit en
    Mai 2002
    Messages
    162
    Détails du profil
    Informations personnelles :
    Âge : 43
    Localisation : France, Loire Atlantique (Pays de la Loire)

    Informations forums :
    Inscription : Mai 2002
    Messages : 162
    Par défaut
    Bonjour,

    Le livre "Knapsack Problems" de Kellerer et al. (http://www.diku.dk/knapsack/) présente à peu près tout ce qui a été fait sur le problème du sac à dos jusqu'à 2004. En particulier, il présente un algo pour résoudre une instance par programmation dynamique en O(nc) en temps et O(n+c) en mémoire.

    C'est loin d'être simple, je ne sais pas si ça vaut le coup de détailler les 5 pages ici. Par contre je peux te les photocopier et te les envoyer (c'est en anglais).

    (dans quelle mesure ça reste légal de copier des pages d'un livre ?)

    Voilà quand même l'algo tel que sorti du bouquin, mais sache qu'il y a plusieurs hypothèses à vérifier (le bouquin explique bien qu'elles sont vérifiées pour le problème du sac à dos).

    On notera
    - N un (sous) ensemble des éléments,
    - C une capacité,
    - X*(N,C) une solution optimale pour cette instance,
    - z*(N,C) la valeur de X*(N,C)
    - SOLVE(N, C) est un algo qui calcule z*(N,c) pour tout c dans {0,...,C} en O(|N|*C) temps et O(|N|+C) en mémoire (je crois que tu as déjà un tel algo), et si |N|=1, alors il calcule aussi X*(N,C).

    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
    16
    17
    18
    19
    20
    21
    -- Algorithme Recursive-DP(N,C) --
     
    Partitionner N en deux ensembles disjoints N1 et N2 de taille équivalentes
    Appeler SOLVE(N1, C) pour obtenir z*(N1, c) pour tout c dans {0,...,C}
    Appeler SOLVE(N2, C) pour obtenir z*(N2, c) pour tout c dans {0,...,C}
    Trouver C1, C2 tels que C1+C2=C et z*(N1,C1)+z*(N2,C2) = z*(N,C)
     
    si |N1| = 1 alors
      fusionner X*(N1,C1) et X*(N*,C*) en X*(union(N1,N*), C1+C*)
      N* = union(N*,N1)
      C* = C* + C1
    fin si
     
    si |N2| = 1 alors
      fusionner X*(N2,C2) et X*(N*,C*) en X*(union(N2,N*), C2+C*)
      N* = union(N*,N2)
      C* = C* + C2
    fin si
     
    si |N1| > 1 alors appeler Recursive-DP(N1,C1)
    si |N2| > 1 alors appeler Recursive-DP(N2,C2)

  4. #4
    Membre expérimenté
    Profil pro
    Étudiant
    Inscrit en
    Août 2005
    Messages
    161
    Détails du profil
    Informations personnelles :
    Âge : 42
    Localisation : France, Maine et Loire (Pays de la Loire)

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : Août 2005
    Messages : 161
    Par défaut
    Tout d'abord merci Francis et YéTeeh pour vos réponses.

    YéTeeh> Je vais essayer de comprendre l'algorithme que tu as donné mais ça m'intéresserais aussi d'avoir les 5 pages du livre concernant cette solution (tu voulais dire scanner au lieu de photocopier ?).

    Edit: je vois a peu près comment fonctionne ton algo, il procède récursivement en découpant a chaque fois le problème en deux et il calcule l'optimum pour ces deux problème et essaie de trouver une combinaison pour arriver à l'optimum du problème parent.

    Le truc qui me gène c'est que ça me parait très couteux en terme de complexité (en temps). Déjà le premier appel de Recursive-DP, calcule z*(N1, c), z*(N2, c) et z*(N, c) grâce à SOLVE qui est en O(|N|*C).
    Et comme SOLVE est rappelé 2 fois à chaque recursion ça donne une complexité en O(log(|N|) * |N| * C).

    Me serait-je trompé quelque part dans mon étude de l'algo ?

  5. #5
    Membre expérimenté
    Profil pro
    Étudiant
    Inscrit en
    Août 2005
    Messages
    161
    Détails du profil
    Informations personnelles :
    Âge : 42
    Localisation : France, Maine et Loire (Pays de la Loire)

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : Août 2005
    Messages : 161
    Par défaut
    Bon voilà le problème est résolu, merci YéTeeh.

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

Discussions similaires

  1. Demande d'info sur MySQL 3.23.58
    Par gobs dans le forum Installation
    Réponses: 5
    Dernier message: 25/01/2006, 12h52
  2. demande d'infos sur le composant IBDataSet
    Par seb8810 dans le forum Bases de données
    Réponses: 4
    Dernier message: 18/01/2006, 15h16
  3. [Débutant] Demande d'info sur OpenGL
    Par SkyDev dans le forum OpenGL
    Réponses: 2
    Dernier message: 01/03/2005, 23h58
  4. Demande d'info sur treeview
    Par Anaxagore dans le forum IHM
    Réponses: 6
    Dernier message: 28/08/2003, 18h27

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