TAILIEUCHUNG - 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ỉ

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. | Giải Thuật Xấp Xỉ Chapter 37 Approximation Algorithms Chương 37 Approximation Algorithms 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. Chương 37 Approximation Algorithms 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ỉ r(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) . Chương 37 Approximation Algorithms 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ỉ r(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 r(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ỉ r(n) được gọi là một giải thuật r(n)-xấp xỉ. Chương 37 Approximation Algorithms 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ỹ thuật lập trình
• Phân tích thiết kế giải thuật
• Bài giảng Phân tích thiết kế giải thuật
• Giải thuật xấp xỉ
• Bài toán che phủ đỉnh
• Bài toán NP đầy đủ
• Phân tích thiết kế giải thuật chương 37
• Kỹ thuật thiết kế giải thuật
• Thiết kế giải thuật
• Bài giảng thiết kế giải thuật
• Kỹ thuật phân tích thiết kế giải thuật
• Phân tích thuật toán
• Phương pháp phân tích thuật toán
• Vai trò của phân tích thuật toán
• Quá trình phân tích thuật toán
• Phân tích thiết kế thuật toán
• Thiết kế thuật toán
• Bài giảng Phân tích thiết kế thuật toán
• Bài giảng Phân tích thiết kế
• Phân tích thiết kế dữ liệu
• Cắt tỉa Alpha Beta
• Tiêu chuẩn đánh giá giải thuật
• Phương pháp đánh giá giải thuật
• Phương pháp thiết kế thuật giải
• Thuật toán chính xác
• Thuật toán gần đúng
• Bước thiết kế một thuật giải
• Single Source Shortest Paths
• Phân tích thiết kế giải thuật chương 10
• Giải bài toán các đường đi ngắn nhất
• Biểu diễn các đường đi ngắn nhất
• Thuật toán sắp xếp
• Phân tích thuật toán sắp xếp
• Thuật toán tìm kiếm
• Phân tích thuật toán tìm kiếm
• Kỹ thuật phân tích thuật toán
• Đánh giá một giải thuật
• Cây khung nhỏ nhất
• Giải thuật tổng quát
• Giải thuật của Kruskal
• Giải thuật của Prim
• Phân tích giải thuật
• Hệ thức truy hồi
• Độ phức tạp giải thuật
• Phân tích giải thuật lặp
• Phân tích giải thuật đệ quy
• Phân tích thuật giải
• Thiết kế thuật giải
• Chiến lược thiết kế thuật giải
• Quy hoạch động
• Biểu diễn thuật giải
• Phân tích thiết kế thuật toán
• Kỹ thuật tối ưu hóa chương trình
• Mức thiết kế một chương trình
• Kỹ thuật tinh chế mã
• Kỹ thuật tối ưu hóa rẽ nhánh
• Phương pháp thiết kế thuật toán
• Tối ưu thuật toán
• Cấu trúc dữ liệu giải thuật
• Bài giảng Cấu trúc dữ liệu giải thuật
• Chia để trị
• Giải thuật quay lui
• Giải thuật tìm kiếm trong đồ thị
• Biểu diễn của một đồ thị
• Biểu diễn một đồ thị vô hướng
• Biểu diễn một đồ thị có hướng
• Giải thuật sắp xếp
• Chương trình sắp xếp
• Cấu trúc dữ liệu
• Giải thuật lưu trữ ngoài
• Giải thuật nâng cao
• Kỹ thuật phân tích giải thuật
• Hệ thống thông tin
• Giải thuật hình học
• Giải thuật so khớp chuỗi
• Hình học tính toán
• Giải thuật thô sơ
• Kỹ thuật quét
• Tính đúng đắn
• Kỹ thuật mã hóa
• Giải thuật đệ quy
• Thiết kế giải thuật đệ quy
• Đệ quy tuyến tính
• Đệ quy nhị phân