Bài giảng Phân tích thiết kế giải thuật: The Greedy algorithms - GV. Hà Đại Dương

Bài giảng trình bày về các tối ưu thuật toán bằng phương pháp tham lam và các bài tập minh họa: bài toán cái túi, bài toán người du lịch, đường đi ngắn nhất,... Để tìm hiểu rõ hơn về nội dung chi tiết của bài giảng, mời các bạn cùng tham khảo.
Nội dung trích xuất từ tài liệu:
Bài giảng Phân tích thiết kế giải thuật: The Greedy algorithms - GV. Hà Đại Dương2/2/2017Analysis and Design of AlgorithmsLecture 6,7The Greedy algorithmsLecturer: Ha Dai Duongduonghd@mta.edu.vn2/2/20171Nội dung1.2.3.4.5.6.7.Lược đồ chungBài toán cái túiBài toán người du lịchĐường đi ngắn nhấtCây bao trùm nhỏ nhấtBài toán tô màuBài toán các khoảng không giao nhau2/2/20172Nội dung1.2.3.4.5.6.7.Lược đồ chungBài toán cái túiBài toán người du lịchĐường đi ngắn nhấtCây bao trùm nhỏ nhấtBài toán tô màuBài toán các khoảng không giao nhau2/2/2017312/2/2017Bài toán tối ưu• PP Tham lam thường dùng cho các bàitoán tối ưu tổ hợp (tối ưu rời rạc)• Bài toán tối ưu tổ hợp có dạng chungmin{f(x):xD}Trong đó D tập hữu hạn các điểm rời rạcnào đó thuộc không gian Rn2/2/20174Ví dụ Máy ATM có 4 (m) loại tiền: 100.000, 50.000, 20.000,10.000; một người muốn rút số tiền là n (n chia hết cho10.000). Hãy tìm phương án trả tiền sao cho số tờ tiềnphải trả là ít nhất. Gọi x=(x1,x2,x3,x4) là một phương án trả tiền; x1, x2,x3, x4 là số tờ tiền phải trả tương ứng với các mệnh giá100.000, 50.000, 20.000,10.000. Theo bài ra ta cần giải:min(f=x1+x2+x3+x4)Với: điều kiện- 100.000x1+50.000x2+20.000x3+10.000x4 = n- xi>=0 (i=1..4)2/2/20175Giải quyết …• Với bài toán tối ưu tổ hợpmin{f(x):xD}• Để tìm phương án tối ưu của bài toán trênngười ta có thể so sánh lần lượt giá trị củaf tại tất cả các phương án thuộc D; cáchnày gọi là “duyệt vét cạn”.• Khi số phần tử của D lớn (dù là hữu hạn)thì việc duyệt vét cạn vẫn gặp nhiều khókhăn.2/2/2017622/2/2017PP Tham lam• PP tham lam đưa ra quyết định dựa ngay vàothông tin đang có, và trong tương lai sẽkhông xem xét lại tác động của các quyếtđịnh trong quá khứ.• Chính vì thế các thuật toán dạng này rất dễđề xuất, và thông thường chúng không đòihỏi nhiều thời gian tính.• Tuy nhiên, các thuật toán dạng này thườngkhông cho kết quả tối ưu.2/2/20177Ý tưởng• Xuất phát từ lời giải rỗng, thuật toán xây dựnglời giải của bài toán theo từng bước, ở mỗibước sẽ chọn một phần tử từ tập ứng cử viênvà bổ sung vào lời giải hiện có.• Hàm Solution(S) nhận biết tính chấp nhận đượccủa lời giải S.• Hàm Select(C) chọn từ tập C ứng cử viên cótriển vọng nhất để bổ sung vào lời giải hiện có.• Hàm Feasible(S+x) kiểm tra tính chấp nhậnđược của lời giải bộ phận S+x.2/2/20178Lược đồ chung2/2/2017932/2/2017Tính đúng đắn của kết quả• Để chỉ ra thuật toán không đúng đắn chỉcần đưa ra một phản ví dụ (một bộ dữ liệumà đối với nó thuật toán không cho lời giảiđúng)• Chứng minh tính đúng đắn của thuật toánkhó hơn nhiều2/2/201710Nội dung1.2.3.4.5.6.7.Lược đồ chungBài toán cái túiBài toán người du lịchĐường đi ngắn nhấtCây bao trùm nhỏ nhấtBài toán tô màuBài toán các khoảng không giao nhau2/2/201711Bài toán(Knapsack Problem)• Có n đồ vật, đồ vật i có trọng lượng wi vàgiá trị ci, i = 1, 2, ..., n.• Tìm cách chất các đồ vật này vào cái túicó trọng lượng là b sao cho tổng trọnglượng của các đồ vật được chất vào túi làkhông quá b, đồng thời tổng giá trị củachúng là lớn nhất.2/2/20171242/2/2017Khái quát• Ký hiệu C = {1, 2, ..., n} tập chỉ số các đồvật.• Bài toán đặt ra là Tìm I ⊂ C sao choV=với2/2/201713Tham lam 1 (Greedy1)• Ý tưởng (tham lam): Đồ vật có giá trị lớn(nhất) còn lại được lấy trước (nếu có thể).• Chi tiết:– Sắp xếp các đồ vật theo thứ tự không tăngcủa giá trị.– Chọn đồ vật từ đầu đến cuối (từ có giá trị caođến có giá trị thấp hơn) nếu dung lượng cònlại của túi đủ chứa nó.2/2/201714Ví dụ 1• Số lượng đồ vật n = 3• Trọng lượng và giá trị các đồ vật là:• Trọng lượng cái túi b = 19Greedy12/2/2017I={1}V = 20Tối ưuI*={2,3}V* = 24155