Bài giảng Toán rời rạc: Thuật toán tham lam - Trần Vĩnh Đức

Bài giảng Toán rời rạc: Thuật toán tham lam cung cấp cho người học những nội dung kiến thức như: Cây bao trùm nhỏ nhất, mã hóa Huffman, công thức Horn, phủ các tập. Mời các bạn cùng tham khảo để biết thêm nội dung chi tiết.
Nội dung trích xuất từ tài liệu:
Bài giảng Toán rời rạc: Thuật toán tham lam - Trần Vĩnh Đức Thuật toán tham lam Trần Vĩnh Đức HUST Ngày 1 tháng 9 năm 2019CuuDuongThanCong.com https://fb.com/tailieudientucntt 1 / 64 Tài liệu tham khảo I S. Dasgupta, C. H. Papadimitriou, and U. V. Vazirani, Algorithms, July 18, 2006.CuuDuongThanCong.com https://fb.com/tailieudientucntt 2 / 64 Nội dung Cây bao trùm nhỏ nhất Mã hóa Huffman Công thức Horn Phủ các tậpCuuDuongThanCong.com https://fb.com/tailieudientucnttted edges are potential links, and the goal is to pick enough of the Bài toán nodes are connected. But this is not all; each link also has a mainflected in that edge’s weight. What is the cheapest possible networ 1 A C E 4 4 3 4 2 5 B 4 D 6 FmediateIobservation is that the optimal set of edges cannot contain Bạn cần xây dựng mạng máy tính bằng cách kết nối từng cặpe removingmáy. an edge from this cycle would reduce the cost withoutconnectivity: I Cần chọn một số kết nối để mạng liên thông; I nhưng không phải tất cả các cặp: Mỗi kết nối tốn một chi phíy1 Removing a cycle edge cannot disconnect a graph. (tiền bảo trì).solutionImust Mạngbe vớiconnected chi phí nhỏ nhất and làacyclic: gì? undirected graphs of thisrees. The particular tree CuuDuongThanCong.com we want is the one with minimum tota https://fb.com/tailieudientucntt 4 / 64 nodes are connected. But this is not all; each link also has a mainflected in that edge’s weight. What is the cheapest possible networ 1 A C E 4 4 3 4 2 5 B 4 D 6 Fmediate observation is that the optimal set of edges cannot contain Tính chấte removing ancạnh Xóa một edge from trên this cycle chu trình would không làm mất reduce tính liên the cost thông củawithout đồconnectivity: thị.y 1 Vậy, Removing mạng vớiachi cycle phí edge cannot nhỏ nhất disconnect phải là một cây. a graph.solution must be connected and acyclic: undirected graphs of thisrees. The particular tree we want is the one with minimum totaas the minimum spanning CuuDuongThanCong.com tree. Here is its formal definition. 5 / 64 https://fb.com/tailieudientucntt Bài toán Cây bao trùm nhỏ nhất (Minimal Spaning Tree) I Input: Đồ thị vô hướng G = (V, E); mỗi cạnh có trọng số we . I Output: Một cây T = (V, E′ ) với E′ ⊆ E, với tổng trọng số ∑ weight(T) = we e∈E′ là nhỏ nhất.CuuDuongThanCong.com https://fb.com/tailieudientucntt 6 / 64um spanning trees Input: An undirected graph G = (V, E ); edge weights we . Tìm tocây e asked bao atrùm network collection of computers by linking selected Output: A tree T = (V, E ′ ), with E ′ ⊆ E , that minimizes his translates into a graph problem in which nodes are computers, ! s are potential links, and the goal is to pick enough of weight(T) these edges = we .are connected. But this is not all; each link also has a maintenance e∈E ′n that edge’s weight. WhatInisthe thepreceding cheapestexample, po ...