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
dun probl me
Un algorithme A est optimal (dans le cas pire) pour P
si on peut montrer quil 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 quun algorithme est optimal ?
Trouver une borne inf rieure (Lower Bound) sur le
nombre dop rations n cessaires pour r soudre P.
Cest dire que pour tous les algorithmes A on
doit prouver que:
WA(n) e 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 d WA(n) d n2.376
CSI3505- Paola Flocchini
La th orie de Complexit
" Exemple 2: recherche dun l ment dans une liste
de n nombres
Il existe une borne inf rieure pour ce probl me: n
Donc lalgorithme de recherche s quentielle est
optimal
CSI3505- Paola Flocchini
La th orie de Complexit
Exemple: Tri (bas sur les comparaisons des clefs)
On sait quil 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 nSud interne repr sente
une comparaison de lalgorithme
Exemple du tri par insertion: pour le cas n=3
CSI3505- Paola Flocchini
La th orie de Complexit
Trier trois nombres avec lalgorithme du tri par insertion:
comportement de lalgorithme pour (5,7,2)
Chaque type dentr e
correspond un chemin de la
racine une feuille dans larbre
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
cda d b
La th orie de Complexit
Arbres de d cision
oui
a < b
non
oui
ad bdc
b<c
non
a<c
b<c
oui
a<c
non
cdbda
oui
non
oui
non
adcdb
cdadb
bd adc
bdcda
CSI3505- Paola Flocchini
(3,8,1)
oui
a < b
non
oui
ad bdc
b<c
non
a<c
b<c
oui
a<c
non
cdbda
oui
non
oui
non
adcdb
cdadb
bd adc
1,3,8
CSI3505- Paola Flocchini
bdcda
La th orie de Complexit
Profondeur: longueur du plus long chemin de la racine
aux feuilles
Propri t des arbres binaires
1.
2d e k
d = profondeur, k = nombre de feuilles
(preuve par induction sur d)
2.
Un arbre binaire avec k feuilles a une profondeur
d e log k
Preuve
2d e k
log 2d e log k
d e 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) e log t
(t est le nombre des feuilles dans larbre 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 e n !
WA(n) e log t e 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 linput 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
sil ny 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
Lutilit de cette classification?
" Si le probl me est non traitable: ne sert a rien dessayer
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 quil existe des probl mes
quon ne pourra jamais r soudre: non
Advertisement
d cidable
Exemple: Probl me darr t
CSI3505- Paola Flocchini
La th orie de Complexit
Probl me darr 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 sarr tera jamais)
CSI3505- Paola Flocchini
La th orie de Complexit
Pour plusieurs probl mes pratiques, personne na
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 dune 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, lunique 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
La th orie de Complexit
" La plupart des probl mes doptimisation peuvent
tre convertis des probl mes de d cision.
" Il suffit dajouter 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 doptimisation dun 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 sil 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 sil 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
cest 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 cest 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 cest 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 dun
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 sil 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
lensemble 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
Advertisement
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
lalgorithme 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
lalgorithme 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
alors B est NP-complete
CSI3505- Paola Flocchini
La th orie de Complexit
"
Prouver quun 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 quon sait d j quil 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 linstance I du probl me A est OUI alors
la r ponse a linstance T(I) du probl me B est OUI
" Si la r ponse a linstance T(I) du probl me B est OUI
alors la r ponse a linstance 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 d 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
lexpression 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 sils proviennent de deux clauses
diff rentes et que leurs litt raux sont consistent lun
nest pas la n gation de lautre
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 )
Advertisement
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
lexpression 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 davoir 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 uVou vV).
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,vV, (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 dentiers 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 e k.
Le probl me PLC est NP-complet.
Supposons quon 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
e |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 d k?.
Le probl me TCP est NP-complet.
Supposons quon 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 cest 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
Advertisement
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 dau plus (n2) pour effectuer la transformation (Cr er la
matrice dadjacence pour G).
Supposons quil 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
linput G pour le probl me TSP.
Supposons quil 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 linput 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 lalgorithme 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
d
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
d
la valeur d'une solution optimale notre probl me
connu
d
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) d 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) d Poids(T) d Poids(T)
CSI3505- Paola Flocchini
La th orie de Complexit
Poids(MST) d Poids(T-commis-voya)
Le poids dun 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 quon a lin galit triangulaire
w(a,b) + w(b,c) e 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 dapproximation
" Construire un arbre recouvrant minimale T avec une racine
quelconque r (en utilisant par exemple lalgorithme de Prim)
19
14
10
12
12
7
18
8
14
CSI3505- Paola Flocchini
"On explore larbre 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 lordre 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 dEuler 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 dEuler P visite chacune des ar tes de M deux fois,
donc |P|=2|M|
Les raccourcis quon fait dans P, naugmente pas le poids
total du tour [ cause de lin 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 dEuler 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