Projektowanie obwodów scalonych
ALP520 - Wykład z Algorytmów Probabilistycznych  p.2
Projektowanie obwodów scalonych
" "
macierz n × n
zawierajÄ…ca n bramek
2
1
3
5
4
2
1
3
4
5
ALP520 - Wykład z Algorytmów Probabilistycznych  p.2
Projektowanie obwodów scalonych
" "
macierz n × n
zawierajÄ…ca n bramek
2
1
3
5
zbiór par bramek, które
zostaną połączone za
4
pomocÄ… przewodu (w celu
2
utworzenia logicznego
1
obwodu)
3
4
5
ALP520 - Wykład z Algorytmów Probabilistycznych  p.2
Projektowanie obwodów scalonych
" "
macierz n × n
zawierajÄ…ca n bramek
2
1
3
5
zbiór par bramek, które
zostaną połączone za
4
pomocÄ… przewodu (w celu
2
utworzenia logicznego
1
obwodu)
3
przewody mogÄ… biec tylko
4
pionowo i poziomo, możliwe
5
jest jedno zgięcie ("plan
Manhattanu")
ALP520 - Wykład z Algorytmów Probabilistycznych  p.2
Projektowanie obwodów scalonych
" "
macierz n × n
zawierajÄ…ca n bramek
2
1
3
5
zbiór par bramek, które
zostaną połączone za
4
pomocÄ… przewodu (w celu
2
utworzenia logicznego
1
obwodu)
3
przewody mogÄ… biec tylko
4
pionowo i poziomo, możliwe
5
jest jedno zgięcie ("plan
Manhattanu")
PrzykÅ‚ad: n = 16, 4×4, 5 prze-
wodów
ALP520 - Wykład z Algorytmów Probabilistycznych  p.2
Projektowanie obwodów scalonych
Problem: wyznaczyć fizyczną
2
1
3
5
ścieżkę dla każdego prze-
wodu Å‚Ä…czÄ…cego dwie bramki
przy ograniczeniach prze-
4
2
strzennych.
1
3
4
5
ALP520 - Wykład z Algorytmów Probabilistycznych  p.3
Projektowanie obwodów scalonych
Problem: wyznaczyć fizyczną
2
1
3
5
ścieżkę dla każdego prze-
wodu Å‚Ä…czÄ…cego dwie bramki
przy ograniczeniach prze-
4
2
strzennych.
Interesuje nas tylko tzw. glo- 1
bal wiring problem, tzn. ciÄ…g bra-
3
mek, przez które będzie prze-
4
biegał dany przewód (ignoru-
5
jemy jego pozycję względem
innego przewodu).
ALP520 - Wykład z Algorytmów Probabilistycznych  p.3
Projektowanie obwodów scalonych
Problem: wyznaczyć fizyczną
2
1
3
5
ścieżkę dla każdego prze-
wodu Å‚Ä…czÄ…cego dwie bramki
przy ograniczeniach prze-
4
2
strzennych.
Interesuje nas tylko tzw. glo- 1
bal wiring problem, tzn. ciÄ…g bra-
3
mek, przez które będzie prze-
4
biegał dany przewód (ignoru-
5
jemy jego pozycję względem
innego przewodu).
Cel: zminimalizować liczbę przewodów przechodzących
przez obszar jednej bramki.
ALP520 - Wykład z Algorytmów Probabilistycznych  p.3
Projektowanie obwodów scalonych
Niech b będzie granicą pomiędzy obszarami dwóch
sÄ…siadujÄ…cych bramek.
wS(b) = liczba przewodów przechodzących przez b w
rozwiÄ…zaniu S
wS = maxb wS(b)
ALP520 - Wykład z Algorytmów Probabilistycznych  p.4
Projektowanie obwodów scalonych
Niech b będzie granicą pomiędzy obszarami dwóch
sÄ…siadujÄ…cych bramek.
wS(b) = liczba przewodów przechodzących przez b w
rozwiÄ…zaniu S
wS = maxb wS(b)
Problem optymalizacyjny: zminimalizować wS
ALP520 - Wykład z Algorytmów Probabilistycznych  p.4
Projektowanie obwodów scalonych
Niech b będzie granicą pomiędzy obszarami dwóch
sÄ…siadujÄ…cych bramek.
wS(b) = liczba przewodów przechodzących przez b w
rozwiÄ…zaniu S
wS = maxb wS(b)
Problem optymalizacyjny: zminimalizować wS
Decyzja: wybór jednej z dwóch możliwości dla każdej pary
bramek: (uproszczenie realnej sytuacji)
ALP520 - Wykład z Algorytmów Probabilistycznych  p.4
Projektowanie obwodów scalonych
Niech b będzie granicą pomiędzy obszarami dwóch
sÄ…siadujÄ…cych bramek.
wS(b) = liczba przewodów przechodzących przez b w
rozwiÄ…zaniu S
wS = maxb wS(b)
Problem optymalizacyjny: zminimalizować wS
Decyzja: wybór jednej z dwóch możliwości dla każdej pary
bramek: (uproszczenie realnej sytuacji)
poziomo, potem pionowo - HV (horizontal-vertical)
pionowo, potem poziomo - VH (vertical-horizontal)
ALP520 - Wykład z Algorytmów Probabilistycznych  p.4
Projektowanie obwodów scalonych
Niech b będzie granicą pomiędzy obszarami dwóch
sÄ…siadujÄ…cych bramek.
wS(b) = liczba przewodów przechodzących przez b w
rozwiÄ…zaniu S
wS = maxb wS(b)
Problem optymalizacyjny: zminimalizować wS
Decyzja: wybór jednej z dwóch możliwości dla każdej pary
bramek: (uproszczenie realnej sytuacji)
poziomo, potem pionowo - HV (horizontal-vertical)
pionowo, potem poziomo - VH (vertical-horizontal)
Uwaga: tylko pionowe lub poziome linie nie wpływają na roz-
wiÄ…zanie, stÄ…d nie sÄ… rozpatrywane
ALP520 - Wykład z Algorytmów Probabilistycznych  p.4
Metoda: rzucić monetą ??
ALP520 - Wykład z Algorytmów Probabilistycznych  p.5
Metoda: rzucić monetą ??
Efekt rzutu monetÄ… :
ALP520 - Wykład z Algorytmów Probabilistycznych  p.5
Metoda: rzucić monetą ??
1 t
b
Efekt rzutu monetÄ… :
1
t
ALP520 - Wykład z Algorytmów Probabilistycznych  p.5
Metoda: rzucić monetą ??
1 t
b
Efekt rzutu monetÄ… : Przy
t
losowym wyborze średnio
2
1
przewodów spośród t będzie
przechodzić przez granicę b.
t
ALP520 - Wykład z Algorytmów Probabilistycznych  p.5
Metoda: rzucić monetą ??
1 t
b
Efekt rzutu monetÄ… : Przy
t
losowym wyborze średnio
2
1
przewodów spośród t będzie
przechodzić przez granicę b.
t
Nie od razu, lepiej trochę poczekać. Istnieje lepsze
rozwiÄ…zanie.
ALP520 - Wykład z Algorytmów Probabilistycznych  p.5
Metoda: rzucić monetą ??
1 t
b
Efekt rzutu monetÄ… : Przy
t
losowym wyborze średnio
2
1
przewodów spośród t będzie
przechodzić przez granicę b.
t
Nie od razu, lepiej trochę poczekać. Istnieje lepsze
rozwiÄ…zanie.
ALP520 - Wykład z Algorytmów Probabilistycznych  p.5
Zagadnienie Programowania Liniowego 0-1
ALP520 - Wykład z Algorytmów Probabilistycznych  p.6
Zagadnienie Programowania Liniowego 0-1
Niech

1 gdy HV - |
xi =
0 gdy V H | -
ALP520 - Wykład z Algorytmów Probabilistycznych  p.6
Zagadnienie Programowania Liniowego 0-1
Niech

1 gdy HV - |
xi =
0 gdy V H | -
Niech Bb ozn. zbiór i : para i może być połączona
przewodem przechodzÄ…cym przez b oraz
HVb =  Bb )" HV  V Hb = Bb )" V H
ALP520 - Wykład z Algorytmów Probabilistycznych  p.6
Zagadnienie Programowania Liniowego 0-1
Niech

1 gdy HV - |
xi =
0 gdy V H | -
Niech Bb ozn. zbiór i : para i może być połączona
przewodem przechodzÄ…cym przez b oraz
HVb =  Bb )" HV  V Hb = Bb )" V H
Funkcja celu:
f(x) = maxbwb(x) min
Ograniczenia:

