Giải thuật xấp xỉ trong Giải thuật nâng cao: Bài giảng TS. Ngô Quốc Việt

GIẢI THUẬT XẤP XỈ

TS. NGÔ QUỐC VIỆT 2015

Nội dung 1. Nhắc lại NP và các vấn đề liên quan 2. Giới thiệu giải thuật xấp xỉ 3. Minh họa giải thuật xấp xỉ với bài toán phủ đỉnh,

TSP. 4. Tóm tắt

Giải thuật nâng cao-Giải thuật xấp xỉ

2

Bài toán NP

• Giải thuật hiệu quả: xác định lời giải tối ưu trong thời gian đa thức • Tuy nhiên, hầu hết các bài toán tối ưu là NP khó. Nghĩa là không tồn tại giải thuật hiệu quả để giải. • NP là một trong những complexity class cơ bản. • NP: nondeterministic polynomial time.

Giải thuật nâng cao-Giải thuật xấp xỉ

3

Bài toán NP

• P: thuật giải thời gian đa thức. Lớp bài toán P có tính chất bao đóng chính xác (tính cộng, tính nhân). • NP: tập các bài toán quyết định (trả lời YES hoặc NO) theo đó một số instances cụ thể của bài toán đang xét được giải và kiểm chứng (verifier) trong thời gian đa thức.

• NP = Problems with Efficient Algorithms

for Verifying Proofs/Certificates/Witnesses

• Định nghĩa: NP là lớp các vấn đề có efficient verifiers, i.e. có giải thuật đa thức để kiểm chứng lời giải đã cho là đúng

Giải thuật nâng cao-Giải thuật xấp xỉ

4

Bài toán NP

• Phần lớn các bài toán thực tế là NP. Có thể efficiently verify nếu given short proof là valid, nhưng không tìm được efficient algorithm để giải.

• • Lớp NP là extremely interesting. • Hầu hết các vấn đề trong CS, math, biology, physics, chemistry, economics, management, sociology, business, v.v, đều thuộc lớp NP.

• Xem

thêm compendium of NP optimization

problems.

Giải thuật nâng cao-Giải thuật xấp xỉ

5

Verifier V của bài toán NP-ví dụ

• Xét bài toán tìm subset có tổng bằng zero (hay hằng

số bất kỳ).

• Nhận xét: số lượng các subset của tập hợp là lũy

thừa (bao nhiêu?)

• Tuy nhiên: cho subset cụ thể  dễ dàng kiểm chứng (verify) tổng các phần tử của nó là zero. Giải thuật kiểm chứng tổng zero của một subset được gọi là verifier.

Giải thuật nâng cao-Giải thuật xấp xỉ

6

Cận dưới của NP problem • Xem:

https://www.youtube.com/watch?v=K2-

Y4a3BtSE

• Reductions: giải một yêu cầu dựa trên các hàm hay problem khác như Subroutine/Oracle/Black Box. Không quan tâm đến độ phức tạp subroutine.

𝑃 𝑂. (Subscript T thể hiện ”Turing”)

Giải thuật nâng cao-Giải thuật xấp xỉ

7

• Giải thuật reduction A có sử dụng hàm O được ký hiệu: 𝐴𝑂 • Vấn đề Q là black-box reducible thành O và viết 𝑄 ≤𝑇 𝑂 iff tồn tại giải thuật A sao cho mọi input x, thì 𝑄 𝑥 = 𝐴𝑂(𝑥) • Nếu A chạy trong thời gian đa thức thì được gọi là polynomial-time black-box reduction, ký hiệu 𝑄 ≤𝑇

Cận dưới của NP problem

• Vấn đề Q là many-one reducible to problem O và viết 𝑄 ≤𝑚 𝑂 iff có giải thuật A sao cho mọi input x, thì 𝑄 𝑥 = 𝑂 𝐴 𝑥

𝑃 𝑂

• Nếu reduction algorithm A là polynomial time thì được gọi là polynomial-time many-one reduction, ký hiệu 𝑄 ≤𝑚

• Nếu có polynomial-time many-one reduction từ vấn

đề A thành NP problem B, thì A thuộc lớp NP.

Giải thuật nâng cao-Giải thuật xấp xỉ

8

NP-complete

𝑝 𝐴

• NP-complete là tập các vấn đề vừa NP, vừa NP-khó. • A là NP-complete iff • A là bài toán NP, và • Mọi bài toán B thuộc lớp NP, thì B là polynomial- time many-one reducible to A 𝐵 ≤𝑚

