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

Version imprimable

15/05/2019, 00h30
sans_deconner

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?
15/05/2019, 18h52
dourouc05

:salut:

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.
17/05/2019, 22h44
sans_deconner

Citation:

Envoyé par dourouc05

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

tu prends "autant que possible" du premier objet que tu ne peux pas faire rentrer dans ton sac)

Salut,
Je n'ai pas compris.
18/05/2019, 03h48
dourouc05

Citation:

Envoyé par sans_deconner

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à :P (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

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).
18/05/2019, 23h51
sans_deconner

Citation:

Envoyé par dourouc05

1. En triant quoi ?

Le tableau d'éléments candidats à entrer dans le sac.

Citation:

Envoyé par dourouc05

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

Il faut être un chouïa plus précis, là :P (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

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

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.