xi + (1 - xi) d" wb(x), "b
i"HVb i"V Hb
oraz xi " {0, 1} "i.
ALP520 - Wykład z Algorytmów Probabilistycznych  p.6
Zagadnienie Programowania Liniowego 0-1
Niech

1 gdy HV - |
xi =
0 gdy V H | -
Niech Bb ozn. zbiór i : para i może być połączona
przewodem przechodzÄ…cym przez b oraz
HVb =  Bb )" HV  V Hb = Bb )" V H
Funkcja celu:
f(x) = maxbwb(x) min
Ograniczenia:

xi + (1 - xi) d" wb(x), "b
i"HVb i"V Hb
oraz xi " {0, 1} "i.
To jeszcze nie jest poprawne zagdanienie programowania
liniowego.
ALP520 - Wykład z Algorytmów Probabilistycznych  p.6
Zagadnienie Programowania Liniowego 0-1
ALP520 - Wykład z Algorytmów Probabilistycznych  p.7
Zagadnienie Programowania Liniowego 0-1
Wprowadzamy dodatkową zmienną w (aby wyeliminować
max).
ALP520 - Wykład z Algorytmów Probabilistycznych  p.7
Zagadnienie Programowania Liniowego 0-1
Wprowadzamy dodatkową zmienną w (aby wyeliminować
max).
ZPL-01:
Zminimalizuj f(x, w) = w, aby "b