• Nếu problem là NP-complete, thì không tồn tại polynomial-time algorithm để tìm nghiệm tối ưu • Thường sử dụng giải thuật xấp xỉ, tham lam, heuristic, … để giải các bài toán NP.

Giải thuật nâng cao-Giải thuật xấp xỉ

9

NP & liên quan

Giải thuật nâng cao-Giải thuật xấp xỉ

10

NP-complete: ví dụ

http://www.cs.uky.edu/~lewis/cs- heuristic/text/class/more-np.html

https://en.wikipedia.org/wiki/List_of_NP- complete_problems Yêu cầu: Anh/Chị đọc và trình bày 2 bài viết trên

Giải thuật nâng cao-Giải thuật xấp xỉ

11

Giới thiệu giải thuật xấp xỉ

• Giải thuật xấp xỉ xác định lời giải xấp xỉ của các bài

toán tối ưu

• Thường dùng cho các vấn đề NP-khó • Khác với giải thuật heuristic (chỉ cần lời giải đủ tốt,

và đủ nhanh)

• Giải thuật xấp xỉ cần xác định rõ chất lượng xấp xỉ,

độ phức tạp.

• Ví dụ: giải thuật xấp xỉ cho bài toán phủ đỉnh.

Giải thuật nâng cao-Giải thuật xấp xỉ

12

Định nghĩa giải thuật xấp xỉ

• Giải thuật xấp xỉ  cho bài toán tối ưu là giải thuật hiệu quả (thời gian đa thức) cho mọi instance của vấn đề sao cho lời giải nằm trong ngưỡng  so với lời giải tối ưu thực sự.

•  : là tỉ lệ xấp xỉ (approximation ratio), hay thừa số

xấp xỉ (approximation factor).

• Định nghĩa: approximation ratio 𝝆 𝒏

là C*, chi phí của

• 𝝆 𝒏 ≥ 𝑚𝑎𝑥(

)

𝐶 𝐶∗ ,

• Chi phí của optimal solution approximation algorithm là C, thì 𝐶∗ 𝐶 • Gọi là: (n)-approximation algorithm.

Giải thuật nâng cao-Giải thuật xấp xỉ

13

Định nghĩa giải thuật xấp xỉ • Vấn đề Maximization thì 𝐶∗/𝜌(𝑛) ≤ 𝐶 ≤ 𝐶∗ • Vấn đề Minimization thì 𝐶∗ ≤ 𝐶 ≤ 𝜌(𝑛). 𝐶∗ • ρ(n) không nhỏ hơn 1. • 1-approximation algorithm là optimal solution

• Mục tiêu là tìm polynomial-time approximation algorithm với small constant approximation ratios

Giải thuật nâng cao-Giải thuật xấp xỉ

14

Approximation scheme

• Approximation scheme là approximation algorithm thêm tham số Є>0, sao cho với Є>0 xác định thì scheme là (1+Є)-approximation algorithm.

• Polynomial-time approximation scheme: runs in

time polynomial in the size of input.

• Khi Є giảm, thì thời gian thực hiện có thể tăng nhanh, ví dụ 𝑂 𝑛2

𝜖

Giải thuật nâng cao-Giải thuật xấp xỉ

15

Phủ đỉnh

• 𝐺 = (𝑉, 𝐸) là đồ thị, V={tập đỉnh}, E={tập cạnh} • 𝑆 ⊆ 𝑉 là một phủ, nếu ∀ (𝑢, 𝑣) ∈ 𝐸, thì 𝑢 ∈ 𝑆, hoặc

𝑣 ∈ 𝑆 hoặc 𝑢, 𝑣 ∈ 𝑆.

• Ví dụ:

Giải thuật nâng cao-Giải thuật xấp xỉ

Phủ đỉnh S

16

Một số ứng dụng của phủ đỉnh

• Bioinformatics

• Cơ sở cho novo genome assembly sử dụng phương pháp overlap-consensus (liên ứng). CABOG, Celera, xây dựng overlap graph của nhiều whole-genome shotgun reads, với each vertex ứng với read và cạnh biểu diễn mutual overlap giữa hai reads

• SNP Assembly Problem

• Computer network securities

• Mô phỏng sự lan truyền của worm máy tính nhằm tìm giải

pháp bảo vệ mạng máy tính lớn.

http://www.dharwadker.org/pirzada/applications

Giải thuật nâng cao-Giải thuật xấp xỉ

17

Phủ đỉnh

• OPTIMIZATION VERSION:

