intTypePromotion=1
zunia.vn Tuyển sinh 2024 dành cho Gen-Z zunia.vn zunia.vn
ADSENSE
 » 
 » 

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

Chia sẻ: Đinh Trường Gấu | Ngày: | Loại File: PPT | Số trang:21

Thêm vào BST
Báo xấu
124
lượt xem 7
download
 
  Download Vui lòng tải xuống để xem tài liệu đầy đủ

Nhằm giúp các bạn có thêm tài liệu phục vụ nhu cầu học tập và nghiên cứu về Công nghệ thông tin, mời các bạn cùng tham "Bài giảng Phân tích thiết kế giải thuật - Chương 37: Giải thuật xấp xỉ" dưới đây. Nội dung bài giảng cung cấp cho các bạn những kiến thức về cách tiếp cận một bài toán NP-đầy đủ, bài toán che phủ đỉnh, giải thuật xấp xỉ, ... Hy vọng đây là tài liệu tham khảo hữu ích cho các bạn.

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 Phân tích thiết kế giải thuật - Chương 37: Giải thuật xấp xỉ

  1. Giải Thuật Xấp Xỉ Chapter 37 Approximation Algorithms
  2. Tiếp cận một bài toán NP­đầy đủ ° Nếu một bài toán là NP­đầy đủ thì không chắc rằng ta sẽ tìm được  một giải thuật thời gian đa thức để giải nó một cách chính xác. ° Tiếp cận một bài toán NP­đầy đủ   1) Nếu các input có kích thước nhỏ thì một giải thuật chạy trong  thời gian số mũ vẫn có thể thoả mãn yêu cầu   2) Thay vì tìm các lời giải tối ưu, có thể tìm các lời giải gần tối ưu  trong thời gian đa thức. 21.5.2004 Chương 37 2 Approximation Algorithms
  3. Giải thuật xấp xỉ ° Một giải thuật xấp xỉ  là một giải thuật trả về lời giải gần tối ưu. ° Giả sử: chi phí của lời giải   0. Gọi C   là chi phí của lời giải tối ưu.   Một giải thuật xấp xỉ cho một bài toán tối ưu được gọi là có tỉ số  xấp xỉ  (n  (approximation ratio, ratio bound) nếu với mọi input có  kích thước n thì chi phí của lời giải do giải thuật xấp xỉ tìm được sẽ  thoả • max(C C  , C   C    r(n 21.5.2004 Chương 37 3 Approximation Algorithms
  4. Giải thuật xấp xỉ ° Chi phí của lời giải do giải thuật xấp xỉ tìm được thỏa, với tỉ số  xấp xỉ  (n ,  • max(C C  , C   C    r(n    – Bài toán tối đa: 0   C   C  , vậy   max(C C  , C   C  = C   C   r(n  .   Chi phí của lời giải tối ưu   r(n  lần chi phí của lời giải gần  đúng. – Bài toán tối thiểu: 0   C    C, vậy   max(C C  , C   C  = C C    r(n  .   Chi phí của lời giải gần đúng    (n  lần chi phí của lời giải tối  ưu. ° Một giải thuật xấp xỉ có tỉ số xấp xỉ  (n  được gọi là một giải  thuật  (n ­xấp xỉ. 21.5.2004 Chương 37 4 Approximation Algorithms
  5. Bài toán che phủ đỉnh   Nhắc lại ° Một che phủ đỉnh (vertex cover) của một đồ thị vô hướng G = (V, E)  là một tập con V’   V sao cho nếu (u, v)   E thì u   V’ hay v   V’  (hoặc cả hai   V’).   Kích thước của một che phủ đỉnh là số phần tử của nó. ° Bài toán che phủ đỉnh là tìm một che phủ đỉnh có kích thước nhỏ  nhất trong một đồ thị vô hướng đã cho.   Bài toán này là dạng bài toán tối ưu của ngôn ngữ NP­đầy đủ   VERTEX­COVER   { G, k  : đồ thị G có một che phủ đỉnh có kích  thước k} . 21.5.2004 Chương 37 5 Approximation Algorithms
  6. Một giải thuật xấp xỉ cho bài toán che phủ đỉnh APPROX­VERTEX­COVER(G) 1 C    2 E’   E[G] 3 while E’    4 do xét (u, v) là một cạnh bất kỳ của E’ 5      C   C   {u, v} 6      tách khỏi E’ tất cả các cạnh liên thuộc tại u hay v 7 return C 21.5.2004 Chương 37 6 Approximation Algorithms
  7. 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
  8. Phân tích APPROX­VERTEX­COVER   Nhận xét: Thời gian chạy của APPROX­VERTEX­COVER là O(E).   Định lý 37.1   APPROX­VERTEX­COVER là một giải thuật 2­xấp xỉ trong thời gian  đa thức. 21.5.2004 Chương 37 8 Approximation Algorithms
  9. Bài toán người bán hàng rong với bất đẳng thức tam giác ° Cho một đồ thị đầy đủ vô hướng G = (V, E) cùng với một hàm chi  phí c : E   Z+. Tìm một chu trình hamilton (một tour) của G với phí  tổn nhỏ nhất. °  Điều kiện: Hàm chi phí c: E   Z+ thỏa mãn bất đẳng thức tam giác   c(u, w)   c(u, v) + c(v, w),  u, v, w   V . APPROX­TSP­TOUR(G, c) 1     chọn một đỉnh r   V G  làm một đỉnh “gốc” 2     nuôi lớn một cây khung nhỏ nhất T cho G từ  gốc r dùng giải thuật MST­PRIM(G, c, r) 3     gọi L là danh sách các đỉnh được thăm viếng  bởi phép duyệt cây theo kiểu tiền thứ tự 4     return chu trình hamilton H viếng các đỉnh  theo thứ tự L 21.5.2004 Chương 37 9 Approximation Algorithms
  10. Thực thi APPROX­TSP­TOUR lên một ví dụ a d a d e e b f g b f g c c h h (a) (b) Cây khung nhỏ nhất T tính bởi MST­ PRIM, đỉnh a là đỉnh gốc.  21.5.2004 Chương 37 10 Approximation Algorithms
  11. Thực thi APPROX­TSP­TOUR lên một ví dụ (tiếp) a d a d e e b f g b f g c c h h (c) (d) Duyệt cây T bắt đầu từ a. Thứ tự các đỉnh  Tua H có được từ kết quả duyệt  khi duyệt kiểu hoàn toàn là: a, b, c, b, h, b,  cây theo kiểu tiền thứ tự mà  a, d, e, f, e, g, e, d, a. Thứ tự các đỉnh khi  APPROX­TSP­TOUR tìm được. Chi  duyệt kiểu tiền thứ tự là: a, b, c, h, d, e, f,  phí của tua H là khoảng chừng  g. 19,074. 21.5.2004 Chương 37 11 Approximation Algorithms
  12. Thực thi APPROX­TSP­TOUR lên một ví dụ (tiếp) a d e b f g c h (e) Tua tối ưu H  , có chi phí là 14,715. 21.5.2004 Chương 37 12 Approximation Algorithms
  13. Bài toán người bán hàng rong với bất đẳng thức tam giác • Định lý 37.2 • APPROX­TSP­TOUR là một giải thuật 2­xấp xỉ thời gian đa thức cho  bài toán người bán hàng rong với bất đẳng thức tam giác. • Chứng minh    Cho A   E, định nghĩa c( A) c(u, v) (u , v ) A ° Gọi H  là một tua tối ưu, gọi H là tua mà APPROX­TSP­TOUR tìm  được ° Cần chứng minh: c H    2c H  . ° (*) Ta có c T    c H    e    c H  vì nếu xoá đi bất cứ cạnh e nào  của H  thì được một cây khung, mà T lại là cây khung nhỏ nhất. 21.5.2004 Chương 37 13 Approximation Algorithms
  14. Bài toán người bán hàng rong với bất đẳng thức tam giác   Chứng minh (tiếp) ° c W  = 2c T , với W là kết quả một duyệt hoàn toàn cây T từ đỉnh r,  vì mỗi cạnh của T được đi qua hai lần. ° c W    2c H , từ trên và vì (*). ° Nhưng W không phải là tua vì mỗi đỉnh được thăm hai lần, do đó  “tránh thăm mọi đỉnh lần thứ hai” (= duyệt cây theo kiểu tiền thứ  tự) để có được tua H, chi phí không tăng vì bất đẳng thức tam giác,  do đó • c H    c W    2c H 21.5.2004 Chương 37 14 Approximation Algorithms
  15. Bài toán người bán hàng rong tổng quát • Định lý 37.3 • Nếu P   NP và     1, thì không tồn tại giải thuật xấp xỉ thời gian  đa thức với tỉ số xấp xỉ   cho bài toán người bán hàng rong tổng  quát. • Chứng minh   Chứng minh bằng phản chứng. ° Giả sử có một số nguyên     1 và một giải thuật  ­xấp xỉ thời gian  đa thức A cho bài toán người bán hàng rong tổng quát.   Hướng chứng minh: Sẽ dùng A để giải bài toán chu trình Hamilton  HAM­CYCLE trong thời gian đa thức. Vì HAM­CYCLE là NP­đầy  đủ và theo giả thiết P   NP nên A không chạy trong thời gian đa  thức, mâu thuẩn! 21.5.2004 Chương 37 15 Approximation Algorithms
  16. Bài toán người bán hàng rong tổng quát • Chứng minh (tiếp) ° Gọi G = (V, E) là một thực thể (instance) của bài toán chu trình  hamilton.   Từ G định nghĩa đồ thị G’ = (V, E’) là đồ thị đầy đủ trên V, với hàm  chi phí  • c(u, v) = 1 nếu (u, v)   E •             =  |V  + 1          trong các trường hợp khác. • Các biểu diển của G’ và c có thể tính được từ một biểu diễn của G  trong thời gian đa thức theo  V  và  E  . 21.5.2004 Chương 37 16 Approximation Algorithms
  17. Bài toán người bán hàng rong tổng quát   Chứng minh (tiếp) ° Gọi H  là tua tối ưu của G’, gọi H là tua mà A tìm được, ta có • c(H )   r c(H ). Phân biệt hai trường hợp: – Trường hợp c(H )   r|V |V    c(H )   r c(H )    V    c(H )   Vậy H  phải chứa ít nhất một cạnh   E. Suy ra G không có chu  trình hamilton. – Trường hợp c(H )   r|V • c(H )    |V    1 = chi phí của một cạnh bất kỳ   E. Do đó H  chỉ chứa cạnh của G, từ đó suy ra H là một chu trình hamilton  của G. ° Vậy ta có thể dùng giải thuật A để giải bài toán chu trình hamilton  trong thời gian đa thức. Mâu thuẫn với giả thiết P   NP! 21.5.2004 Chương 37 17 Approximation Algorithms
  18. Bài toán che phủ tập ° Một thực thể (X, F ) của bài toán che phủ tập gồm một tập hữu hạn  X và một họ F các tập con của X sao cho X  S. S F   Một tập con C   F được gọi là che phủ X nếu X  S. S C ° Bài toán che phủ tập là tìm một tập con C   F , với   C   là nhỏ  nhất, sao cho C che phủ X. 21.5.2004 Chương 37 18 Approximation Algorithms
  19. Dạng quyết định của bài toán che phủ tập ° Dạng bài toán quyết định cho bài toán che phủ tập là tìm một che  phủ sao cho kích thước của nó   k, với k là một tham số của một  thực thể của bài toán quyết định. ° Bài toán quyết định cho bài toán che phủ tập là NP­đầy đủ. 21.5.2004 Chương 37 19 Approximation Algorithms
  20. Một giải thuật xấp xỉ cho bài toán che phủ tập ° Một giải thuật xấp xỉ cho bài toán che phủ tập – dùng phương pháp greedy. GREEDY­SET­COVER(X, F ) 1 U   X 2 C    3 while U    4 do chọn một S   F sao cho   S   U   là lớn nhất 5      U   U   S 6      C   C   {S} 7 return C 21.5.2004 Chương 37 20 Approximation Algorithms
ADSENSE

CÓ THỂ BẠN MUỐN DOWNLOAD

THÔNG TIN
TRỢ GIÚP
HỖ TRỢ KHÁCH HÀNG
Theo dõi chúng tôi

Chịu trách nhiệm nội dung:

Nguyễn Công Hà - Giám đốc Công ty TNHH TÀI LIỆU TRỰC TUYẾN VI NA

LIÊN HỆ

Địa chỉ: P402, 54A Nơ Trang Long, Phường 14, Q.Bình Thạnh, TP.HCM

Hotline: 093 303 0098

Email: support@tailieu.vn

Giấy phép Mạng Xã Hội số: 670/GP-BTTTT cấp ngày 30/11/2015 Copyright © 2022-2032 TaiLieu.VN. All rights reserved.

 

Đồng bộ tài khoản
2=>2