xi + (1 - xi) - w d" 0,
i"HVb i"V Hb
gdy xi " {0, 1} "i, w > 0
ALP520 - Wykład z Algorytmów Probabilistycznych  p.7
Zagadnienie Programowania Liniowego 0-1
Wprowadzamy dodatkową zmienną w (aby wyeliminować
max).
ZPL-01:
Zminimalizuj f(x, w) = w, aby "b

xi + (1 - xi) - w d" 0,
i"HVb i"V Hb
gdy xi " {0, 1} "i, w > 0
Ten problem jest NP-trudny! ( nie ma szans na efektywne
obliczenie optymalnego rozwiÄ…zania).
ALP520 - Wykład z Algorytmów Probabilistycznych  p.7
Relaksacja Zagadnienia Prog. Liniowego
ALP520 - Wykład z Algorytmów Probabilistycznych  p.8
Relaksacja Zagadnienia Prog. Liniowego
Zamiast xi " {0, 1} dopuszczamy xi " [0; 1](ZRPL)
Zysk: istnieje wiele efektywnych algorytmów rozwiązujących
ten problem. (alg. Simplex, alg. elipsoidalny, metoda punktu
wewnętrznego)
ALP520 - Wykład z Algorytmów Probabilistycznych  p.8
Relaksacja Zagadnienia Prog. Liniowego
Zamiast xi " {0, 1} dopuszczamy xi " [0; 1](ZRPL)
Zysk: istnieje wiele efektywnych algorytmów rozwiązujących
ten problem. (alg. Simplex, alg. elipsoidalny, metoda punktu
wewnętrznego)
Niech
xi (1 d" i d" n) będzie rozwiązaniem problemu ZRPL oraz u

Ć
będzie wartością opowiadającą temu rozwiązaniu.
ALP520 - Wykład z Algorytmów Probabilistycznych  p.8
Relaksacja Zagadnienia Prog. Liniowego
Zamiast xi " {0, 1} dopuszczamy xi " [0; 1](ZRPL)
Zysk: istnieje wiele efektywnych algorytmów rozwiązujących
ten problem. (alg. Simplex, alg. elipsoidalny, metoda punktu
wewnętrznego)
Niech
xi (1 d" i d" n) będzie rozwiązaniem problemu ZRPL oraz u