• INPUT: graph G • OUTPUT: vertex cover S of minimum-size (số đỉnh ít

nhất)

• DECISION VERSION:

• INSTANCE: graph G, integer k • QUESTION: does G have vertex cover of size  k

Giải thuật nâng cao-Giải thuật xấp xỉ

18

Phủ đỉnh

• Dạng bài toán NP-Complete • Sử dụng dạng giải thuật tham lam, hoặc xấp xỉ để

giải quyết

• Yêu cầu: Sử dụng chiến lược tham lam để giải bài phủ đỉnh. Trình bày thuật giải, cho biết độ phức tạp, và cài đặt chương trình minh họa.

Giải thuật nâng cao-Giải thuật xấp xỉ

19

Phủ đỉnh-xấp xỉ Giải thuật 1 1. Chọn cạnh A bất kỳ, bỏ tất cả các cạnh có nối đến hai đỉnh

của A ( kể cả cạnh A)

2. Chọn cạnh khác & lặp lại bước 1 đến khi mọi cạnh bị loại

bỏ.

vertex-cover tìm được theo giải thuật 1, thường gấp đôi phủ đỉnh tối ưu

Giải thuật nâng cao-Giải thuật xấp xỉ

20

Phủ đỉnh-xấp xỉ-giải thuật 1

Giải thuật nâng cao-Giải thuật xấp xỉ

Optimal Size=3 Near Optimal size=6

21

Phủ đỉnh-xấp xỉ-giải thuật 1

1 2 3

Not cover

1 2 3

Giải thuật nâng cao-Giải thuật xấp xỉ

4 5 6 7

22

Phủ đỉnh-xấp xỉ-giải thuật 1

1 2 3

Cover Size=4

4 5 6 7

1 2 3

Cover Size=7

Giải thuật nâng cao-Giải thuật xấp xỉ

4 5 6 7

23

Phủ đỉnh-xấp xỉ-giải thuật 1

Cover Size=5

4 5 6 7

1 2 3

Cover Size=3

Giải thuật nâng cao-Giải thuật xấp xỉ

4 5 6 7

24

Phủ đỉnh-xấp xỉ-giải thuật 1

APPROX-VERTEX-COVER là 2-approximate algorithm • Gọi c là phủ đỉnh xấp xỉ, và c* là phủ đỉnh tối ưu, A là

tập cạnh của lệnh 4. Cần chứng minh

𝑐 𝑐∗ ≤ 2.

• Lệnh 5 thêm cả hai đỉnh, trong khi chỉ cần thêm một

hoặc hai đỉnh trên

• Không có hai cạnh trong A, phủ cùng một đỉnh trong c* (vì đã bị xóa-lệnh 6)  𝑐∗ ≥ 𝐴

• Vì vậy:

𝑐 𝑐∗ ≤ 2.

Giải thuật nâng cao-Giải thuật xấp xỉ

25

Phủ đỉnh-xấp xỉ-giải thuật 1

2 3 1 𝛼 = 𝑀𝑎𝑥(6/3, 3/6) = 2

4 5 6 7

1 2 3

𝛼 = 𝑀𝑎𝑥(4/3, 3/4) = 1.33

Giải thuật nâng cao-Giải thuật xấp xỉ

4 5 6 7

26

Phủ đỉnh-xấp xỉ

(ln n)-approximation

Giải thuật 2 1. Chọn đỉnh v có bậc lớn nhất, cho v vào S. 2. Xóa mọi cạnh có nối với v. 3. Tiếp tục bước 1, 2 đến khi không còn cạnh nào Giải thuật 3 1. Tìm matching M tối đại trong G. 2. Với mỗi cạnh 𝑢, 𝑣 ∈ 𝑀, thêm hai đỉnh u, v vào S.

Giải thuật nâng cao-Giải thuật xấp xỉ

27

Phủ tập hợp-ví dụ • Một khu quy hoạch (có nhiều khu phố) cần xác định các

vị trí xây trường với hai ràng buộc • Trường phải trong khu phố (town) • Không học sinh/phụ huynh nào phải đi qua xa (vd: 10km) từ

nhà đến trường

Các khu phố

• Câu hỏi: cần xây tối thiểu bao nhiêu trường? • Yêu cầu trên có thể giải thông qua khái niệm phủ tập

hợp.

Giải thuật nâng cao-Lý thuyết số

Khu phố trong phạm vi 10km

28

Phủ tập hợp-định nghĩa

