Loading presentation...
Prezi is an interactive zooming presentation

Present Remotely

Send the link below via email or IM

Copy

Present to your audience

Start remote presentation

  • Invited audience members will follow you as you navigate and present
  • People invited to a presentation do not need a Prezi account
  • This link expires 10 minutes after you close the presentation
  • A maximum of 30 users can follow your presentation
  • Learn more about this feature in our knowledge base article

Do you really want to delete this prezi?

Neither you, nor the coeditors you shared it with will be able to recover it again.

DeleteCancel

Make your likes visible on Facebook?

Connect your Facebook account to Prezi and let your likes appear on your timeline.
You can change this under Settings & Account at any time.

No, thanks

Problème de Sac à Dos

No description
by

Khaoula Ghali

on 25 December 2015

Comments (0)

Please log in to add your comment.

Report abuse

Transcript of Problème de Sac à Dos

Problème de Sac à Dos et le problème de coloriage
2) Probléme de Sac à Dos
Description de probléme de sac à Dos
2) Probléme de Sac à Dos
Formulation
Plan
2) Probléme de Sac à Dos
Dans notre cas,
nous avons un sac à dos de poids maximal
P
et
n
objets.
Pour chaque objet
i
, nous avons un
poids
pi
et une valeur
vi
.
Pour quatre objets
(n = 4)
et un sac à dos d'un poids maximal de
30 kg
(P = 30),
nous avons par exemple les données suivantes :


2) Probléme de Sac à Dos
Ensuite, il nous faut définir les variables qui représentent en quelque sorte les actions ou les
décisions qui amèneront à trouver une solution.

On définit la variable
xi
associée à un objet
i
de la façon suivante :


xi = 1
si l’objet i est mis dans le sac

xi = 0
si l’objet i n’est pas mis dans le sac.
2) Probléme de Sac à Dos
2) Probléme de Sac à Dos
Défintion
2) Probléme de Sac à Dos
Exemple
L'
optimisation combinatire
est une displine combinant à la fois des techniques mathématiques et de l'informatique afin de résoudre des problèmes d'optimisation.

Un
problème d'optimisation
consiste à maximiser (ou minimiser) une certaines fonctions sur un ensemble fini d'éléments ou solutions.
Cette fonction s'appelle fonction Coût, fonction économique ou fonction objective.
1) Introduction
Elaboré par:
Ben Ghali Khaoula
Bourourou Mariem

1) Introduction
2) Problème de sac à dos
3) Probléme de coloriage
4)L'utilité de problème de sac à dos et le problème de coloriage
5) Conclusion

1
En algorithmique,
le problème du sac à dos
, noté également KP (en anglais,
Knapsack problem
) est un problème d'optimisation combinatoire.

Il modélise une situation analogue au remplissage d'un
sac à dos
, ne pouvant supporter plus d'un certain poids, avec tout ou partie d'un ensemble donné d'objets ayant chacun un
poids
et une
valeur
. Les objets mis dans le sac à dos doivent
maximiser la valeur totale
,
sans dépasser le poids maximum
.
Données:
sac à dos vide, objets ayant chacun un poids et une valeur

Objectif:
maximiser la valeur totale des objets dans le sac

contrainte:
poids maximal autorisé dans le sac
On dispose de
n
objets de poids positifs
w1, w2,...,wn
et de valeurs positives
v1, V2,..., vn
, respectivement.

On a un sac à dos de capacité maximale en poids de
w.
Problème:
Remplir le sac à dos de sorte de maximiser
la valeur des objets inclus tout en respectant
la contrainte de poids
On suppose qu’on peut apporter une
fraction
xi
de chaque objet
i



Stratégie vorace:

- Sélectionner chaque objet à tour de rôle dans un certain ordre

- Mettre la plus grande fraction possible de cet objet dans le sac (sans
dépasser la capacité maximale du sac)

- Arrêter quand le sac est plein
2) Probléme de Sac à Dos
Fonctions de sélection possibles

1) Choisir à chaque étape l’objet de plus grande valeur

2) Choisir à chaque étape l’objet le plus léger

3) Choisir à chaque étape l’objet dont la valeur par unité de poids est maximale
2) Probléme de Sac à Dos
Théorème:

Si les objets sont choisis par ordre
décroissant de valeur
par unité de poids
(vi/wi )
,
alors l’algorithme du sac à dos
vorace trouve une solution optimale.
2) Probléme de Sac à Dos
L’énoncé de ce problème fameux est simple:

« Étant donné plusieurs objets possédant
chacun un poids et une valeur et étant donné un poids maximum pour le sac,

quels objets faut-il mettre dans le sac de manière à maximiser la valeur totale sans dépasser le poids maximal autorisé pour le sac ?
»
2) Probléme de Sac à Dos
2) Probléme de Sac à Dos
Dans notre exemple, une solution réalisable est de mettre tous les objets dans le sac à dos sauf
le premier, nous avons donc :

x1 = 0, x2 = 1, x3 = 1, et x4 = 1.
Puis il faut définir les contraintes du problème
la somme des poids de tous les objets dans le sac doit être inférieure ou égale au poids maximal du sac à dos.
Cela s’écrit ici
x1.p1 + x2.p2 + x3.p3 + x4.p4 ≤ P

et pour n objets :

