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 :

Efficacité du PSE / problème du sac à dos


Sujet :

Algorithmes et structures de données

  1. #1
    Nouveau membre du Club
    Homme Profil pro
    Étudiant
    Inscrit en
    septembre 2017
    Messages
    23
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 22
    Localisation : France, Alpes Maritimes (Provence Alpes Côte d'Azur)

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : septembre 2017
    Messages : 23
    Points : 28
    Points
    28
    Par défaut Efficacité du PSE / problème du sac à dos
    Bonjour,
    J'ai un problème qui s'apparente à celui du sac à dos.
    J'ai fait un programme de PSE.
    Je souhaiterais améliorer sa performance.

    Je compte le nombre de feuilles et le nombre de noeuds parcourus.
    Je souhaite en réduire le nombre.
    Outre les éléments habituels du PSE (couper des branches inutiles), il me semblait que trier la liste devrait avoir un impact sur le nombre de noeuds/feuilles parcouru(e)s.
    Vrai?

    Et aussi qu'il fallait trier dans l'ordre croissant de ratio valeur / poids.
    L'idée étant qu'en commençant l'arbre par les items les moins probables, on va couper plus de branches.
    Vrai?

  2. #2
    Responsable Qt & Livres


    Avatar de dourouc05
    Homme Profil pro
    Ingénieur de recherche
    Inscrit en
    août 2008
    Messages
    24 801
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Val de Marne (Île de France)

    Informations professionnelles :
    Activité : Ingénieur de recherche
    Secteur : Enseignement

    Informations forums :
    Inscription : août 2008
    Messages : 24 801
    Points : 168 363
    Points
    168 363
    Par défaut


    Effectivement, en prenant les objets dans l'ordre indiqué par ce ratio, tu as une très bonne heuristique (qui te donne une solution primale, puis une duale en considérant que tu prends "autant que possible" du premier objet que tu ne peux pas faire rentrer dans ton sac). Tu peux l'appliquer à chaque nœud de ton arbre pour améliorer tes bornes, ça pourrait accélérer tes traitements.
    Vous souhaitez participer aux rubriques Qt ou PyQt (tutoriels, FAQ, traductions), HPC ? Contactez-moi par MP.

    Créer des applications graphiques en Python avec PyQt5
    Créer des applications avec Qt 5.

    Pas de question d'ordre technique par MP !

  3. #3
    Nouveau membre du Club
    Homme Profil pro
    Étudiant
    Inscrit en
    septembre 2017
    Messages
    23
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 22
    Localisation : France, Alpes Maritimes (Provence Alpes Côte d'Azur)

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : septembre 2017
    Messages : 23
    Points : 28
    Points
    28
    Par défaut
    Citation Envoyé par dourouc05 Voir le message
    en prenant les objets dans l'ordre indiqué par ce ratio, tu as une très bonne heuristique (qui te donne une solution primale
    Donc, en triant par valeur/poids ascendant, on coupe plus de branches?
    Citation Envoyé par dourouc05 Voir le message
    tu prends "autant que possible" du premier objet que tu ne peux pas faire rentrer dans ton sac)
    Salut,
    Je n'ai pas compris.

  4. #4
    Responsable Qt & Livres


    Avatar de dourouc05
    Homme Profil pro
    Ingénieur de recherche
    Inscrit en
    août 2008
    Messages
    24 801
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Val de Marne (Île de France)

    Informations professionnelles :
    Activité : Ingénieur de recherche
    Secteur : Enseignement

    Informations forums :
    Inscription : août 2008
    Messages : 24 801
    Points : 168 363
    Points
    168 363
    Par défaut
    Citation Envoyé par sans_deconner Voir le message
    Donc, en triant par valeur/poids ascendant, on coupe plus de branches?
    1. En triant quoi ? En faisant quoi avec ce tri ? Il faut être un chouïa plus précis, là (et ce n'est pas juste de la pédanterie : en l'état, je n'ai pas assez compris ce que tu expliques pour te dire si tu as raison ou pas avec une certitude suffisante).
    2. L'espoir est que tu limites l'exploration, oui, mais je ne peux pas te le garantir pour n'importe quelle instance.

    Citation Envoyé par sans_deconner Voir le message
    Je n'ai pas compris.
    Si tu arrives à faire rentrer les premier et deuxième objets (respectivement, des poids de 10 et 15, pour un sac de capacité 30), en les considérant dans l'ordre du ratio valeur/poids, tu peux faire rentrer "un peu" du troisième objet (s'il a un poids de 10, tu pourras en faire rentrer la moitié). Puisque la solution n'est pas réalisable (elle n'est pas entière), ce n'est pas une borne primale ; par contre, ça te donne une borne duale (relâchement linéaire du problème initial, mais sans utiliser le simplexe).
    Vous souhaitez participer aux rubriques Qt ou PyQt (tutoriels, FAQ, traductions), HPC ? Contactez-moi par MP.

    Créer des applications graphiques en Python avec PyQt5
    Créer des applications avec Qt 5.

    Pas de question d'ordre technique par MP !

  5. #5
    Nouveau membre du Club
    Homme Profil pro
    Étudiant
    Inscrit en
    septembre 2017
    Messages
    23
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 22
    Localisation : France, Alpes Maritimes (Provence Alpes Côte d'Azur)

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : septembre 2017
    Messages : 23
    Points : 28
    Points
    28
    Par défaut
    Citation Envoyé par dourouc05 Voir le message
    1. En triant quoi ?
    Le tableau d'éléments candidats à entrer dans le sac.
    Citation Envoyé par dourouc05 Voir le message
    En faisant quoi avec ce tri ?
    Qui dit tri, dit critère de tri.
    Donc il faut bien choisir un critère.

    Citation Envoyé par dourouc05 Voir le message
    Il faut être un chouïa plus précis, là (et ce n'est pas juste de la pédanterie : en l'état, je n'ai pas assez compris ce que tu expliques pour te dire si tu as raison ou pas avec une certitude suffisante).
    2. L'espoir est que tu limites l'exploration, oui, mais je ne peux pas te le garantir pour n'importe quelle instance.
    On tente d'entrer successivement les éléments dans le sac (puis on coupe des branches lorsqu'il n'y a plus assez de poids disponible), il faut bien avoir un ordre dans lequel on essaie de les faire entrer.
    Donc, voilà, je me dis qu'en entrant d'abord les moins probables, j'aurais plus de branches à couper.

    Citation Envoyé par dourouc05 Voir le message
    Si tu arrives à faire rentrer les premier et deuxième objets (respectivement, des poids de 10 et 15, pour un sac de capacité 30), en les considérant dans l'ordre du ratio valeur/poids, tu peux faire rentrer "un peu" du troisième objet (s'il a un poids de 10, tu pourras en faire rentrer la moitié).
    OK. Mais quel rapport avec ma question?
    Citation Envoyé par dourouc05 Voir le message
    Puisque la solution n'est pas réalisable (elle n'est pas entière), ce n'est pas une borne primale ; par contre, ça te donne une borne duale (relâchement linéaire du problème initial, mais sans utiliser le simplexe).
    Je n'ai pas compris.

Discussions similaires

  1. Réponses: 2
    Dernier message: 24/02/2010, 23h08
  2. Compréhension d'un algorithme sur le problème du sac à dos
    Par Treuze dans le forum Algorithmes et structures de données
    Réponses: 3
    Dernier message: 18/12/2006, 15h26

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