• Cho tập phổ biến 𝑈 = 𝑢1, 𝑢2, … , 𝑢𝑛 • Gọi 𝑆1, 𝑆2, … , 𝑆𝑘 ⊆ 𝑈 là các tập con có các trọng số tương ứng 𝑐1, 𝑐2, … , 𝑐𝑛

và 𝑆𝑖

𝑖 = 𝑈.

• Mục tiêu: cần tìm 𝐼 = 1,2, … , 𝑚 sao cho cực tiểu 𝑐𝑖 𝑖 • Hỏi: U, Si, ci trong bài toán xây các trường?

• 𝑈 ={các town trong khu quy hoạch} • Với mỗi khu phố x, Sx là tập các town trong phạm vi 10km.

Trường tại x sẽ phủ các town này

• cx=1, x ?

Giải thuật nâng cao-Lý thuyết số

29

Phủ tập hợp-giải thuật greedy • Chọn Si chứa nhiều town nhất chưa được phủ • Lặp lại cho đến khi các Si được chọn phủ U.

• Ví dụ xây trường

• Chọn Sa, Sa chứa a, b, d, e, k, i, h. • Chọn Sf hoặc Sg, vì chứa f, g. • Chọn Sc và Sj chứa chính nó. • 𝑐𝑖

𝑖 = 4.

• Nhận xét: có thể chọn giải pháp tốt hơn? • Xây trường tại b, e, và i là giải pháp tốt hơn

Giải thuật nâng cao-Lý thuyết số

30

Phủ tập hợp-giải thuật greedy

1. 𝐶 = *+ 2. While 𝐶 ≠ 𝑈

Tìm tập S có cost nhỏ nhất

Đặt 𝛼 =

𝑐(𝑆) 𝑆−𝐶

Với mỗi 𝑒 ∈ 𝑆\C, đặt 𝑝𝑟𝑖𝑐𝑒(𝑒) = 𝛼 𝐶 = 𝐶 ∪ 𝑆

3. Ouput S

Giải thuật nâng cao-Lý thuyết số

31

SC là bài toán NP-complete

•

Định lý: Set Cover (SC) là NP-complete Chứng minh:

INSTANCE: Cho universe U n phần tử, tập các subset của U, S = {S1, …, Sm}, và số nguyên dương b

QUESTION: Tồn tại tập 𝐶 ⊆ 1,2, … , 𝑚 , |C| ≤ b, sao cho

= 𝑈

𝑆𝑖 𝑖∈𝐶

Subcollection 𝑆𝑖 | 𝑖 ∈ 𝐶 thỏa điều kiện trên là set cover của U

Giải thuật nâng cao-Lý thuyết số

32

SC là bài toán NP-complete (tt) 1. Cần chứng minh SC thuộc NP. Dễ dàng kiểm chứng điều kiện YES của instance trên. Nghĩa là, cho subcollection C, nếu |𝐶| ≤ 𝑏 và hội của các tập trong C chứa mọi phần tử của U theo thời gian đa thức.

2. Để chứng minh định lý, cần phải chứng minh

Vertex Cover (VC) ≤p Set Cover (SC)

Cho instance C của VC (undirected graph G=(V,E) và số nguyên dương j), chúng ta cần xây dựng C’ của SC trong thời gian đa thức sao cho C là satisfiable iff C’ là satisfiable.

Giải thuật nâng cao-Lý thuyết số

33

SC là bài toán NP-complete (tt)

• Construction: Đặt U = E. Định nghĩa n phần tử của U và tập S như sau:

• Đánh nhãn mọi đỉnh trong V từ 1 đến n. Đặt Si là tập các cạnh nối với đỉnh i. Sau đó, đặt b = j. Cách xây dựng này là thời gian đa thức ứng với kích thước của VC instance

• Chú ý: mỗi cạnh ứng với mỗi phần tử trong U và mỗi đỉnh ứng với một set trong S.

Giải thuật nâng cao-Lý thuyết số

34

Phủ đỉnh có trọng số

• Tìm tập các đỉnh của graph sao cho mỗi cạnh chứa

ít nhất một đỉnh trong tập.

• Mỗi đỉnh có trọng số, cần tìm phủ đỉnh total weight

nhỏ nhất.

• Các phủ đỉnh: *1,3,4+; *1,7,5+

Giải thuật nâng cao-Giải thuật xấp xỉ

35

VERTEX-COVER p SET-COVER

•

Vertex Cover là trường hợp đặc biệt của Set Cover Chuyển vertex cover sang set cover:

• 1. T = the set of edges E 2. Các subsets ứng với từng vertex, mỗi subset chứa tập các cạnh nối với corresponding vertex