Ć
będzie wartością opowiadającą temu rozwiązaniu.
w0 będzie maksymalną liczbą przewodów przechodzących
przez wszystkie granice bramek w optymalnym rozwiÄ…zaniu.
ALP520 - Wykład z Algorytmów Probabilistycznych  p.8
Relaksacja Zagadnienia Prog. Liniowego
Zamiast xi " {0, 1} dopuszczamy xi " [0; 1](ZRPL)
Zysk: istnieje wiele efektywnych algorytmów rozwiązujących
ten problem. (alg. Simplex, alg. elipsoidalny, metoda punktu
wewnętrznego)
Niech
xi (1 d" i d" n) będzie rozwiązaniem problemu ZRPL oraz u

Ć
będzie wartością opowiadającą temu rozwiązaniu.
w0 będzie maksymalną liczbą przewodów przechodzących
przez wszystkie granice bramek w optymalnym rozwiÄ…zaniu.
Oczywiście u
d" w0.
ALP520 - Wykład z Algorytmów Probabilistycznych  p.8
Relaksacja Zagadnienia Prog. Liniowego
Zamiast xi " {0, 1} dopuszczamy xi " [0; 1](ZRPL)
Zysk: istnieje wiele efektywnych algorytmów rozwiązujących
ten problem. (alg. Simplex, alg. elipsoidalny, metoda punktu
wewnętrznego)
Niech
xi (1 d" i d" n) będzie rozwiązaniem problemu ZRPL oraz u

Ć
będzie wartością opowiadającą temu rozwiązaniu.
w0 będzie maksymalną liczbą przewodów przechodzących
przez wszystkie granice bramek w optymalnym rozwiÄ…zaniu.
Oczywiście u
d" w0.
Ale xi może być ułamkiem. Trzeba zaokrąglić do 0 lub 1.
Ć
ALP520 - Wykład z Algorytmów Probabilistycznych  p.8
Losowe zaokrÄ…glanie (randomized rounding)
Zaokrąglić xi do wartości całkowitej (0 lub 1) xi z
Ć Ż
prawdopodobieństwem
Pr(xi = 1) = xi E(xi) = xi
Ż Ć Ż Ć
ALP520 - Wykład z Algorytmów Probabilistycznych  p.9
Losowe zaokrÄ…glanie (randomized rounding)
Zaokrąglić xi do wartości całkowitej (0 lub 1) xi z
Ć Ż
prawdopodobieństwem
Pr(xi = 1) = xi E(xi) = xi
Ż Ć Ż Ć
Ustalmy granicę b. Liczba wS(b) przewodów przechodzących
przez b w rozwiÄ…zaniu S (ZRPL+losowe zaokrÄ…glanie) jest
zmiennÄ… losowÄ….
ALP520 - Wykład z Algorytmów Probabilistycznych  p.9
Losowe zaokrÄ…glanie (randomized rounding)
Zaokrąglić xi do wartości całkowitej (0 lub 1) xi z
Ć Ż
prawdopodobieństwem
Pr(xi = 1) = xi E(xi) = xi
Ż Ć Ż Ć
Ustalmy granicę b. Liczba wS(b) przewodów przechodzących
przez b w rozwiÄ…zaniu S (ZRPL+losowe zaokrÄ…glanie) jest
zmiennÄ… losowÄ….

wS(b) = xi + (1 - xi)
Å» Å»
i"HVb i"V Hb
ALP520 - Wykład z Algorytmów Probabilistycznych  p.9
Losowe zaokrÄ…glanie (randomized rounding)
Zaokrąglić xi do wartości całkowitej (0 lub 1) xi z
Ć Ż
prawdopodobieństwem
Pr(xi = 1) = xi E(xi) = xi
Ż Ć Ż Ć
Ustalmy granicę b. Liczba wS(b) przewodów przechodzących
przez b w rozwiÄ…zaniu S (ZRPL+losowe zaokrÄ…glanie) jest
zmiennÄ… losowÄ….

wS(b) = xi + (1 - xi
Å» Å»
i"HVb i"V Hb
)
µw (b) = E(wS(b)) = xi + (1 - xi) d" u
d" w0
Ć Ć
S i"HVb i"V Hb
ALP520 - Wykład z Algorytmów Probabilistycznych  p.9
Losowe zaokrÄ…glanie (randomized rounding)
Zaokrąglić xi do wartości całkowitej (0 lub 1) xi z
Ć Ż
prawdopodobieństwem
Pr(xi = 1) = xi E(xi) = xi
Ż Ć Ż Ć
Ustalmy granicę b. Liczba wS(b) przewodów przechodzących
przez b w rozwiÄ…zaniu S (ZRPL+losowe zaokrÄ…glanie) jest
zmiennÄ… losowÄ….

