Introduction
Algorithmes: Complexité, Analyse, Ordre
Diviser pour régner
Programmation dynamique
Algorithmes voraces
Complexité du calcul
CSI3505- Paola Flocchini
La théorie de Complexité
Bornes inférieures pour la complexité
d’un problème
Un algorithme A est optimal (dans le cas pire) pour P si on peut montrer qu’il est impossible de trouver un autre algorithme pour P et qui a une meilleure complexité (dans le cas pire) que A.
CSI3505- Paola Flocchini
La théorie de Complexité
Comment montrer qu’un algorithme est optimal ?
Trouver une borne inférieure (Lower Bound) sur le
nombre d’opérations nécessaires pour résoudre P. C’est dire que pour tous les algorithmes A on doit prouver que:
WA(n) ≥ K
CSI3505- Paola Flocchini
La théorie de Complexité
• Exemple: Multiplication des matrices
Algorithme de Strassen: n2.81
Meilleur algorithme connu: n2.376
Il existe une borne inférieure pour ce problème: n2
Pour tout algorithme optimal A de multiplication des matrices:
n2 ≤ WA(n) ≤ n2.376
CSI3505- Paola Flocchini
La théorie de Complexité
• Exemple 2: recherche d’un élément dans une liste
de n nombres
Il existe une borne inférieure pour ce problème: n
Donc l’algorithme de recherche séquentielle est
optimal
CSI3505- Paola Flocchini
La théorie de Complexité
Exemple: Tri (basé sur les comparaisons des clefs)
On sait qu’il y a des algorithmes de tri dont la
complexité est (n log n).
Peut on faire mieux?
Quelle est la borne inférieure pour ce problème?
CSI3505- Paola Flocchini
La théorie de Complexité
Arbres de décision: arbre binaire où chaque nœud interne représente
une comparaison de l’algorithme
Exemple du tri par insertion: pour le cas n=3
CSI3505- Paola Flocchini
La théorie de Complexité
Trier trois nombres avec l’algorithme du tri par insertion: comportement de l’algorithme pour (5,7,2)
Chaque type d’entrée correspond à un chemin de la racine à une feuille dans l’arbre de décision.
En général: Le nombre maximal de comparaisons est égal à la longueur du plus long chemin de la racine aux feuilles.
CSI3505- Paola Flocchini
a < b
oui
b<c
non
a<c
non
c≤a ≤ b
La théorie de Complexité
Arbres de décision
oui
a < b
non
oui
a≤ b≤c
b<c
non
a<c
b<c
oui
a<c
non
c≤b≤a
oui
non
oui
non
a≤c≤b
c≤a≤b
b≤ a≤c
b≤c≤a
CSI3505- Paola Flocchini
(3,8,1)
oui
a < b
non
oui
a≤ b≤c
b<c
non
a<c
b<c
oui
a<c
non
c≤b≤a
oui
non
oui
non
a≤c≤b
c≤a≤b
b≤ a≤c
1,3,8
CSI3505- Paola Flocchini
b≤c≤a
La théorie de Complexité
Profondeur: longueur du plus long chemin de la racine
aux feuilles
Propriété des arbres binaires
1.
2d ≥ k
d = profondeur, k = nombre de feuilles
(preuve par induction sur d)
2.
Un arbre binaire avec k feuilles a une profondeur d ≥ log k
Preuve
2d ≥ k
log 2d ≥ log k
d ≥ log k
CSI3505- Paola Flocchini
La théorie de Complexité
Obtenir une borne inférieure pour tout les
algorithmes de tri qui utilisent des comparaisons
• A: algorithme de tri qui utilise des comparaisons
TA(n): arbre de décision pour A avec un input de
taille n
WA(n) = profondeur de TA(n)
WA(n) ≥ log t (t est le nombre des feuilles dans l’arbre de décision)
CSI3505- Paola Flocchini
La théorie de Complexité
• Nombre de feuilles ? pour chaque permutation des valeurs a trier x1, …, xn
on aura au moins une feuille
Chaque permutation est une solution pour quelques ensembles de valeurs (donc elle doit apparaître comme feuille dans l'arbre)
Donc t ≥ n !
WA(n) ≥ log t ≥ log n!
CSI3505- Paola Flocchini
La théorie de Complexité
• log n ! = Θ(n log n )
Donc la complexité de tout algorithme de tri par
comparaisons est:
Ω(n log n)
CSI3505- Paola Flocchini
La théorie de Complexité
Nous savons que il existe des algorithmes de tri
avec une complexité O(n log n) (exemple: tri par fusion)
Puisque la borne inférieure pour les algorithmes de
tri est de n log n
Tri par fusion est un algorithme optimal
Θ(n log n) est un temps nécessaire et suffisant pour trier n éléments.
CSI3505- Paola Flocchini
La théorie de Complexité
Un algorithme est dit polynomial si sa complexité dans le pire
cas est inférieure ou égale à Θ(p(n)), où p(n) est un polynôme en n (n est la taille de l'input).
Ex.
Θ(n2) Θ(n4) Θ(nn) Θ(n!) Θ(n200000)
oui oui non non oui
CSI3505- Paola Flocchini
La théorie de Complexité
Un algorithme est efficace (polynomial) si sa
complexité dans le pire cas est O(p(n)) ou n est la taille de l’input du problème.
efficace = polynomial
CSI3505- Paola Flocchini
La théorie de Complexité
Un problème est traitable si l'on connaît un algorithme polynomial pour le résoudre.
Il existe de nombreux problèmes pour lesquels aucun algorithme polynomial n'est connu.
Pour certains d'entre eux, des algorithmes polynomiaux existent mais aucun n'a encore été découvert.
Pour d'autres, nous avons une forte impression qu'aucun algorithme polynomial ne peut être trouvé.
CSI3505- Paola Flocchini
La théorie de Complexité
• Un problème est non traitable
s’il n’y a aucun algorithme polynomial qui le résout.
(Tous les algorithmes ont une complexité dans le pire cas qui ne peut être borné par un polynôme p(n) où n est la taille du problème.)
• Exemples de fonctions non bornés par un polynôme:
( ) f n
=
n
c
,
n
, …log n
CSI3505- Paola Flocchini
La théorie de Complexité
L’utilité de cette classification?
• Si le problème est non traitable: ne sert a rien d’essayer
de chercher un algorithme efficace.
• Tous les algorithmes seront trop lents pour des données
assez grandes.
• Changer la stratégie en utilisant des approximations,
heuristiques, etc.
• Quelque fois on a besoin de résoudre des versions
restreintes du problème. La version restreinte pourrait être tractable
CSI3505- Paola Flocchini
La théorie de Complexité
Non décidable
– problème impossible à résoudre : il ne peut jamais exister un algorithme.
Turing a montré qu’il existe des problèmes qu’on ne pourra jamais résoudre: non décidable
Exemple: Problème d’arrêt
CSI3505- Paola Flocchini
La théorie de Complexité
Problème d’arrêt:
Algo A pour probleme P
Donnée X
A va-t-il s’ arrêter pour la donnée X
OUI A(X)
NON (ne s’arrêtera jamais)
CSI3505- Paola Flocchini
La théorie de Complexité
Pour plusieurs problèmes pratiques, personne n’a jamais trouvé un algorithme efficace pour les résoudre : · Exemples :
· Commis voyageur, coloration des graphes, etc.
· La plupart des problèmes en "testing et routing".
· Plusieurs problèmes de réseaux, bases de données,
problèmes sur les graphes, etc.
CSI3505- Paola Flocchini
La théorie de Complexité
• La théorie des problèmes NP-complets
– Cette théorie nous permet de prouver que la plupart de ces problèmes non-tractables sont équivalents en termes de difficulté.
– Un problème de ce type “NP complet” ne peut probablement pas être résolu d’une façon efficace
CSI3505- Paola Flocchini
La théorie de Complexité
· Besoin de définir
· Problème de décisions · La classe des problèmes P · Algorithmes non déterministes · La classe des problèmes NP · Le concept de transformations polynomiales · La classe des problèmes NP-complets
CSI3505- Paola Flocchini
La théorie de Complexité
· Dans toute cette théorie, on ne considère
que les problèmes de décisions
· Un problème est dit de décision si pour tout input, l’unique output possible est de type
“OUI” ou “NON”
CSI3505- Paola Flocchini
La théorie de Complexité
• Exemples:
• Étant donnés un graphe G, un nombre k et deux sommets s et t dans G, existe-t-il un chemin de longueur au plus k?
• Étant donné un graphe G,
existe-t-il un cycle Hamiltonien dans G?
(Un cycle est, dit Hamiltonien si tous les sommets du graphe
apparaissent une et une seule fois dans ce cycle)
CSI3505- Paola Flocchini
Publicité
La théorie de Complexité
• La plupart des problèmes d’optimisation peuvent
être convertis à des problèmes de décision.
• Il suffit d’ajouter une borne K sur la valeur à
optimiser et changer la question:
– Existe-t-il une solution dont la valeur est au plus K (Pour
les problèmes de minimisation)
– Existe-t-il une solution dont la valeur est au moins K
(Pour les problèmes de maximisation)
CSI3505- Paola Flocchini
La théorie de Complexité
Version du commis voyageur comme problème
de décision
Soient un ensemble de villes C={c1,...,cm}, une fonction distance d(ci, cj) entre les villes dans C. Soit un nombre K.
Existe-t-il un tour de toutes les villes dont la
longueur est au plus K ?
La problème du commis voyageur est traitable si est seulement si le problème de décision correspondant est tractable CSI3505- Paola Flocchini
La théorie de Complexité
optimisation
La version d’optimisation d’un problème est traitable si est seulement si la version de décision correspondant est traitable
décision
CSI3505- Paola Flocchini
La théorie de Complexité
Algorithme polynomial non-déterministe
1) Guessing (partie non-déterministe)
retourne un string S pour une instance I
certificat
donnée du problème
2) Vérification (partie déterministe)
retourne oui/non pour l'instance I et le string S
(ou bien ne s'arrête pas)
CSI3505- Paola Flocchini
La théorie de Complexité
• Définition: La classe P
– Un problème de décision est dans la classe P s’il a des algorithmes polynomiaux déterministe qui le résout.
• Définition: La classe NP
– Un problème de décision est dans la classe NP s’il a des algorithmes polynomiaux non déterministe qui le résout.
• NP “Non-deterministic Polynomially bounded.”
CSI3505- Paola Flocchini
La théorie de Complexité
• Classe NP: classe des problèmes pour
lesquels on est capable de vérifier dans un temps polynomial si le certificat S (une proposition de solution) est ou non une solution.
CSI3505- Paola Flocchini
La théorie de Complexité
Problème dans la classe NP
Facile de vérifier une solution
proposée (mais on ne sais pas si c’est facile a résoudre)
Problème dans la classe P
Facile a résoudre
Théorème: P ⊆ NP
CSI3505- Paola Flocchini
NP
P
La théorie de Complexité
Algorithme de vérification pour le problème du commis voyageur : • Vérification si un ensemble de sommets
représente une solution:
1. Vérifier que c’est un cycle.
2. Vérifier que sa longueur est au plus K.
• Il y a un algorithme polynomial qui fait
cette vérification
Le problème du commis voyageur est dans NP
CSI3505- Paola Flocchini
La théorie de Complexité
Algorithme de vérification pour le problème CHEMIN :(Étant données un graphe G, un nombre k et deux sommets s et t, existe-t-il un chemin de longueur au plus k?)
• Vérification si un ensemble de sommets
représente une solution:
• Vérifier que c’est un chemin de s a t.
• Vérifier que sa longueur est au plus K.
Il y a un algorithme polynomial qui fait cette
vérification. Le problème CHEMIN est dans NP
CSI3505- Paola Flocchini
La théorie de Complexité
Coloration d'un graphe
Soit G = (V,E) un graphe orienté dont on veut colorer les Sommets avec la condition suivante:
Deux sommets reliés par une arête, ont deux couleurs différentes.
Problème: Étant donnée un graphe G, trouver un algorithme qui colore proprement G et qui utilise le nombre minimum possible de couleurs
Forme de Décision: Étant données un graphe G et un entier positif k, est-ce qu'il existe une coloration qui utilise au plus k couleurs ?
CSI3505- Paola Flocchini
La théorie de Complexité
Ordonnancement des Examens: exemple d’un
problème qui peut s'exprimer en termes de coloration d'un graphe:
Un graphe dont les sommets sont tous les cours, et on met une arête entre u et v s’il existe au moins un étudiant qui prends les cours u et v en même temps.
ENG 1000
CSI 3503
Phy 1500
ENG 3300 CSI3505- Paola Flocchini
CSI 3505
La théorie de Complexité
Exemple:
1
2
3
4
5
Deux couleurs
CSI3505- Paola Flocchini
La théorie de Complexité
• Autres exemples:
2 couleurs
2 couleurs
5 couleurs
3 couleurs
CSI3505- Paola Flocchini
La théorie de Complexité
Algorithme de vérification pour le problème
COLORATION :
• Vérification si une coloration des sommets
représente une solution:
• Vérifier que le nombre de couleurs utilisées est au
plus K.
• Pour chaque arête (u, v) dans le graphe, Vérifier que u
et v sont colorés différemment.
Il y a un algorithme polynomial qui fait cette vérification. Le
problème COLORATION est dans NP
CSI3505- Paola Flocchini
La théorie de Complexité
Algorithme de vérification pour le
problème HAMILTONIEN:
• Vérification si un ensemble de sommet
représente une solution:
• Vérifier que ce ensemble contient tous les
sommets du graphe une seule fois.
Il y a un algorithme polynomial qui fait cette vérification. Le problème HAMILTONIEN est dans NP
CSI3505- Paola Flocchini
La théorie de Complexité
Une question ouverte
Est ce que P = NP ?
NP
P
?
NP = P
CSI3505- Paola Flocchini
Problèmes NP-complets
CSI3505- Paola Flocchini
La théorie de Complexité
La classe des problèmes NP-complets est
l’ensemble de tous les problèmes Q vérifiant les propriétés suivantes:
NP
1- Q est dans NP. 2- Il existe une algorithme polynomial pour résoudre Q si est seulement si pour tout problème Q’ dans la classe NP il existe un algorithme polynomial pour résoudre Q’.
CSI3505- Paola Flocchini
La théorie de Complexité
Comment prouver:
Il existe un algorithme polynomial pour
résoudre Q
si est seulement si
pour tout autre problème dans la classe NP il existe un algorithme polynomial pour le résoudre?
CSI3505- Paola Flocchini
La théorie de Complexité
Réduction des problèmes.
Problème P1
Input X
Transformation T (algorithme)
Problème P2, Input T(X)
1. La transformation doit se faire en temps polynomial
2. La réponse correcte de P1 pour x est « OUI" alors la réponse correcte de P2 pour T(x) est aussi " OUI ".
3. La réponse correcte de P2 pour T(x) est " OUI" alors la réponse correcte de P1 pour x est aussi " OUI ".
CSI3505- Paola Flocchini
La théorie de Complexité
Si la fonction T peut être calculer en temps
polynomial, nous dirons que
P1 est polynomialement réductible a P2
( P1 ∝ P2)
CSI3505- Paola Flocchini
La théorie de Complexité
Donc,
P1 ∝ P2 =
il existe une fonction T qui transforme tout input x de P1 en T(x), un input de P2, de telle sorte que la réponse correcte de P1 pour x soit "oui" si et seulement si la réponse correcte de P2 pour T(x) est aussi "oui".
CSI3505- Paola Flocchini
La théorie de Complexité
P1 ∝ P2 P2 est au moins, aussi difficile à résoudre que P1 La composition de la fonction T et de
l'algorithme résolvant P2 nous donne un algorithme pour résoudre P1.
x (input pour P1)
T
T(x)
input pour P2
Algorithme pour P2
Réponse OUI ou NON
CSI3505- Paola Flocchini
La théorie de Complexité
Théorème: Si P1 ∝ P2 et P2 est dans P, alors P1 est aussi
dans P.
Définition équivalente de la classe NP-complet Un problème P1 est NP-complet si
P1 est dans NP et, pour tout autre problème P2 dans NP, P2 ∝ P1
CSI3505- Paola Flocchini
La théorie de Complexité
Un problème P1 est NP-complet si P1 est dans NP et, pour tout autre problème P2 dans NP, P2 ∝ P1
NP
∝
∝ ∝
P1
∝ ∝
∝
∝
CSI3505- Paola Flocchini
La théorie de Complexité
Conséquence très importante: si l'on parvient à montrer qu'un problème (Prob) NP-complet se trouve dans P, alors on aura démontré que tous les problèmes de NP sont dans P ! ET DONC P = NP!!!
Prenons un problème P1 quelconque dans NP. Puisque Prob est NP-complet, alors P1 ∝ Prob . La composition de la transformation (polynomiale) et l’algorithme polynomial de Prob nous donne un algorithme polynomial pour P1.
Très improbable que ceci soit vrai
CSI3505- Paola Flocchini
… si un problème NP-complet Prob se trouve dans P
Prenons un problème P1 quelconque dans NP.
Puisque Prob est NP-complet, alors P1 ∝ Prob .
NP
P1
∝
Prob
x (input pour P1)
T
T(x)
input pour Prob
Algorithme pour Prob
Réponse OUI ou NON
CSI3505- Paola Flocchini
Mais alors il existe un algorithme polynomial pour P1 !
La composition de la transformation (polynomiale) et l’algorithme polynomial de Prob nous donne ca.
x (input pour P1)
T
T(x)
input pour Prob
Algorithme pour Prob
Réponse OUI ou NON
P1 est dans la classe P
CSI3505- Paola Flocchini
P
Facile a résoudre
NP
NP-comp
probablement
difficile a résoudre
Facile a vérifier
A ∝ B B est au moins, aussi difficile à résoudre que A (donc B a le même niveau de difficulté ou il est PLUS DIFFICILE que A)
CSI3505- Paola Flocchini
Si A est NP-complete
A
B
et A ∝ B
Publicité
alors B est NP-complete
CSI3505- Paola Flocchini
La théorie de Complexité
•
Prouver qu’un problème B est NP-complet?
– Prouver que B est dans NP (Vérification si un ensemble
représente une solution en un temps polynomial)
– Trouver un problème A qu’on sait déjà qu’il est NP-complet et trouver une fonction T qui transforme chaque instance du probléme A en une instance du probléme B avec les propriétés suivantes:
• La transformation T se fait en un temps polynomial
• Si la réponse a l’instance I du problème A est “OUI” alors
la réponse a l’instance T(I) du problème B est “OUI”
• Si la réponse a l’instance T(I) du problème B est “OUI” alors la réponse a l’instance I du problème A est “OUI”
CSI3505- Paola Flocchini
La théorie de Complexité
Définition: Forme normale conjonctive (FNC)
Littéral = variable booléenne ou sa négation (x ou ¬x) Clause = littéral ou une disjonction de littéraux (∨)
Une expression booléenne est en Forme normale conjonctive (FNC) si elle est une clause ou une conjonction (∧) de clauses
(¬x1 ∨ x2 ∨ ¬x3 ) ∧ (x1 ∨ ¬x4 ) ∧ (¬x2 ∨ ¬x3 ∨ ¬x4 )
K-FNC: les clauses contenant un maximum de k littéraux
CSI3505- Paola Flocchini
La théorie de Complexité
• Problème de Satisfaisabilité
Une expression booléenne est satisfaisable s'il existe (au moins) une assignation de valeurs a ses variables booléenne qui la rende vraie SAT: Problème de décider, étant donnée une expressions booléenne, si elle est satisfaisable
K-SAT: Problème de décider, étant donnée une expressions booléenne avec ≤ k littéraux, si elle est satisfaisable
CSI3505- Paola Flocchini
La théorie de Complexité
SAT-FNC la restriction de SAT aux formes normales
conjonctives
k-SAT-FNC la restriction de SAT aux formes normales conjonctives avec au plus k littéraux
(exemple: 2-SAT est resolvable en temps polynomial)
CSI3505- Paola Flocchini
La théorie de Complexité
• Exemples:
(¬x1 ∨ x2 ∨ ¬x3 ) ∧ (x1 ∨ ¬x4 ) ∧ (¬x2 ∨ ¬x3 ∨ ¬x4 ) OUI
x1 = vrai
x2 = vrai
x3 = faux
x4 = faux
(x1 ∨ x2) ∧ (¬x1) ∧ (¬x2)
NON
CSI3505- Paola Flocchini
La théorie de Complexité
Théorème de Cook: SAT-FNC est un problème NP-complet
Conséquence: 3-SAT-FNC est un problème NP-complet
CSI3505- Paola Flocchini
La théorie de Complexité
• C est une Clique dans un graphe G si toutes les
paires de sommets dans C sont adjacentes. “C est un sous graphe complet dans G”
• Problème “CLIQUE”:
Étant donnée un graphe G, un nombre k,
existe-t-il une clique de taille k?
G contient une clique de taille 4
CSI3505- Paola Flocchini
La théorie de Complexité
• CLIQUE est NP-complet Clique est dans NP • Vérification si un ensemble de sommet représente une
solution:
• Vérifier que ce ensemble contient k sommets.
• Vérifier que ce ensemble de sommets représente une
clique “toutes les paires sont reliées”.
– Il y a un algorithme polynomial qui fait cette vérification.
Le problème CLIQUE est dans NP
CSI3505- Paola Flocchini
La théorie de Complexité
• Il suffit de réduire 3-SAT au problème CLIQUE
3-SAT ∝ CLIQUE
• Transformer une expression booléenne 3-FNS en un graphe
tel que ce graphe contient une clique de taille k
si est seulement si
l’expression booléenne est satisfaisable.
CSI3505- Paola Flocchini
La théorie de Complexité
• La réduction:
– Soit B = C1 ∧ C2 ∧ … ∧ Ck une formule en 3-CNF, avec k
clauses, contenant chacune 3 littéraux distincts.
– Pour chaque clause on crée 3 sommets, un pour chaque
littéral dans la clause.
– On relie deux sommets s’ils proviennent de deux clauses différentes et que leurs littéraux sont consistent “l’un n’est pas la négation de l’autre”
– Exemple:
B = (x ∨ ¬y ∨ ¬z) ∧ (¬x ∨ y ∨ z ) ∧ (x ∨ y ∨ z )
CSI3505- Paola Flocchini
La théorie de Complexité
Exemple: E = (x ∨ ¬y ∨ ¬z) ∧ (¬x ∨ y ∨ z ) ∧ (x ∨ y ∨ z )
1
2
3
x1
y1
z1
x2
y2
z2
x3
y3
z3
CSI3505- Paola Flocchini
La théorie de Complexité
Exemple: E = (x ∨ ¬y ∨ ¬z) ∧ (¬x ∨ y ∨ z ) ∧ (x ∨ y ∨ z )
1
2
3
CSI3505- Paola Flocchini
La théorie de Complexité
Exemple: E = (x ∨ ¬y ∨ ¬z) ∧ (¬x ∨ y ∨ z ) ∧ (x ∨ y ∨ z )
1
2
3
x1
y1
z1
x2
y2
z2
x3
y3
z3
CSI3505- Paola Flocchini
La théorie de Complexité
Exemple: E = (x ∨ ¬y ∨ ¬z) ∧ (¬x ∨ y ∨ z ) ∧ (x ∨ y ∨ z )
1
2
3
x1
y1
z1
x2
y2
z2
x3
y3
z3
CSI3505- Paola Flocchini
La théorie de Complexité
Exemple: E = (x ∨ ¬y ∨ ¬z) ∧ (¬x ∨ y ∨ z ) ∧ (x ∨ y ∨ z )
1
2
3
x1
y1
z1
x2
y2
z2
x3
y3
z3
CSI3505- Paola Flocchini
La théorie de Complexité
•ce graphe contient une clique de taille k
si est seulement si
l’expression booléenne est satisfaisable.
CSI3505- Paola Flocchini
Preuve:
–Si E est satisfaisable, alors chaque clause a au moins un
littéral avec une valeur “Vraie”
–Prends le sommet correspondant de chaque littéral.
Ça doit former une clique de taille k. (Pourquoi?)
(x ∨ ¬y ∨ ¬z) ∧ (¬x ∨ y ∨ z ) ∧ (x ∨ y ∨ z )
Ex: x,y vrai
x1
y1
z1
x2
y2
z2
x3
y3
z3
CSI3505- Paola Flocchini
La théorie de Complexité
– Si G a une clique V’ de taille k, alors V’ contient un sommet
(littéral) dans chacune des clause de E. (Pourquoi?)
– Il suffit de donner la valeur “Vraie” pour ces littéraux. Ceci satisfait la formule E, sans risque d’avoir des contradictions.
(x ∨ ¬y ∨ ¬z) ∧ (¬x ∨ y ∨ z ) ∧ (x ∨ y ∨ z )
x,y,z vrai
x1
y1
z1
x2
y2
z2 CSI3505- Paola Flocchini
x3
y3
z3
La théorie de Complexité
(x ∨ ¬y ∨ ¬z) ∧ (¬x ∨ y ∨ z ) ∧ (x ∨ y ∨ z )
¬y , ¬x ,z vrai
x1
y1
z1
x2
y2
z2 CSI3505- Paola Flocchini
x3
y3
z3
La théorie de Complexité
• Autres exemples de problèmes NP-complets Vertex Cover (VC) Instance: Graphe G=(V,E) et un entier k Question: Existe-t-il une couverture de G par un ensemble de
sommets de taille au plus k?
(V’⊆ V une couverture de G si pour tout (u,v)∈E, on a u∈V’ou v∈V’).
couverture
CSI3505- Paola Flocchini
La théorie de Complexité
Ensemble Indépendant (IND) Instance: Graphe G=(V,E) et un entier k Question: Existe-t-il un ensemble indépendant dans G de taille au moins k? (V’⊆ V est indépendant si pour tous u,v∈V’, (u,v)∉E.)
indépendant
CSI3505- Paola Flocchini
La théorie de Complexité
Cycle Hamiltonien (HAM) Instance: Graphe G=(V,E) et un entier k Question: Existe-t-il un cycle Hamiltonien dans G?
Coloration des graphes(COLORATION) Instance: Graphe G=(V,E) et un entier k Question: Peut on colorer les sommets de G avec au plus k couleurs,
tel que toute paire de sommets adjacents ont des couleurs différentes.
3-Coloration des graphes (lorsque k=3)
Somme
Instance: Un ensemble d’entiers E et un entier T
Question: Existe-t-il un sous ensemble de E dont la somme est T?
CSI3505- Paola Flocchini
La théorie de Complexité
Tous les problèmes
Arrêt
Problèmes NP
Problèmes NP-Complets
TSP
Problèmes P TRI
CSI3505- Paola Flocchini
La théorie de Complexité
Exemples
SAT
3-SAT-CNF
Somme
Clique
VertexCover
Hamiltonien
Commis Voyageur
CSI3505- Paola Flocchini
La théorie de Complexité
Exemple: Problème du plus long cycle (PLC).
Soit un graphe G et un entier k, déterminer si G possède un cycle de longueur ≥ k.
Le problème PLC est NP-complet.
Publicité
Supposons qu’on a déjà prouver que le Problème
Hamiltonien est NP-complet
CSI3505- Paola Flocchini
La théorie de Complexité
1) PLC est dans NP: une solution proposée peut clairement être
vérifiée en temps polynomial.
2) Montrons que le problème du cycle hamiltonien (HAM) est
polynomialement réductible en PLC, HAM ∝ PLC.
Supposons que le graphe G=(V,E) soit l'input de HAM, et que nous désirions donc savoir s'il existe un cycle hamiltonien pour G. Nous transformons cet input en un input pour PLC: étant donné G, déterminer si G possède un cycle de longueur ≥ |V|.
CSI3505- Paola Flocchini
La théorie de Complexité
HAM
Input G=(V,E)
Transformation T
PLC, ou k=|V| Input T(G)=G=(V,E)
Clairement, Si G possède un cycle hamiltonien alors G a un cycle
de longueur supérieure ou égale à |V'|.
Si G a un cycle de longueur supérieure ou égale à |V'| alors G possède un cycle hamiltonien.
Nous avons ainsi montré que HAM ∝ PLC.
PLC est NP-complet
CSI3505- Paola Flocchini
La théorie de Complexité
Problème du commis voyageur (TSP).
Soit un graphe G complet et pondéré avec n sommets, et soit une valeur k, existe-t-il un tour de poids ≤ k?.
Le problème TCP est NP-complet.
Supposons qu’on a déjà prouver que le Problème Hamiltonien
est NP-complet
CSI3505- Paola Flocchini
La théorie de Complexité
1)
TSP est dans NP: une solution proposée peut clairement être vérifiée en temps polynomial.
1) Vérifier que c’est un cycle. 2) Vérifier que sa longueur est au plus k
2) Montrons que le problème du cycle hamiltonien (CH) est polynomialement réductible en TSP, HAM ∝ TSP.
Supposons que le graphe G=(V,E) soit l'input de HAM, et que nous désirions donc savoir s'il existe un cycle hamiltonien pour G. Nous transformons cet input en un input G’ pour TSP ou n = |V|: Ajoute a G’ toutes les arêtes qui manquent dans G pour obtenir un graphe complet Les arêtes qui existaient dans G’ auront un poids de 1, et les nouvelles arêtes auront un poids de 2.
CSI3505- Paola Flocchini
La théorie de Complexité
• Transformation:
CH
Input G=(V,E)
1
5
4
Transformation T
TSP, ou n=|V| Input T(G)=G’=(V,E) 1
2
2
1
1
2
5
1
1
4
2
1
1
3 CSI3505- Paola Flocchini
2
1
3
La théorie de Complexité
On a besoin d’au plus (n2) pour effectuer la transformation (Créer la
matrice d’adjacence pour G’).
Supposons qu’il existe un cycle Hamiltonien v1, v2, …, vn pour G. Ce
cycle est un tour dans G’ et son poids est n “puisque toutes les arêtes de G ont un poids de 1”. Donc la réponse est “OUI” à l’input G’ pour le problème TSP.
Supposons qu’il existe un tour dans G’ de poids n. Puisque ce tours contient tous les sommets de G’ et donc n arêtes et puisque chaque arête a un poids 1, alors le poids du tour est n et toutes ses arêtes ont un poids de 1. Donc les arête du tours sont toutes dans G. Ce qui représente un cycle Hamiltonien dans G. Donc la réponse est “OUI” à l’input G pour le problème Hamiltonien (HAM).
CSI3505- Paola Flocchini
La théorie de Complexité
Qui faire si le problème est NP-complet? Approche 1
Chercher à obtenir autant d'amélioration que possible sur la simple recherche exhaustive. (Tout en acceptant l'apparente inévitabilité que l’algorithme aura une complexité exponentiel)
Approche 2 Tenter de trouver une "bonne" solution (pas nécessairement
optimale) en un temps acceptable. Ces algorithmes sont appelés algorithmes approximatifs ou heuristiques; ils sont souvent basés sur quelques règles empiriques intelligemment choisies.
CSI3505- Paola Flocchini
La théorie de Complexité
Exemple: Un heuristique vorace pour le problème du commis voyageur: "plus proche voisin"
Choisir une ville initiale puis toujours choisir comme ville suivante la ville non encore visitée la plus proche de la ville courante.
Heuristique simple La différence entre la solution trouver et la solution
optimale pourrait être arbitrairement grande
CSI3505- Paola Flocchini
La théorie de Complexité
Les algorithmes approximatifs sont habituellement
évalués par une combinaisons d'études empiriques.
Certains offrent des garanties théoriques
d'efficacité, alors que d'autres n'en offrent guère et peuvent même s'avérer extrêmement mauvais pour certaines instances de problèmes.
CSI3505- Paola Flocchini
La théorie de Complexité
Bornes inférieures sur les solutions optimales pour
calibrer les solutions heuristiques
Cas des solutions heuristiques pour les problème de
minimisation
La valeur d'une solution optimale à notre problème
≤
la valeur d'une solution heuristique à notre problème.
Si la solution heuristique n'offre pas de garantie théorique d'efficacité, ces deux valeurs peuvent être très éloignées - aucun moyen d'évaluer la qualité de notre solution heuristique.
CSI3505- Paola Flocchini
La théorie de Complexité
On ne connaît pas la valeur de la solution optimale, par contre
supposons que nous obtenions une borne inférieure (pas trop petite) sur la valeur d'une solution optimale.
La valeur de la borne inférieure ≤ la valeur d'une solution optimale à notre problème
connu
≤
la valeur d'une solution heuristique à notre problème.
Si la différence entre la borne inférieure et la solution heuristique est petite …. Si par contre cette différence est grande …..
CSI3505- Paola Flocchini
La théorie de Complexité
• Borne inférieure pour le problème du commis voyageur (avec des
poids non-négatifs) – Prenons un tour T de poids minimal et soit T’ obtenu de T en éliminant
une arête quelconque.
–T’ est un arbre recouvrant du graphe de départ et Poids(T’) ≤ Poids(T)
23
3
5
2
4
7
2
1
4
2
2
8
23
3
5
2
7
4 CSI3505- Paola Flocchini
3
4
2
2
1
2
8
3
La théorie de Complexité
4
2
23
3
5
2
4
7
2
1
2
8
3
–On est capable de construire facilement un arbre recouvrant
minimal (MST) et donc:
Poids(MST) ≤ Poids(T’) ≤ Poids(T)
CSI3505- Paola Flocchini
La théorie de Complexité
Poids(MST) ≤ Poids(T-commis-voya)
Le poids d’un arbre recouvrant minimal représente une borne inférieure pour le problème du commis voyageur
CSI3505- Paola Flocchini
La théorie de Complexité
• 2-approximation pour le problème du
commis voyageur (TSP) – On suppose qu’on a l’inégalité triangulaire
w(a,b) + w(b,c) ≥ w(a,c) pour tout les sommets a, b et c.
Même dans ce cas, le problème est NP-complet
5
a
b
7
CSI3505- Paola Flocchini
4
c
La théorie de Complexité
Algorithme d’approximation
• Construire un arbre recouvrant minimale T avec une racine quelconque r (en utilisant par exemple l’algorithme de Prim)
19
14
10
12
12
7
18
8
14
CSI3505- Paola Flocchini
•On explore l’arbre en utilisant un “pre-ordre” (visiter sommet avant
les fils).
1
8
14
19
5
10
12
12
7
14
4
2
18
3
•Soit L la liste des sommets par ordre de “visite”
2,1,5,3,4
CSI3505- Paola Flocchini
•Retourner le tour qui correspond a l’ordre des sommets dans L.
2,1,5,3,4
1
8
14
19
5
10
12
12
7
14
4
2
18
3
CSI3505- Paola Flocchini
La théorie de Complexité
Exemple:
Tour d’Euler P a partir du MST
Tour correspondent T pour TSP
CSI3505- Paola Flocchini
La théorie de Complexité
Un tour pour TSP (moins une arête) représente un arbre recouvrant donc |M|<|OPT|.
Le tour d’Euler P visite chacune des arêtes de M deux fois, donc |P|=2|M|
Les raccourcis qu’on fait dans P, n’augmente pas le poids total du tour [à cause de l’inégalité triangulaire w(a,b) + w(b,c) > w(a,c) ] donc, |T|<|P|.
Conclusion, |T|<|P|=2|M|<2|OPT|
Tour T obtenu de P
Tour d’Euler P CSI3505- Paola Flocchini
Tour Optimal OPT
La théorie de Complexité
3/2-approximation TSP (Christofides 1976)
Meilleure approximation connue pour TSP
CSI3505- Paola Flocchini