Pour vérifier que la contrainte est respectée dans notre exemple, il suffit de calculer cette somme :
0 × 13 + 1 × 12 + 1 × 8 + 1 ×10 = 30
,
ce qui est bien inférieur ou égal à 30
,
donc la
contrainte est respectée
.
Nous parlons alors de solution réalisable. Mais ce n’est pas nécessairement la meilleure solution.
Enfin, il faut exprimer la fonction qui traduit notre objectif :
maximiser la valeur totale des
objets dans le sac
. Pour n objets, cela s’écrit :
Dans notre exemple, la valeur totale contenue dans le sac est égale à
10
.
Cette solution n’est pas la meilleure
,
car il existe une autre solution
de valeur plus grande que 10
: il faut prendre seulement
les objets 1 et 2
qui donneront une valeur totale de
11
.
Il n’existe pas de meilleure solution que cette dernière, nous dirons alors que cette solution est optimale.
2) Probléme de Sac à Dos
3) Probléme de coloriage
Définition

En théorie des graphes, colorer un graphe signifie attribuer une couleur à chacun de ses sommets de manière que deux sommets reliés par une arête soient de couleur différente.
Est souvent recherchée l'utilisation d'un nombre minimal de couleurs, dit
nombre chromatique
.
Ce problème peut être complexifié en ne cherchant plus une mais plusieurs couleurs par sommets et en associant des
coûts à chacune des couleurs
. Le champ d'applications de la coloration de graphe couvre notamment le problème de l'attribution de fréquences dans les télécommunications ou la conception de puces électroniques.
Deux sommets adjacents ne peuvent pas être coloriés de la même couleur et tous les sommets doivent être coloriés

3) Probléme de coloriage
Complexité du problème de coloration usuelle
3) Probléme de coloriage
Le problème de coloration usuelle est
NP-difficile
au sens fort.
Tout algorithme qui colore un graphe avec
un minimum de couleurs et en garantissant que ce nombre de couleurs est bien minimal a une complexité exponentielle sauf pour des graphes particuliers pour lesquels ce problème est plus facile.

3) Probléme de coloriage
3) Probléme de coloriage
3) Probléme de coloriage
3) Probléme de coloriage
3) Probléme de coloriage
3) Probléme de coloriage
3) Probléme de coloriage
Le principe de l’algorithme glouton (greedy algorithm) :
faire toujours un choix localement optimal dans l’espoir que ce choix mènera à une solution globalement optimale.
l’algorithme glouton
On cherche à obtenir une coloration des sommets d’un graphe qui satisfasse à la contrainte suivante :
deux sommets voisins n’ont jamais la mème couleur.
On cherche à optimiser le nombre de couleurs utilisées.
Le plus petit nombre de couleurs permettant la coloration est appelé
nombre chromatique du graphe
.

On considère l’algorithme suivant :
Input:
Un graphe G et des couleurs 1,2,3,4. . .
Les sommets de G sont numérotés de 1 à n (s1,s2,. . .,sn).

Output:

Une coloration valide du graphe G. Mais le nombre de
couleurs utilisées est-il minimal ?

Traitement:
Pour i allant de 1 à n, affecter au sommet si
la plus petite couleur non déjà affectée à ses voisins déjà coloriés (c’est-à-dire la plus petite couleur non déjà affectée à ceux des sommets s1,s2,. . .,si−1 qui lui sont adjacents).
En d’autres termes,
on gloutonne :
on s’attache, localement, à ne pas augmenter le nombre de couleurs lorsque c’est possible.

Appliquer l’algorithme au graphe ci-dessous avec plusieurs numérotions des sommets et en déduire que l’algorithme ne donne pas nécessairement le nombre chromatique.

Première numérotation :
Seconde numérotation :

. Etablir qu’on peut toujours numéroter les sommets de façon à obtenir le nombre chromatique en appliquant l’algorithme.

On suppose disposer d’une coloration optimale par les couleurs
c1, c2, c3, . . ., cχ
.

On numérote d’abord les sommets de
couleur c1,
puis les sommets de
couleur c2
, puis les sommets de
couleur c3
. . .

L’algorithme colorie alors les sommets de couleur c1 en une couleur c'1, les sommets de couleurs c2 en couleur c'1ou c'2, les sommets de couleur c3 en couleur c'1 , c'2 ou c'3. . .

Appliquer le principe de la démonstration précédente au graphe ci-dessous pour lequel on a donné une coloration optimale.
On numérote, par exemple, comme suit suivant l’ordre , , des
couleurs :
Les sommets 1, 2, 3, 4 reprennent la couleur
rouge
:
Les sommets 5, 6, 7 voisins de sommets rouges prennent la couleur
jaune
:
Le sommet 8 ne reprend pas sa couleur initiale :
Le sommet 9 doit prendre une troisième couleur :

2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
25
4) L'utilité de problème de sac à dos et le problème de coloriage
L'utilité de problème de sac à dos et le problème de coloriage
problème de sac à dos
le problème de coloriage
attribution de fréquences dans les télécommunications

la conception de puces électroniques.

Dans des systèmes d'aide à la gestion de portefeuille :
pour équilibrer sélectivité et diversification dans le but de trouver le meilleur rapport entre rendement et risque pour un capital placé sur plusieurs actifs financiers (actions...)
Dans le chargement de bateau ou d'avion :
tous les bagages à destination doivent être amenés, sans être en surcharge
dans la découpe de matériaux :

pour minimiser les chutes lors de la découpe de sections de longueurs diverses dans des barres en fer, de rouleaux de papier ou de textile
problème de « bin packing »
5) Conclusion
Les problèmes de sac à dos et de coloriage sont les problèmes d'optimisation, mais ils ne sont pas les seuls qui nous donnent une solution optimale.
Full transcript