Bài giảng Phân tích thiết kế giải thuật - Chương 13: Giải thuật xấp xỉ (Approximation Algorithms)

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

Approximation Algorithms

2

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(CC^, C^C)  r(n) .

21.5.2004

Chöông 37

Approximation Algorithms

3

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(CC^, C^C)  r(n)

– Baøi toaùn toái ña: 0  C  C^, vaäy

max(CC^, 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(CC^, C^C) = CC^ 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

Approximation Algorithms

4

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

Approximation Algorithms

5

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

5

6

do xeùt (u, v) laø moät caïnh baát kyø cuûa E’

C  C  {u, v}

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

Approximation Algorithms

6

Thöïc thi APPROX-VERTEX-COVER

c

b

d

c

e

b

a

d

e

c

a

b

f

g

f

g

c

b

d

e

c

e

c

a

b

f

g

a

b

f

d

e

a

f

g

a

f

g

21.5.2004

Chöông 37

Approximation Algorithms

7

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

Approximation Algorithms

8

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

Approximation Algorithms

9

Thöïc thi APPROX-TSP-TOUR leân moät ví duï

a

b

d

a

b

d

e

f

g

f

g

c

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

Approximation Algorithms

10

Thöïc thi APPROX-TSP-TOUR leân moät ví duï (tieáp)

a

d

a

d

e

b

f

g

b

f

g

c

h

(c)

(d)

Duyeät caây T baét ñaàu töø a. Thöù töï caùc ñænh

khi duyeät kieåu hoaøn toaøn laø: a, b, c, b, h, b,

a, d, e, f, e, g, e, d, a. Thöù töï caùc ñænh khi

duyeät kieåu tieàn thöù töï laø: a, b, c, h, d, e, f, g.

Tua H coù ñöôïc töø keát quaû duyeät

caây theo kieåu tieàn thöù töï maø

APPROX-TSP-TOUR tìm ñöôïc. Chi

phí cuûa tua H laø khoaûng chöøng

19,074.

21.5.2004

Chöông 37

Approximation Algorithms

11

Thöïc thi APPROX-TSP-TOUR leân moät ví duï (tieáp)

a

b

d

e

f

g

c

h

(e)

Tua toái öu H^, coù chi phí laø 14,715.

21.5.2004

Chöông 37

Approximation Algorithms

12

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

c(A) =

c(u,v)

Cho A  E, ñònh nghóa



(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

Approximation Algorithms

13

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

Approximation Algorithms

14

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

Approximation Algorithms

15

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

= r|V| + 1

neáu (u, v)  E

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

Approximation Algorithms

16

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 )  rc(H^). Phaân bieät hai tröôøng hôïp:

– Tröôøng hôïp c(H )  r|V|

r|V|  c(H )  rc(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

Approximation Algorithms

17

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

Approximation Algorithms

18

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

Approximation Algorithms

19

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 U  X

2 C  

3 while U  

4

5

6

do choïn moät S  F sao cho | S  U | laø lôùn nhaát

U  U − S

C  C  {S}

7 return C

21.5.2004

Chöông 37

Approximation Algorithms

20