algoritmos aleatorizados sobre grafos - …dma.eui.upm.es/matdis/seminario3/mincut.pdf ·...
TRANSCRIPT
ALGORITMOS ALEATORIZADOSSOBRE GRAFOS
III Seminario de Matemática Discreta14 de junio de 2001
Ángeles Martínez Sánchez Gregoria Blanco Viejo
Matemática Aplicada E. U. Informática
U. P. M.
Algoritmos deterministas
1- Se resuelve el problema correctamente.2- Para cada input, el output siempre es el mismo.3- El número de cálculos es polinomial en el tamaño del
input.4- Operaciones o tipo de datos que precisa la
implementación suelen ser complicados.
input outputalgoritmo
Algoritmos aleatorizados
1- No siempre se resuelve el problema correctamente.2- Para un mismo input, el output puede variar.3- El número de cálculos es polinomial o polilogarítmico en
el tamaño del input.4- La estrategia, las operaciones y el tipo de datos que
precisa la implementación no son complicados.
input outputalgoritmo
Números aleatoriosElecciones aleatorias
Algoritmos aleatorizados:Las Vegas y Monte Carlo
Las Vegas• Siempre se obtiene la solución correcta• Su tiempo de ejecución es una variable aleatoria con
esperanza polinomial
Ejemplo: Ordenación Quicksort de una lista de números• Determinista: Punto de corte mediana → O(nL(n))• Aleatorizado: Punto de corte aleatorio → O(nL(n))
Algoritmos aleatorizados:Las Vegas y Monte Carlo
Monte Carlo• No siempre se obtiene la solución correcta• Probabilidad de fallo acotada• Ejecuciones independientes reducen la cota de error.
Ejemplos:
–Test de primalidad
–Igualdades matriciales
ALGORITMO ALEATORIO•Elegir aleatoriamente X ∈ Mnx1 (K) •Obtener A×(B×X) , C×X•Comparar A×(B×X) = C×X
A×(B×X) = C×X ⇒ A×B = Csi
A×(B×X) ≠ C×X ⇒ A×B ≠C
ALGORITMO DETERMINISTA•Obtener A×B •Comparar A×B = C
K CUERPO FINITO¿A×B = C?
A, B, C ∈ Mnxn (K)
)n(O)n(O ,3823 →
)n(O 2
ANÁLISIS DEL ALGORITMO ALEATORIO
•Si A×B ≠ C ⇒ Algoritmo A×B = C∃ x ≠ 0 / A×(B×X) = C×X ⇔∃ x ≠ 0 / (A×B-C)×X = 0 ⇔∃ x ≠ 0 ∈ Ker(A×B-C)
↑dim(Ker(A×B-C)) = r r<n
•Si A×B = C ⇒ El algoritmo siempre va adevolver la respuesta correcta
KKK
KK
)fallo(P n
n
n
r1
1
=≤=−
mK)ntesindependiepruebasmtrasfallo(P 1≤
e c
a
d
b
k=2
• val(C) ↔ conectividad• aristas de un corte C• |V| = n 2n-1 –1 cortes
G multigrafo conexo G=(V, A)
VC C V / C C Corte =∪⊂≠ ∅
k = min val(C) / C corte CvCu / uv Card val(C) ∈∈=
Problema del mínimo corte
1,1,
0, 0,
0,
0,
2,
2,
mínimo corte ↔ máximo flujoG multigrafo ↔ G grafo ponderado
e
ca
d
b
e
ca
d
b
3
2
11
1 1
val (flujo maximal) = val (corte minimal)
a
d
val(f*) = 3
mínimo corte ↔ máximo flujo
• ¿Se puede mejorar? • ¿Hay algoritmos “específicos”?
s-t cortes mínimos → O(n2)
2n
EDMONDS - KARP → O(m2n)
GOLDBERG, TARJAN → O(mnL(n2/m))
Mejoras
GOMORI - HU → n-1 ejecuciones → 1 ejecución
Algoritmos aleatorizados
Contracciones
G multigrafo conexo G=(V, A) uv∈ A
G´ = ( V´, A´) = G/uv V´ = V - u,v ∪ u´ A´= A - uv / xu →xu´ - bucles vy →u´y
e c
a
d
b
← metavértice
e´ c
a b
G/ed
Contracción ed
Propiedades de las contracciones
e c
a
d
b
e´ c
a b
G/ed
G=(V, A) → G´ = ( V´, A´)
• card(V´) = card(V) - 1• card(A´) < card(A)• Todo corte C´de G´ induce un corte C en G
• Minval(C) / C corte en G ≤ Minval(C´) / C´ corte en G´
Algoritmo CONTRACT KARGER 1992
e c
a
d
b
• Elegir aleatoriamente uv∈V y obtener G´=G/uv• Iterar hasta obtener un grafo con 2 metavértices x,y• Devolver k=grado(x) C=vértices colapsados en x
e c
a b
e
a
e
a
bk=4
XX
X
e c
a
d
b
e´ c
a b
a
b
Otra ejecución del algoritmo:
c
a b
k=2
X
X
X
Análisis del algoritmo CONTRACT
Proposición – G multigrafo, C corte minimal, val(C)=k
• No existe ningún vértice v / g(v)<k
• 2A nk≥
Proposición – Contract proporciona un corte minimal C ⇔durante la ejecución no se suprime ninguna arista de C.
Proposición – La probabilidad de obtener un corte minimalcon el algoritmo Contract es:
Ω∈≥ 22
12nn
P )(acierto
Dem – C corte minimal, val(C)=k
nEP
nAkEPnkA
nVG 212
21
01
0
0
0 −≥≤=
≥
== )(
||)(
||
||
)()/(
)(||)/()(||
||
121
12
21
112
112
1
1
1 −−≥
−≤=
−≥
−==
nEEP
nAkEEPknA
nVG
)()/(
)()/())((||
)(||
121
12
21
1 1
1
1
11
1
1 −−−≥
−−≤
−−≥
−−== ∩∩
−
=
−
=−
−
− inEEP
inEEPkinA
inVG i
i
jii
i
ji
i
i
i
Ei = no elegir una arista de C en el paso i
Ω∈≥ 22
12nn
P )(acierto
=∩∩∩= − )( 221 nEEEP L
≥= ∩−
=− )/()/()( j
n
jn EEPEEPEP
3
12121 L
P(no elegir ninguna arista de C)=
2
2
1
21
21
21nnnin
n
i≥
−=
−−
−≥ ∏−
= )()(
22
212n
Pn
P −≤⇒≥ )()( falloacierto
enfalloPpruebasn n 121 )(
22
2
2 2
<
−≤⇒
¿Coste del algoritmo?
)n(L
e )(Ppruebas)n(Ln
<⇒ 12 fallo
Proposición – El algoritmo CONTRACT se puede implementarde modo que su tiempo de ejecución sea O(n2)
Dem - • G(n,m) → Gn-2)(2,m´) n-2 contracciones O(n)
O(n2)• Contracción: elegir una arista y modificar O(n)
e c
a
d
b
ed
x
∑∑∑ω=ω+ω=
=+=
)v(g)ed(
)d(g)ed(
)v(g)d(g
)e(g)ed(
)v(g)e(g
)d/ed(P)d(P)e/ed(P)e(P)ed(P2
e c
a
d
b
0300230100010110010120110
edcba
edcba
e´ c
a b
0010200000100110010120110
edcba
edcba
54324
30324
x
3245 ×−+=
Observaciones:
• Las cotas inferiores de las probabilidades van decreciendo
Estrategia para mejorar el algoritmo
• El coste “total” es O(n4)
Hay cortes minimales
2n
nEP
nEP 212
11 −=⇒= )()(
121
12
1212 −−=⇒
−=
nEEP
nEEP )/()/(
• Las cotas de las probabilidades de mantener un corteminimal se alcanzan en Cn
FAST-CONTRACT KARGER – STEIN 1993
• Mientras n≥2
−
− G1=contract(G, n→t)− G2=contract(G, n→t)
• Calcular recursivamente cortes de valor mínimo k1 y k2para los grafos G1 y G2.
• Devolver k=mink1, k2
+= 1
2nt
G=(V,A) multigrafo |V|=n
Análisis del algoritmo FAST-CONTRACT
Proposición – La probabilidad de obtener un corte minimalcon el algoritmo Fast-Contract es:
Ω∈)(
)(nL
P 1acierto
Dem.- Sea C un corte minimal val(C)=k
⇔conservaloGGenadrecursividLa
GaoGapasaC
21
21 C corte el conserva C(G)-F
P(G) = P(G→G1)P(G1) + P(G→G2)P(G2) –
P(G→G1)P(G1) P(G→G2)P(G2)
G
G1 G2
Ω∈)(
)(nL
P 1acierto
P(G) = P(G→G1)P(G1) + P(G→G2)P(G2) – P(G→G1)P(G1)P(G→G2)P(G2)
P(n) = Acotación de la probabilidad para un multigrafo de n vértices
)()()()(
+−
++
+≥ 1
2411
2211
221 2 nPnPnPnP
>
+−
+=
=
2124
112
12
2 nnPnPnP
P
)()()(
)(
( ) )(nLmnm
22 ==↓
>−=
=
−− 241
1
211
2
mppp
p
mmm 14
44
1 +<<
++ − mp
Hm mm
))(
()()(nL
nPm
pm11 Θ∈⇒Θ∈
)()(
)()(
nLcP
nLcP −≤⇒≥ 1falloacierto
e)n(Lc )(Ppruebas
c)n(L c
)n(L 11 <
−≤⇒ fallo
¿Coste del algoritmo?
)n(L
e )(Ppruebas)n(L
<⇒ 12 fallo
Proposición – FAST-CONTRACT se puede implementar demodo que su tiempo de ejecución sea O(n 2 L(n))
Dem -
>+
+=
=
212
2
12
2 nnOnTnT
T
)()()(
)(
>+=
=
− 222
1
1
2
mOttt
mmm )(
))(()( nLnOnT 2∈ )( mm mOt 2∈
)(log prof. 2 n
2d ))n(Logn(O)(
)n(O
))(
n(O)n(O)n(O
d
prof
d
d
dd
22
2
0
2
222
212
22
22
=
=
=+
++
+
∑=
LL
Problema del mínimo corte
• GOLDBERG, TARJAN, GOMORI - HU → O(mnL(n2/m))
ALGORITMO DETERMINISTA:
ALGORITMOS ALEATORIZADOS:
• CONTRACT → O(n2)
• FAST-CONTRACT → O(n2L(n)) →
→(n)L
L(n)n
2
2
)(
)(nL
eP
< 1fallo
O(n4L(n))
O(n2L3(n))