Kinh doanh - Marketing
Kinh tế quản lý
Biểu mẫu - Văn bản
Tài chính - Ngân hàng
Công nghệ thông tin
Tiếng anh ngoại ngữ
Kĩ thuật công nghệ
Khoa học tự nhiên
Khoa học xã hội
Văn hóa nghệ thuật
Sức khỏe - Y tế
Văn bản luật
Nông Lâm Ngư
Kỹ năng mềm
Luận văn - Báo cáo
Giải trí - Thư giãn
Tài liệu phổ thông
Văn mẫu
Giới thiệu
Đăng ký
Đăng nhập
Tìm
Danh mục
Kinh doanh - Marketing
Kinh tế quản lý
Biểu mẫu - Văn bản
Tài chính - Ngân hàng
Công nghệ thông tin
Tiếng anh ngoại ngữ
Kĩ thuật công nghệ
Khoa học tự nhiên
Khoa học xã hội
Văn hóa nghệ thuật
Y tế sức khỏe
Văn bản luật
Nông lâm ngư
Kĩ năng mềm
Luận văn - Báo cáo
Giải trí - Thư giãn
Tài liệu phổ thông
Văn mẫu
Thông tin
Điều khoản sử dụng
Quy định bảo mật
Quy chế hoạt động
Chính sách bản quyền
Giới thiệu
Đăng ký
Đăng nhập
0
Trang chủ
Khoa Học Tự Nhiên
Toán học
Phân tích thiết kế giải thuật (Bài giảng tiếng Anh) - Chapter 8: Approximation Algorithms
Đang chuẩn bị liên kết để tải về tài liệu:
Phân tích thiết kế giải thuật (Bài giảng tiếng Anh) - Chapter 8: Approximation Algorithms
Nguyên Thảo
85
22
ppt
Đang chuẩn bị nút TẢI XUỐNG, xin hãy chờ
Tải xuống
Many problems of practical significance are NPcomplete but are too important to abandon merely because obtaining an optimal solution is intractable (khó). If a problem is NP-complete, we are unlikely to find a polynomial time algorithm for solving it exactly, but it may still be possible to find near-optimal solution in polynomial time. | Chapter 8 Approximation Algorithms Outline Why approximation algorithms? The vertex cover problem The set cover problem TSP Why Approximation Algorithms ? Many problems of practical significance are NP-complete but are too important to abandon merely because obtaining an optimal solution is intractable (khó). If a problem is NP-complete, we are unlikely to find a polynomial time algorithm for solving it exactly, but it may still be possible to find near-optimal solution in polynomial time. In practice, near-optimality is often good enough. An algorithm that returns near-optimal solutions is called an approximation algorithm. Performance bounds for approximation algorithms i is an optimization problem instance c(i) be the cost of solution produced by approximate algorithm and c*(i) be the cost of optimal solution. For minimization problem, we want c(i)/c*(i) to be as small as possible. For maximization problem, we want c*(i)/c(i) to be as small as possible. An approximation . | Chapter 8 Approximation Algorithms Outline Why approximation algorithms? The vertex cover problem The set cover problem TSP Why Approximation Algorithms ? Many problems of practical significance are NP-complete but are too important to abandon merely because obtaining an optimal solution is intractable (khó). If a problem is NP-complete, we are unlikely to find a polynomial time algorithm for solving it exactly, but it may still be possible to find near-optimal solution in polynomial time. In practice, near-optimality is often good enough. An algorithm that returns near-optimal solutions is called an approximation algorithm. Performance bounds for approximation algorithms i is an optimization problem instance c(i) be the cost of solution produced by approximate algorithm and c*(i) be the cost of optimal solution. For minimization problem, we want c(i)/c*(i) to be as small as possible. For maximization problem, we want c*(i)/c(i) to be as small as possible. An approximation algorithm for the given problem instance i, has a ratio bound of p(n) if for any input of size n, the cost c of the solution produced by the approximation algorithm is within a factor of p(n) of the cost c* of an optimal solution. That is max(c(i)/c*(i), c*(i)/c(i)) ≤ p(n) Note that p(n) is always greater than or equal to 1. If p(n) = 1 then the approximate algorithm is an optimal algorithm. The larger p(n), the worst algorithm Relative error We define the relative error of the approximate algorithm for any input size as |c(i) - c*(i)|/ c*(i) We say that an approximate algorithm has a relative error bound of ε(n) if |c(i)-c*(i)|/c*(i)≤ ε(n) 1. The Vertex-Cover Problem Vertex cover: given an undirected graph G=(V,E), then a subset V V such that if (u,v) E, then u V or v V (or both). Size of a vertex cover: the number of vertices in it. Vertex-cover problem: find a vertex-cover of minimal size. This problem is NP-hard, since the related decision problem is .
TÀI LIỆU LIÊN QUAN
Bài giảng: Phân tích thiết kế giải thuật (ĐH Cần Thơ)
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ỉ
Bài giảng Phân tích thiết kế giải thuật: Chương 1 - Trịnh Huy Hoàng
Bài giảng Phân tích thiết kế và giải thuật - Chương 2: Kỹ thuật thiết kế giải thuật
Bài giảng Phân tích thiết kế thuật toán: Chương 3 - Nguyễn Văn Linh
Bài giảng Phân tích thiết kế giải thuật - Chương 10: Single-Source Shortest Paths
Bài giảng Phân tích thiết kế giải thuật: Chương 4 - Trịnh Huy Hoàng
Bài giảng Phân tích thiết kế và giải thuật - Chương 1: Kỹ thuật phân tích giải thuật
Bài giảng Phân tích thiết kế giải thuật: Chương 2 - Trịnh Huy Hoàng
Bài giảng Phân tích thiết kế thuật toán: Chương 1 - Nguyễn Văn Linh
crossorigin="anonymous">
Đã phát hiện trình chặn quảng cáo AdBlock
Trang web này phụ thuộc vào doanh thu từ số lần hiển thị quảng cáo để tồn tại. Vui lòng tắt trình chặn quảng cáo của bạn hoặc tạm dừng tính năng chặn quảng cáo cho trang web này.