Giải thuật nâng cao-Giải thuật xấp xỉ

36

•

VERTEX-COVER p SET-COVER T = { (1, 3), (3,7), (1, 7), (4, 5), (4, 6) } Subsets:

• 1. S1 = { (1, 3), (1, 7) } w = 1 2. S3 = { (1, 3), (3, 7) } w = 3 3. S7 = { (1, 7), (3, 7) } w = 7 4. S4 = { (4, 5), (4, 6) } w = 4 5. S6 = { (4, 6) } w = 6 6. S5 = { (4, 5) } w = 5

Giải thuật nâng cao-Giải thuật xấp xỉ

37

VERTEX-COVER p SET-COVER

one element for every edge

VC VC

one set for every vertex, containing the edges it covers

Giải thuật nâng cao-Lý thuyết số

38

SC là bài toán NP-complete (tt) • Cần chứng minh C là satisfiable iff C’ là satisfiable. • Nghĩa là, cần chứng minh nếu original instance của VC là YES instance iff constructed instance of SC là YES instance.

• (→) • Giả sử G có phủ đỉnh C kích thước tối đa là j. Theo cách xây dựng trên, C ứng với collection C’ của các subsets của U. Vì b = j, |C’| ≤ b. C’ phủ mọi elements trong U vì C “phủ ” mọi cạnh trong G. • Để thấy điều này, xét bất kỳ phần tử nào của U. Sao cho một phần tử là cạnh trong G. Vì C là set cover, có ít nhất một endpoint của cạnh này thuộc C.

Giải thuật nâng cao-Lý thuyết số

39

SC là bài toán NP-complete (tt)

• (←) • Giả sử có set cover C’ kích thước tối đa b trong constructed instance. Vì mỗi tập trong in C’ được kết hợp với đỉnh trong G, đặt C là tập các đỉnh này. Thì |C| = |C’| ≤ b = j. C là vertex cover của G vì C’ là set cover.

• Để thấy điều này, xét cạnh bất kỳ e. Vì e thuộc U, nên C’ phải chứa ít nhất một tập set có chứa e. Theo cách xây dựng trên, chỉ một tập hợp chứa e ứng với các là các endpoint của e. Vậy C phải chứa ít nhất một endpoint của e.

Giải thuật nâng cao-Lý thuyết số

40

Giải thuật Set Cover

Algorithm 1: (trường hợp uniform cost) 1. C = empty 2. while U is not empty

pick a set Si such that Si covers the most elements in U remove the new covered elements from U C = C union Si

5. 6. return C

Giải thuật nâng cao-Lý thuyết số

41

Giải thuật Set Cover • Trường hợp non-uniform cost • Phươn pháp ương tự. Tại mỗi bước lặp, tah vì chọn tập Si sao cho Si phủ nhiều nhất các phần tử chưa được phủ, thì chọn tập Si có cost-effectiveness α nhỏ nhất, với α được định nghĩa :

𝛼 =

𝑐 𝑆𝑖 𝐴𝑖 ∩ 𝑈

• Câu hỏi: tại sao chọn smallest α? Tạy sao định nghĩa α

như trên

Giải thuật nâng cao-Lý thuyết số

42

Giải thuật Set Cover

Algorithm 2: (trường hợp non-uniform cost) 1. C = empty 2. while U is not empty

pick a set Si such that Si has the smallest α for each new covered elements e in U set price(e) = α remove the new covered elements from U C = C union Si

7. 8. return C

Giải thuật nâng cao-Lý thuyết số

43

Giải thuật xấp xỉ cho Max-Cut

• Cho đồ thị 𝐺 = 𝑉, 𝐸 . Yêu cầu tách thành hai tập đỉnh S, T sao cho số cạnh bị cắt (cut edge: một đỉnh trong S, đỉnh kia trong T) là nhiều nhất

Giải thuật 2-approximation

1. S ← Ø , T ← V 2. Nếu chuyển một từ S sang T, hoặc ngược lại mà làm tăng số cut edges, thì thực hiện chuyển nút. Repeat 2.

3. Output số cut edges.

Giải thuật nâng cao-Giải thuật xấp xỉ

44

1 1 2

2 1 20

4 3

Bài toán TSP • Cho đồ thị 𝐺 = 𝑉, 𝐸 có trọng số, vô hướng. Từ đỉnh bất kỳ đi đến mọi đỉnh khác và quay trở lại đỉnh xuất phát với chi phí thấp nhất

