Xem mẫu
- Giaûi Thuaät Xaáp Xæ
Chapter 37
Approximation Algorithms
- Tieáp caän moät baøi toaùn NP-ñaày ñuû
° Neáu moät baøi toaùn laø NP-ñaày ñuû thì khoâng chaéc raèng ta seõ tìm ñöôïc
moät giaûi thuaät thôøi gian ña thöùc ñeå giaûi noù moät caùch chính xaùc.
° Tieáp caän moät baøi toaùn NP-ñaày ñuû
1) Neáu caùc input coù kích thöôùc nhoû thì moät giaûi thuaät chaïy trong thôøi
gian soá muõ vaãn coù theå thoaû maõn yeâu caàu
2) Thay vì tìm caùc lôøi giaûi toái öu, coù theå tìm caùc lôøi giaûi gaàn toái öu
trong thôøi gian ña thöùc.
21.5.2004 Chöông 37 2
Approximation Algorithms
- Giaûi thuaät xaáp xæ
° Moät giaûi thuaät xaáp xæ laø moät giaûi thuaät traû veà lôøi giaûi gaàn toái öu.
° Giaû söû: chi phí cuûa lôøi giaûi 0. Goïi C laø chi phí cuûa lôøi giaûi toái öu.
Moät giaûi thuaät xaáp xæ cho moät baøi toaùn toái öu ñöôïc goïi laø coù tæ soá
xaáp xæ r(n) (approximation ratio, ratio bound) neáu vôùi moïi input coù
kích thöôùc n thì chi phí cuûa lôøi giaûi do giaûi thuaät xaáp xæ tìm ñöôïc seõ
thoaû
max(CC , C C) r(n) .
21.5.2004 Chöông 37 3
Approximation Algorithms
- Giaûi thuaät xaáp xæ
° Chi phí cuûa lôøi giaûi do giaûi thuaät xaáp xæ tìm ñöôïc thoûa, vôùi tæ soá xaáp
xæ r(n),
max(CC , C C) r(n)
– Baøi toaùn toái ña: 0 C C , vaäy
max(CC , C C) = C C r(n) .
Chi phí cuûa lôøi giaûi toái öu r(n) laàn chi phí cuûa lôøi giaûi gaàn
ñuùng.
– Baøi toaùn toái thieåu: 0 C C, vaäy
max(CC , C C) = CC r(n) .
Chi phí cuûa lôøi giaûi gaàn ñuùng r(n) laàn chi phí cuûa lôøi giaûi toái
öu.
° Moät giaûi thuaät xaáp xæ coù tæ soá xaáp xæ r(n) ñöôïc goïi laø moät giaûi thuaät
r(n)-xaáp xæ.
21.5.2004 Chöông 37 4
Approximation Algorithms
- Baøi toaùn che phuû ñænh
Nhaéc laïi
° Moät che phuû ñænh (vertex cover) cuûa moät ñoà thò voâ höôùng G = (V, E)
laø moät taäp con V’ V sao cho neáu (u, v) E thì u V’ hay v V’
(hoaëc caû hai V’).
Kích thöôùc cuûa moät che phuû ñænh laø soá phaàn töû cuûa noù.
° Baøi toaùn che phuû ñænh laø tìm moät che phuû ñænh coù kích thöôùc nhoû
nhaát trong moät ñoà thò voâ höôùng ñaõ cho.
Baøi toaùn naøy laø daïng baøi toaùn toái öu cuûa ngoân ngöõ NP-ñaày ñuû
VERTEX-COVER = {G, k : ñoà thò G coù moät che phuû ñænh coù kích
thöôùc k} .
21.5.2004 Chöông 37 5
Approximation Algorithms
- Moät giaûi thuaät xaáp xæ cho baøi toaùn che phuû ñænh
APPROX-VERTEX-COVER(G)
1 C
2 E’ E[G]
3 while E’
4 do xeùt (u, v) laø moät caïnh baát kyø cuûa E’
5 C C {u, v}
6 taùch khoûi E’ taát caû caùc caïnh lieân thuoäc taïi u hay v
7 return C
21.5.2004 Chöông 37 6
Approximation Algorithms
- Thöïc thi APPROX-VERTEX-COVER
b c d b c d
a e f g a e f g
b c d b c d
a e f g a e f g
b c d b c d
a e f g a e f g
21.5.2004 Chöông 37 7
Approximation Algorithms
- Phaân tích APPROX-VERTEX-COVER
Nhaän xeùt: Thôøi gian chaïy cuûa APPROX-VERTEX-COVER laø O(E).
Ñònh lyù 37.1
APPROX-VERTEX-COVER laø moät giaûi thuaät 2-xaáp xæ trong thôøi gian
ña thöùc.
21.5.2004 Chöông 37 8
Approximation Algorithms
- Baøi toaùn ngöôøi baùn haøng rong vôùi baát ñaúng thöùc tam giaùc
° Cho moät ñoà thò ñaày ñuû voâ höôùng G = (V, E) cuøng vôùi moät haøm chi
phí c : E Z+. Tìm moät chu trình hamilton (moät tour) cuûa G vôùi phí
toån nhoû nhaát.
° Ñieàu kieän: Haøm chi phí c: E Z+ thoûa maõn baát ñaúng thöùc tam giaùc
c(u, w) c(u, v) + c(v, w), u, v, w V .
APPROX-TSP-TOUR(G, c)
1 choïn moät ñænh r V[G] laøm moät ñænh “goác”
2 nuoâi lôùn moät caây khung nhoû nhaát T cho G töø
goác r duøng giaûi thuaät MST-PRIM(G, c, r)
3 goïi L laø danh saùch caùc ñænh ñöôïc thaêm vieáng
bôûi pheùp duyeät caây theo kieåu tieàn thöù töï
4 return chu trình hamilton H vieáng caùc ñænh
theo thöù töï L
21.5.2004 Chöông 37 9
Approximation Algorithms
- Thöïc thi APPROX-TSP-TOUR leân moät ví duï
a d a d
e e
b f g b f g
c c
h h
(a) (b)
Caây khung nhoû nhaát T tính bôûi MST-
PRIM, ñænh a laø ñænh goác.
21.5.2004 Chöông 37 10
Approximation Algorithms
- Thöïc thi APPROX-TSP-TOUR leân moät ví duï (tieáp)
a d a d
e e
b f g b f g
c c
h h
(c) (d)
Duyeät caây T baét ñaàu töø a. Thöù töï caùc ñænh Tua H coù ñöôïc töø keát quaû duyeät
khi duyeät kieåu hoaøn toaøn laø: a, b, c, b, h, b, caây theo kieåu tieàn thöù töï maø
a, d, e, f, e, g, e, d, a. Thöù töï caùc ñænh khi APPROX-TSP-TOUR tìm ñöôïc. Chi
duyeät kieåu tieàn thöù töï laø: a, b, c, h, d, e, f, g. phí cuûa tua H laø khoaûng chöøng
19,074.
21.5.2004 Chöông 37 11
Approximation Algorithms
- Thöïc thi APPROX-TSP-TOUR leân moät ví duï (tieáp)
a d
e
b f g
c
h
(e)
Tua toái öu H , coù chi phí laø 14,715.
21.5.2004 Chöông 37 12
Approximation Algorithms
- Baøi toaùn ngöôøi baùn haøng rong vôùi baát ñaúng thöùc tam giaùc
Ñònh lyù 37.2
APPROX-TSP-TOUR laø moät giaûi thuaät 2-xaáp xæ thôøi gian ña thöùc cho
baøi toaùn ngöôøi baùn haøng rong vôùi baát ñaúng thöùc tam giaùc.
Chöùng minh
Cho A E, ñònh nghóa c( A) = c(u, v)
(u , v )A
° Goïi H laø moät tua toái öu, goïi H laø tua maø APPROX-TSP-TOUR tìm
ñöôïc
° Caàn chöùng minh: c(H) 2c(H) .
° (*) Ta coù c(T) c(H e) c(H) vì neáu xoaù ñi baát cöù caïnh e naøo
cuûa H thì ñöôïc moät caây khung, maø T laïi laø caây khung nhoû nhaát.
21.5.2004 Chöông 37 13
Approximation Algorithms
- Baøi toaùn ngöôøi baùn haøng rong vôùi baát ñaúng thöùc tam giaùc
Chöùng minh (tieáp)
° c(W) = 2c(T), vôùi W laø keát quaû moät duyeät hoaøn toaøn caây T töø ñænh r,
vì moãi caïnh cuûa T ñöôïc ñi qua hai laàn.
° c(W) 2c(H), töø treân vaø vì (*).
° Nhöng W khoâng phaûi laø tua vì moãi ñænh ñöôïc thaêm hai laàn, do ñoù
“traùnh thaêm moïi ñænh laàn thöù hai” (= duyeät caây theo kieåu tieàn thöù
töï) ñeå coù ñöôïc tua H, chi phí khoâng taêng vì baát ñaúng thöùc tam giaùc,
do ñoù
c(H) c(W) 2c(H) .
21.5.2004 Chöông 37 14
Approximation Algorithms
- Baøi toaùn ngöôøi baùn haøng rong toång quaùt
Ñònh lyù 37.3
Neáu P NP vaø r 1, thì khoâng toàn taïi giaûi thuaät xaáp xæ thôøi gian ña
thöùc vôùi tæ soá xaáp xæ r cho baøi toaùn ngöôøi baùn haøng rong toång quaùt.
Chöùng minh
Chöùng minh baèng phaûn chöùng.
° Giaû söû coù moät soá nguyeân r 1 vaø moät giaûi thuaät r-xaáp xæ thôøi gian
ña thöùc A cho baøi toaùn ngöôøi baùn haøng rong toång quaùt.
Höôùng chöùng minh: Seõ duøng A ñeå giaûi baøi toaùn chu trình Hamilton
HAM-CYCLE trong thôøi gian ña thöùc. Vì HAM-CYCLE laø NP-ñaày
ñuû vaø theo giaû thieát P NP neân A khoâng chaïy trong thôøi gian ña
thöùc, maâu thuaån!
21.5.2004 Chöông 37 15
Approximation Algorithms
- Baøi toaùn ngöôøi baùn haøng rong toång quaùt
Chöùng minh (tieáp)
° Goïi G = (V, E) laø moät thöïc theå (instance) cuûa baøi toaùn chu trình
hamilton.
Töø G ñònh nghóa ñoà thò G’ = (V, E’) laø ñoà thò ñaày ñuû treân V, vôùi haøm
chi phí
c(u, v) = 1 neáu (u, v) E
= r|V| + 1 trong caùc tröôøng hôïp khaùc.
Caùc bieåu dieån cuûa G’ vaø c coù theå tính ñöôïc töø moät bieåu dieãn cuûa G
trong thôøi gian ña thöùc theo |V| vaø |E| .
21.5.2004 Chöông 37 16
Approximation Algorithms
- Baøi toaùn ngöôøi baùn haøng rong toång quaùt
Chöùng minh (tieáp)
° Goïi H laø tua toái öu cuûa G’, goïi H laø tua maø A tìm ñöôïc, ta coù
c(H ) rc(H). Phaân bieät hai tröôøng hôïp:
– Tröôøng hôïp c(H ) r|V|
r|V| c(H ) rc(H) |V| c(H)
Vaäy H phaûi chöùa ít nhaát moät caïnh E. Suy ra G khoâng coù chu
trình hamilton.
– Tröôøng hôïp c(H ) r|V|
c(H ) r|V| + 1 = chi phí cuûa moät caïnh baát kyø E. Do ñoù H chæ
chöùa caïnh cuûa G, töø ñoù suy ra H laø moät chu trình hamilton cuûa
G.
° Vaäy ta coù theå duøng giaûi thuaät A ñeå giaûi baøi toaùn chu trình hamilton
trong thôøi gian ña thöùc. Maâu thuaãn vôùi giaû thieát P NP!
21.5.2004 Chöông 37 17
Approximation Algorithms
- Baøi toaùn che phuû taäp
° Moät thöïc theå (X, F ) cuûa baøi toaùn che phuû taäp goàm moät taäp höõu haïn
X vaø moät hoï F caùc taäp con cuûa X sao cho
X = S.
S F
Moät taäp con C F ñöôïc goïi laø che phuû X neáu X= S.
S C
° Baøi toaùn che phuû taäp laø tìm moät taäp con C F , vôùi | C | laø nhoû nhaát,
sao cho C che phuû X.
21.5.2004 Chöông 37 18
Approximation Algorithms
- Daïng quyeát ñònh cuûa baøi toaùn che phuû taäp
° Daïng baøi toaùn quyeát ñònh cho baøi toaùn che phuû taäp laø tìm moät che
phuû sao cho kích thöôùc cuûa noù k, vôùi k laø moät tham soá cuûa moät
thöïc theå cuûa baøi toaùn quyeát ñònh.
° Baøi toaùn quyeát ñònh cho baøi toaùn che phuû taäp laø NP-ñaày ñuû.
21.5.2004 Chöông 37 19
Approximation Algorithms
- Moät giaûi thuaät xaáp xæ cho baøi toaùn che phuû taäp
° Moät giaûi thuaät xaáp xæ cho baøi toaùn che phuû taäp
– duøng phöông phaùp greedy.
GREEDY-SET-COVER(X, F )
1 UX
2 C
3 while U
4 do choïn moät S F sao cho | S U | laø lôùn nhaát
5 UUS
6 C C {S}
7 return C
21.5.2004 Chöông 37 20
Approximation Algorithms
nguon tai.lieu . vn