wS(b) = xi + (1 - xi
Å» Å»
i"HVb i"V Hb
)
µw (b) = E(wS(b)) = xi + (1 - xi) d" u
d" w0
Ć Ć
S i"HVb i"V Hb
Niech µ = µw (b).
S
ALP520 - Wykład z Algorytmów Probabilistycznych  p.9
Losowe zaokrÄ…glanie (randomized rounding)
Zaokrąglić xi do wartości całkowitej (0 lub 1) xi z
Ć Ż
prawdopodobieństwem
Pr(xi = 1) = xi E(xi) = xi
Ż Ć Ż Ć
Ustalmy granicę b. Liczba wS(b) przewodów przechodzących
przez b w rozwiÄ…zaniu S (ZRPL+losowe zaokrÄ…glanie) jest
zmiennÄ… losowÄ….

wS(b) = xi + (1 - xi
Å» Å»
i"HVb i"V Hb
)
µw (b) = E(wS(b)) = xi + (1 - xi) d" u
d" w0
Ć Ć
S i"HVb i"V Hb
Niech µ = µw (b). KorzystajÄ…c z nierównoÅ›ci Chernoffa (1):
S
ALP520 - Wykład z Algorytmów Probabilistycznych  p.9
Losowe zaokrÄ…glanie (randomized rounding)
Zaokrąglić xi do wartości całkowitej (0 lub 1) xi z
Ć Ż
prawdopodobieństwem
Pr(xi = 1) = xi E(xi) = xi
Ż Ć Ż Ć
Ustalmy granicę b. Liczba wS(b) przewodów przechodzących
przez b w rozwiÄ…zaniu S (ZRPL+losowe zaokrÄ…glanie) jest
zmiennÄ… losowÄ….

wS(b) = xi + (1 - xi
Å» Å»
i"HVb i"V Hb
)
µw (b) = E(wS(b)) = xi + (1 - xi) d" u
d" w0
Ć Ć
S i"HVb i"V Hb
Niech µ = µw (b). KorzystajÄ…c z nierównoÅ›ci Chernoffa (1):
S