• TSP thuộc lớp NP-complete • Không tồn tại polynomial-time approximation

algorithm với constant approximation ratio.

Giải thuật nâng cao-Giải thuật xấp xỉ

45

Bài toán TSP

• Có thể giải TSP theo 2 bước • Tìm MST cho đồ thị đang xét • Bắt đầu từ bất kỳ node và di chuyển trên các cung của

MST, và thêm cung tắt để đi khi cần.

red bold arcs form a tour

Giải thuật nâng cao-Giải thuật xấp xỉ

start node

46

Bài toán TSP

• Thông thường, có thể giả thiết triangle inequality đúng cho cost function c: E  R xác định trên các cung của đồ thị G=(V,E) :

cuw  cuv + cvw for any u, v, w V

then the algorithm for TSP

is a 2-approximation algorithm.

• Định lý: If the cost function satisfies the triangle inequality,

Giải thuật nâng cao-Giải thuật xấp xỉ

47

c23  c23

red bold arcs of tour

start node

Bài toán TSP  Với e là cung trên tour, thì (triangle inequality), c(e)  c(f1)+…+c(fk) Vd: c15  c13 + c35  Mỗi cung của tree (**) là shortcut nhiều nhất hai lần. Vd: cung tree 3-5 là shortcut bởi cung tour 1-5 và 5-6 .  Nhận xét

𝑐𝑜𝑠𝑡 𝑡𝑠𝑝 𝑡𝑜𝑢𝑟 = 𝑐(𝑒)

≤ 2. 𝑐 𝑒 𝑒∈𝑀𝑆𝑇

𝑒∈𝑇𝑜𝑢𝑟 = 2. 𝑐𝑜𝑠𝑡(𝑀𝑆𝑇)

Giải thuật nâng cao-Giải thuật xấp xỉ

48

Bài toán TSP

Use Prim’s algorithm to get a MST

a d

b f

• Trọng số cạnh là khoảng cách giữa hai đỉnh

Giải thuật nâng cao-Giải thuật xấp xỉ

49

Bài toán TSP

Use Prim’s algorithm to get a MST

Chọn “a”là root

a d

Preorder tree walk

b f

a b c h d e f g

• Trọng số cạnh là khoảng cách giữa hai đỉnh • Bất phương trình tam giác thỏa

Giải thuật nâng cao-Giải thuật xấp xỉ

50

Bài toán TSP

Use Prim’s algorithm to get a MST

Chọn “a”là root

a d

Preorder tree walk

b f

a b c h d e f g

• Tổng trọng số gấp đôi lời giải tối ưu

Giải thuật nâng cao-Giải thuật xấp xỉ

The route là…

51

Bài toán TSP

• Giải thuật APPROX-TSP-1 là polynomial-time 2-

approximation algorithm.

Pre-order

• APPROX-TSP-TOUR là O(V2) • C(MST) ≤ C(H) H: optimal soln Optimal C(W)=2C(MST) W: Preorder walk C(W)≤2C(H) C(H)≤C(W) C(H)≤2C(H)

H: approx soln & triangle inequality

Giải thuật nâng cao-Giải thuật xấp xỉ

Solution

52

Bài toán TSP

APPROX-TSP-2(G, c) 1. Select a vertex r Є V[G] to be root. 2. Compute a MST T for G from root

r using Prim Alg.

3. Find a minimal-weight matching M for vertices of odd degree in T. 4. Find an Euler cycle C in G’ = (V, T U

M).

O(1) O(n lg n) O(n3) O(n2) O(n)

5. L=list of vertices in preorder walk

of C.

6. return the Hamiltonian cycle H in

the order L.

Giải thuật nâng cao-Giải thuật xấp xỉ

53

Chu trình Hamilton • Cho đồ thị 𝐺 = 𝑉, 𝐸 , tìm chu trình sao cho đi qua

mỗi đỉnh đúng một lần

• HAM-CYCLE trở thành Spanning Tree khi bỏ một

cạnh bất kỳ

• cost(MST) ≤ cost(min-HAM-CYCLE)

Giải thuật nâng cao-Giải thuật xấp xỉ

54

Tóm tắt

• Các khái niệm P, NP, NP-complete • Giải thuật xấp xỉ với hệ số xấp xỉ • Minh họa với các bài toán phủ đỉnh, TSP, chu trình

Hamilton

Giải thuật nâng cao-Giải thuật xấp xỉ

Bài giảng Giải thuật nâng cao: Giải thuật xấp xỉ - TS. Ngô Quốc Việt

Chủ đề: