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

Chia sẻ: 4584125 4584125 | Ngày: | Loại File: PDF | Số trang:55

Thêm vào BST

Báo xấu

109
lượt xem 6
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Chương này đề cập đến giải thuật xấp xỉ. Những nội dung chính trong bài giảng gồm có: 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. Mời các bạn tham khảo.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Bài giảng Giải thuật nâng cao: Giải thuật xấp xỉ - 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. • 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 𝑄 ≤𝑃𝑇 𝑂. (Subscript T thể hiện ”Turing”) Giải thuật nâng cao-Giải thuật xấp xỉ 7
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 𝝆 𝒏 • Chi phí của optimal solution là C*, chi phí của 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 2 nhanh, ví dụ 𝑂 𝑛 𝜖 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ụ: Phủ đỉnh S Giải thuật nâng cao-Giải thuật xấp xỉ 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