t2
Pr(X e" µ + t) d" exp -
2(µ+t/3)
ALP520 - Wykład z Algorytmów Probabilistycznych  p.9
Losowe zaokrÄ…glanie (randomized rounding)
Zaokrąglić xi do wartości całkowitej (0 lub 1) xi z
Ć Ż
prawdopodobieństwem
Pr(xi = 1) = xi E(xi) = xi
Ż Ć Ż Ć
Ustalmy granicę b. Liczba wS(b) przewodów przechodzących
przez b w rozwiÄ…zaniu S (ZRPL+losowe zaokrÄ…glanie) jest
zmiennÄ… losowÄ….

wS(b) = xi + (1 - xi
Å» Å»
i"HVb i"V Hb
)
µw (b) = E(wS(b)) = xi + (1 - xi) d" u
d" w0
Ć Ć
S i"HVb i"V Hb
Niech µ = µw (b). KorzystajÄ…c z nierównoÅ›ci Chernoffa (1):
S
2
·2w0
Pr(wS(b) e" (1 + ·)w0) d" Pr(wS(b) e" µ + ·w0) d" exp(- ) d"
·w0
2(µ+ )
3
·2w0
·2w0
4
exp(- ) < e- .
·
2(1+ )
3
ALP520 - Wykład z Algorytmów Probabilistycznych  p.9
Losowe zaokrÄ…glanie (randomized rounding)
·2w0
4
OtrzymaliÅ›my, że Pr(wS(b) e" (1 + ·)w0) d" e- , dla · < 3.
ALP520 - Wykład z Algorytmów Probabilistycznych  p.10
Losowe zaokrÄ…glanie (randomized rounding)
·2w0
4
OtrzymaliÅ›my, że Pr(wS(b) e" (1 + ·)w0) d" e- , dla · < 3. To
musi zachodzić dla każdej granicy b (jest ich co najwyżej 2n).
ALP520 - Wykład z Algorytmów Probabilistycznych  p.10
Losowe zaokrÄ…glanie (randomized rounding)
·2w0
4
OtrzymaliÅ›my, że Pr(wS(b) e" (1 + ·)w0) d" e- , dla · < 3. To
musi zachodzić dla każdej granicy b (jest ich co najwyżej 2n).
Zatem
·2w0
·2w0
4
2ne- 0 gdy - ln(2n) "
4
ALP520 - Wykład z Algorytmów Probabilistycznych  p.10
Losowe zaokrÄ…glanie (randomized rounding)
·2w0
4
OtrzymaliÅ›my, że Pr(wS(b) e" (1 + ·)w0) d" e- , dla · < 3. To
musi zachodzić dla każdej granicy b (jest ich co najwyżej 2n).
Zatem
·2w0
·2w0
4
2ne- 0 gdy - ln(2n) "
4

ln n+ln ln n
czyli · = 2
w0
ALP520 - Wykład z Algorytmów Probabilistycznych  p.10
Losowe zaokrÄ…glanie (randomized rounding)
·2w0
4
OtrzymaliÅ›my, że Pr(wS(b) e" (1 + ·)w0) d" e- , dla · < 3. To
musi zachodzić dla każdej granicy b (jest ich co najwyżej 2n).
Zatem
·2w0
·2w0
4
2ne- 0 gdy - ln(2n) "
4

ln n+ln ln n
czyli · = 2
w0
Uwaga:
Powyższe oszacowanie jest dobre o ile wartość optymalna
Å‚
3
jest duża, w0 H" nł, ł > 0. Wtedy wS d" (1 + o(n- ))w0.
ALP520 - Wykład z Algorytmów Probabilistycznych  p.10
Losowe zaokrÄ…glanie (randomized rounding)
·2w0
4
OtrzymaliÅ›my, że Pr(wS(b) e" (1 + ·)w0) d" e- , dla · < 3. To
musi zachodzić dla każdej granicy b (jest ich co najwyżej 2n).
Zatem
·2w0
·2w0
4
2ne- 0 gdy - ln(2n) "
4

ln n+ln ln n
czyli · = 2
w0
Uwaga:
Powyższe oszacowanie jest dobre o ile wartość optymalna
Å‚
3
jest duża, w0 H" nł, ł > 0. Wtedy wS d" (1 + o(n- ))w0.
Jeśli w0 jest małe, to wystarczy rozwiązanie poniższego
zadania.
ALP520 - Wykład z Algorytmów Probabilistycznych  p.10
Losowe zaokrÄ…glanie (randomized rounding)
·2w0
4
OtrzymaliÅ›my, że Pr(wS(b) e" (1 + ·)w0) d" e- , dla · < 3. To
musi zachodzić dla każdej granicy b (jest ich co najwyżej 2n).
Zatem
·2w0
·2w0
4
2ne- 0 gdy - ln(2n) "
4

ln n+ln ln n
czyli · = 2
w0
Uwaga:
Powyższe oszacowanie jest dobre o ile wartość optymalna
Å‚
3
jest duża, w0 H" nł, ł > 0. Wtedy wS d" (1 + o(n- ))w0.
Jeśli w0 jest małe, to wystarczy rozwiązanie poniższego
zadania.
Zadanie. Podaj prostą metodę zaokrąglania, która zagwarantuje
rozwiązanie, dla którego wS d" 2w0, gdzie w0 jest wartością w
rozwiÄ…zaniu optymalnym.
ALP520 - Wykład z Algorytmów Probabilistycznych  p.10
Problem MAX-SAT (Maximum satisfiability)
ALP520 - Wykład z Algorytmów Probabilistycznych  p.11
Problem MAX-SAT (Maximum satisfiability)
zmienne Boolowskie: xi " {true(1), false(0)}
literały: xi, xi(negacja)
Å»
klauzule: np. x1 (" x3 (" x4
Å»
formuła w koniunkcyjnej postaci normalnej (CNF):
C1 '" C2 '" . . ., gdzie Ci jest klauzulą (alternatywą literałów)
ALP520 - Wykład z Algorytmów Probabilistycznych  p.11
Problem MAX-SAT (Maximum satisfiability)
zmienne Boolowskie: xi " {true(1), false(0)}
literały: xi, xi(negacja)
Å»
klauzule: np. x1 (" x3 (" x4
Å»
formuła w koniunkcyjnej postaci normalnej (CNF):
C1 '" C2 '" . . ., gdzie Ci jest klauzulą (alternatywą literałów)
FormuÅ‚a jest PRAWDZIWA Ð!Ò! każda klauzula jest prawdziwa
ALP520 - Wykład z Algorytmów Probabilistycznych  p.11
Problem MAX-SAT (Maximum satisfiability)
zmienne Boolowskie: xi " {true(1), false(0)}
literały: xi, xi(negacja)
Å»
klauzule: np. x1 (" x3 (" x4
Å»
formuła w koniunkcyjnej postaci normalnej (CNF):
C1 '" C2 '" . . ., gdzie Ci jest klauzulą (alternatywą literałów)
FormuÅ‚a jest PRAWDZIWA Ð!Ò! każda klauzula jest prawdziwa
Formuła jest spełnialna jeśli istnieje prawdziwe
wartościowanie.
ALP520 - Wykład z Algorytmów Probabilistycznych  p.11
Problem MAX-SAT (Maximum satisfiability)
zmienne Boolowskie: xi " {true(1), false(0)}
literały: xi, xi(negacja)
Å»
klauzule: np. x1 (" x3 (" x4
Å»
formuła w koniunkcyjnej postaci normalnej (CNF):
C1 '" C2 '" . . ., gdzie Ci jest klauzulą (alternatywą literałów)
FormuÅ‚a jest PRAWDZIWA Ð!Ò! każda klauzula jest prawdziwa
Formuła jest spełnialna jeśli istnieje prawdziwe
wartościowanie.
Problemy decyzyjne:
SAT - czy istnieje prawdziwe wartościowanie dla danej
formuły?
k-SAT- czy istnieje prawdziwe wartościowanie dla danej for-
muły, w której |Ci| = k, "i?
ALP520 - Wykład z Algorytmów Probabilistycznych  p.11
Problem MAX-SAT (Maximum satisfiability)
zmienne Boolowskie: xi " {true(1), false(0)}
literały: xi, xi(negacja)
Å»
klauzule: np. x1 (" x3 (" x4
Å»
formuła w koniunkcyjnej postaci normalnej (CNF):
C1 '" C2 '" . . ., gdzie Ci jest klauzulą (alternatywą literałów)
FormuÅ‚a jest PRAWDZIWA Ð!Ò! każda klauzula jest prawdziwa
Formuła jest spełnialna jeśli istnieje prawdziwe
wartościowanie.
Problemy decyzyjne:
SAT - czy istnieje prawdziwe wartościowanie dla danej
formuły?
k-SAT- czy istnieje prawdziwe wartościowanie dla danej for-
muły, w której |Ci| = k, "i?
ALP520 - Wykład z Algorytmów Probabilistycznych  p.11
Problem optymalizacyjny MAX-SAT
MAX-SAT - znalez
ć wartościowanie, które maksymalizuje liczbę
spełnionych klauzul.
ALP520 - Wykład z Algorytmów Probabilistycznych  p.12
Problem optymalizacyjny MAX-SAT
MAX-SAT - znalez
ć wartościowanie, które maksymalizuje liczbę
spełnionych klauzul.
Założenie: żadna klauzula nie zawiera x oraz x.
Å»
ALP520 - Wykład z Algorytmów Probabilistycznych  p.12
Problem optymalizacyjny MAX-SAT
MAX-SAT - znalez
ć wartościowanie, które maksymalizuje liczbę
spełnionych klauzul.
Założenie: żadna klauzula nie zawiera x oraz x.
Å»
Przykład: Dana jest formuła Boolowska Ć w postaci
CNF(kpn):
Ć = (x1 (" x2 (" x4) '" (x3 (" x4 (" x5) '" (x1 (" x2 (" x4 (" x5)
Å» Å» Å» Å» Å»
ALP520 - Wykład z Algorytmów Probabilistycznych  p.12
Problem optymalizacyjny MAX-SAT
MAX-SAT - znalez
ć wartościowanie, które maksymalizuje liczbę
spełnionych klauzul.
Założenie: żadna klauzula nie zawiera x oraz x.
Å»
Przykład: Dana jest formuła Boolowska Ć w postaci
CNF(kpn):
Ć = (x1 (" x2 (" x4) '" (x3 (" x4 (" x5) '" (x1 (" x2 (" x4 (" x5)
Å» Å» Å» Å» Å»
SAT- problem NP -zupełny (pierwszy generyczny dowód
(Cook))
MAX-SAT jest NP -trudny
ALP520 - Wykład z Algorytmów Probabilistycznych  p.12
Algorytm aproksymacyjny dla MAX-SAT
ALP520 - Wykład z Algorytmów Probabilistycznych  p.13
Algorytm aproksymacyjny dla MAX-SAT
1. Metoda (losowa konstrukcja)
ALP520 - Wykład z Algorytmów Probabilistycznych  p.13
Algorytm aproksymacyjny dla MAX-SAT
1. Metoda (losowa konstrukcja)
Twierdzenie 1. Dla każdej formuły o m klauzulach istnieje
wartościowanie, w którym co najmniej połowa klauzul jest spełniona.
ALP520 - Wykład z Algorytmów Probabilistycznych  p.13
Algorytm aproksymacyjny dla MAX-SAT
1. Metoda (losowa konstrukcja)
Twierdzenie 1. Dla każdej formuły o m klauzulach istnieje
wartościowanie, w którym co najmniej połowa klauzul jest spełniona.
Dowód:
Rzuć uczciwą monetą. "i :
ALP520 - Wykład z Algorytmów Probabilistycznych  p.13
Algorytm aproksymacyjny dla MAX-SAT
1. Metoda (losowa konstrukcja)
Twierdzenie 1. Dla każdej formuły o m klauzulach istnieje
wartościowanie, w którym co najmniej połowa klauzul jest spełniona.
Dowód:
Rzuć uczciwą monetą. "i :

1
1 z prawd.
2
xi =
1
0 z prawd.
2
ALP520 - Wykład z Algorytmów Probabilistycznych  p.13
Algorytm aproksymacyjny dla MAX-SAT
1. Metoda (losowa konstrukcja)
Twierdzenie 1. Dla każdej formuły o m klauzulach istnieje
wartościowanie, w którym co najmniej połowa klauzul jest spełniona.
Dowód:
Rzuć uczciwą monetą. "i :

1
1 z prawd.
2
xi =
1
0 z prawd.
2
Wtedy "0 d" i d" m niech

1 jeśli Ci true
Zi =
0 w przec. przypadku
ALP520 - Wykład z Algorytmów Probabilistycznych  p.13
Losowa konstrukcja - cd.
ALP520 - Wykład z Algorytmów Probabilistycznych  p.14
Losowa konstrukcja - cd.
m

liczba spełnionych klauzul: Z = Zi.
i=1
ALP520 - Wykład z Algorytmów Probabilistycznych  p.14
Losowa konstrukcja - cd.
m

liczba spełnionych klauzul: Z = Zi.
i=1
EZi = Pr(Ci = 1) = 1 - Pr(Ci = 0) =
1 1
1 - e"
i
2
2|C |
ALP520 - Wykład z Algorytmów Probabilistycznych  p.14
Losowa konstrukcja - cd.
m

liczba spełnionych klauzul: Z = Zi.
i=1
EZi = Pr(Ci = 1) = 1 - Pr(Ci = 0) =
1 1
1 - e"
i
2
2|C |
m

m
zatem EZ = EZi e" .
2
i=1
m
Z tego wynika, że " wartoÅ›ciowanie É : Zw e" .
2
ALP520 - Wykład z Algorytmów Probabilistycznych  p.14
Losowa konstrukcja - cd.
m

liczba spełnionych klauzul: Z = Zi.
i=1
EZi = Pr(Ci = 1) = 1 - Pr(Ci = 0) =
1 1
1 - e"
i
2
2|C |
m

m
zatem EZ = EZi e" .
2
i=1
m
Z tego wynika, że " wartoÅ›ciowanie É : Zw e" .
2
Czy można to poprawić? - nie bo x '" x.
Å»
ALP520 - Wykład z Algorytmów Probabilistycznych  p.14