zunia.vn

Tuyển sinh 2024 dành cho Gen-Z

zunia.vn

» Công Nghệ Thông Tin

» Kỹ thuật lập trình

Bài giảng Thuật toán: Chương 4 - GV. Nguyễn Thanh Cẩm

Chia sẻ: Nguyễn Hà | Ngày: | Loại File: PDF | Số trang:42

Báo xấu

180
lượt xem 33
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Chương 4 Thuật toán tham lam thuộc bài giảng thuật toán, cùng nắm kiến thức trong chương này thông qua việc tìm hiểu các nội dung chính sau: thuật toán tham lam, một số thí dụ minh họa.

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 Thuật toán: Chương 4 - GV. Nguyễn Thanh Cẩm

TRƯỜNG CAO ĐẲNG CNTT HỮU NGHỊ ViỆT - HÀN KHOA KHOA HỌC MÁY TÍNH -----------***----------- THUẬT TOÁN (Algorithms) Nguyễn Thanh Cẩm
Nội Dung C1 THUẬT TOÁN VÀ ĐỘ PHỨC TẠP C2 CHIA ĐỂ TRỊ C3 QUY HOẠCH ĐỘNG C4 THUẬT TOÁN THAM LAM C5 THUẬT TOÁN QUAY LUI Nguyễn Thanh Cẩm
THUẬT TOÁN THAM LAM 4.1 Thuật toán tham lam 4.2 Một số bài toán minh họa Nguyễn Thanh Cẩm
THUẬT TOÁN THAM LAM 4.1 Thuật toán tham lam 4.1.1 Đặc điểm chung của thuật toán tham lam 4.1.2 Thuật toán tham lam Sự khác nhau giữa thuật toán tham lam và 4.1.3 thuật toán quy hoạch động Nguyễn Thanh Cẩm
4.1.1 Đặc điểm chung của thuật toán tham lam  Một bài toán thực hiện cấu trúc con tối ưu (optimal substructure) nếu cách giải quyết tối ưu của bài toán chứa đựng cách giải quyết tối ưu những bài toán con của nó.  Đối với nhiều bài toán, thuật toán tham lam hầu như không cho ra lời giải tối ưu toàn cục, vì chúng thường không chạy trên tất cả các trường hợp. Tuy nhiên, các thuật toán này vẫn hữu ích vì chúng dễ thiết kế và cho ra các ước lượng tốt về lời giải tối ưu.  Nếu một thuật toán tham lam cho ra kết quả tối ưu toàn cục cho một lớp bài toán nào đó, thì thuật toán thường sẽ được chọn lựa, vì nó chạy nhanh hơn các phương pháp tối ưu hóa khác như quy hoạch động … Nguyễn Thanh Cẩm
4.1.2 Thuật toán tham lam Thuật tham lam có 05 thành phần:  Một tập hợp các ứng viên C (candidate), để từ đó tạo ra lời giải.  Một hàm lựa chọn Select(C), để theo đó lựa chọn ứng viên tốt nhất để bổ sung vào lời giải.  Một hàm khả thi Feasible(S  x), dùng để quyết định nếu một ứng viên có thể được dùng để xây dựng lời giải.  Một hàm mục tiêu Solution(S), ấn định giá trị của lời giải hoặc một lời giải chưa hoàn chỉnh.  Một hàm đánh giá, chỉ ra khi nào ta tìm ra một lời giải hoàn chỉnh. Nguyễn Thanh Cẩm
4.1.2 Thuật toán tham lam Thuật tham lam: void Greedy; //Giả sử C là tập các ứng cử viên { S = ; // S là lời giải xây dựng theo thuật toán While ( (C  0) and not Solution(S)) { x  Select(C); C = C\x; If (Feasible(S  x)) S=S x } If (Solution(S) ) Return S } Nguyễn Thanh Cẩm
4.1.2 Thuật toán tham lam  Chúng minh tính đúng đắn:  Để chỉ ra thuật toán không cho lời giải đúng chỉ cần đư-a ra một phản ví dụ  Việc chứng minh thuật toán đúng khó hơn nhiều và ta sẽ nghiên cứu cụ thể trong phần sau đây :  Lập luận biến đổi (Exchange Argument)  Giả sử cần chứng minh thuật toán A cho lời giải đúng. A(I) là lời giải tìm được bởi thuật toán A đối với bộ dữ liệu I. Còn O là lời giải tối ưu của bài toán với bộ dữ liệu này.  Ta cần tìm cách xây dựng phép biến đổi  để biến đổi O thành O’ sao cho:  O’ cũng tốt không kém gì O (Nghĩa là O’ vẫn tối ưu).  O’ giống với A(I) nhiều hơn O.  Giả sử đã xây dựng được phép biến đổi vừa nêu. Để chứng minh tính đúng đắn dựa vào hai sơ đồ chứng minh sau  1) Chứng minh bằng phản chứng: Giả sử A không đúng đắn, hãy tìm bộ dữ liệu I sao cho A(I) khác với lời giải tối ưu của bài toán. Gọi O là lời giải tối ưu giống với A(I) nhất => A(I) khác O. Dùng phép biến đổi  chúng ta có thể biến đổi O  O’ sao cho O’ vẫn tối ưu và O’ giống với A(I) hơn => mâu thuẫn giả thiết O là lời giải tối ưu giống với A(I) nhất.  2) Chứng minh trực tiếp: O là lời giải tối ưu. Biến đổi O  O’ giống với A(I) hơn là O. Nếu O’ = A(I) thì A(I) chính là phương án tối ưu ngược lại biến đổi O’  O’’ giống với A(I) hơn. Cứ thế ta thu được dãy O’, O’’ ,O’’’ …..ngày càng giống hơn, và chỉ có một số hữu hạn điều kiện để so sánh nên chỉ sau một số hữu hạn lần phép biến đổi sẽ kết thúc và đó là tại A(I). Nguyễn Thanh Cẩm
4.1.3 Sự khác nhau giữa thuật toán tham lam và thuật toán quy hoạch động  Toàn bộ phương pháp tối ưu có thể đạt được, từ việc chọn tối ưu trong từng bước chọn. Về khía cạnh này, thuật toán tham lam khác với thuật toán quy hoạch động ở chỗ:  Trong quy hoạch động chúng ta thực hiện chọn cho từng bước, nhưng việc lựa chọn này phụ thuộc vào cách giải quyết các bài toán con.  Với thuật toán tham lam, tại mỗi bước chúng ta chọn bất cứ cái gì là tốt nhất vào thời điểm hiện tại, và sau đó giải quyết các vấn đề phát sinh từ việc chọn này. Vấn đề chọn thực hiện bởi thuật toán tham lam không phụ thuộc vào việc lựa chọn trong tương lai hay cách giải quyết các bài toán con.  Vì vậy khác với quy hoạch động, giải quyết các bài toán con theo kiểu bottom-up (từ dưới lên), thuật toán tham lam thường sử dụng giải pháp top-down (từ trên xuống). Nguyễn Thanh Cẩm
THUẬT TOÁN THAM LAM 4.2 Một số bài toán minh họa 4.2.1 Bài toán đường đi của người giao hàng 4.2.2 Bài toán các đoạn thẳng không giao nhau 4.2.3 Bài toán cái ba lô 4.2.4 Bài toán cây khung nhỏ nhất Nguyễn Thanh Cẩm
4.2.1 Bài toán đường đi của người giao hàng  Bài toán: Có một người đi giao hàng, cần đi giao hàng tai n thành phố. Xuất phát tại một thành phố nào đó đi qua các thành phố khác để giao hàng và trở về thành phố ban đầu. Mỗi thành phố chỉ đến 1 lần khoảng cách từ một thành phố đến các thành phố khác là xác định. Giả thiết rằng, mỗi thành phố đều có đường đi đến các thành phố còn lại. Khoảng cách giữa hai thành phố có thể là khoảng cách địa lý, có thể là cước phí di chuyển hoặc thời gian di chuyển. Ta gọi chung là độ dài. Hãy tìm một chu trình (một đường đi khép kín thỏa mãn điều kiện trên) sao cho tổng độ dài các cạnh là nhỏ nhất, hay nói cách khác là tìm một phương án có giá trị nhỏ nhất. Bài toán này cũng được gọi là bài toán người du lịch.  Một cách tổng quát, có thể không tồn tại một đường đi giữa hai thành phố a và b nào đó. Trong trường hợp đó ta cho đường đi ảo giữa a và b với độ dài bằng ∞ Nguyễn Thanh Cẩm
4.2.1 Bài toán đường đi của người giao hàng  Bài toán này có nhiều ứng dụng rất quan trọng. Thí dụ một máy hàn các điểm được điều khiển bởi máy tính. Nhiệm vụ của nó là hàn một số điểm dự định ở trên một tấm kim loại. Người thợ hàn bắt đầu từ một điểm ở bên ngoài tấm kim loại và kết thúc tại chính điểm này, do đó tấm kim loại phải được di chuyển đến điểm cần hàn được đưa vào vị trí hàn ( tương tự như ta đưa tấm vải vào đầu mũi kim của máy khâu). Cần tìm một phương án di chuyến tấm kim loại sao cho việc di chuyến ít nhất.  Hình ảnh sau minh họa bài toán trên:            Nguyễn Thanh Cẩm
4.2.1 Bài toán đường đi của người giao hàng  Với phương pháp véc cạn ta xét tất cả các chu trình, mỗi chu trình tính tổng độ dài các cạnh của nó rồi chọn một chu trình có tổng độ dài nhỏ nhất.  Tuy nhiên chúng ta cần xét tất cả (n-1)! chu trình. Thật vậy do mỗi chu trình đi qua tất cả các đỉnh (thành phố) nên ta cố định một đỉnh. Từ đỉnh này ta có n-1 cạnh tới n-1 đỉnh khác nên ta có n-1 cách chọn cạnh đầu tiên của chu trình. Sau khi đã chọn được cạnh đầu tiên chúng ta có n-2 cách chọn cạnh thứ hai, do đó ta có (n-1)(n-2) cách chọn hai cạnh. Cứ lý luận như vậy ta sẽ có (n-1)! cách chọn chu trình khác nhau. Và đó là một thuật toán với thời gian lớn hơn hàm mũ. Nguyễn Thanh Cẩm
4.2.1 Bài toán đường đi của người giao hàng  Áp dụng kỹ thuật tham lam ta có: B1: Sắp xếp các cạnh theo thứ tự tăng của độ dài B2: Xét các cạnh có độ dài từ nhỏ đến lớn để đưa vào chu trình B3: Một cạnh sẽ được đưa vào chu trình sẽ thỏa mãn: Không tạo thành một chu trình con Không tạo thành một đỉnh có cấp >= 3 Lặp lại bước ba cho đến khi được một chu trình. Nguyễn Thanh Cẩm
4.2.1 Bài toán đường đi của người giao hàng  Thí dụ: cho bài toán TSP với 6 đỉnh được cho bởi các tọa độ sau: c(1,7) d(15,7) b(4,3) e(15,4) a(0,0) f(18,0)  6 thành phố có tất cả 15 cạnh. Đó là các cạnh ab, ac, ad, ae, af, bc, bd, be, bf, cd, ce, cf, de, df, ef. Độ dài các cạnh ở đây là khoảng cách Euclide trong đó cạnh de = 3 là nhỏ nhất nên de được chọn vào chu trình. Kế đến là 3 cạnh ab,bc ef đều có độ dài 5 cả 3 cạnh đều thỏa mãn hai điều kiện nói trên nên đều được chọn vào chu trình, cạnh có độ dài nhỏ nhất kế tiếp là ac = 7.08 nhưng không thể đưa cạnh này vào chu trình vì nó sẽ tạo ra chu trình con (abca) cạnh df cũng bị lý do tương tự. Cạnh be cũng được xem xét rồi cũng bị loại do tạo ra đỉnh b và đỉnh e có cấp 3, tương tự chúng ta cũng loại bd. cd là cạnh tiếp theo được xét và được chọn cuối cùng ta có chu trình abcdefa với tổng độ dài là 50. Đây chỉ là một phương án tốt. Phương án tối ưu là chu trình acdefba với tổng độ dài là 48.39 Nguyễn Thanh Cẩm
4.2.1 Bài toán đường đi của người giao hàng c(1,7) d(15,7) c(1,7) d(15,7) b(4,3) e(15,4) b(4,3) e(15,4) a(0,0) f(18,0) a(0,0) f(18,0) Nguyễn Thanh Cẩm
4.2.1 Bài toán đường đi của người giao hàng  Thuật toán: void Tsp { chutrinh = 0 // sắp xếp các cạnh trong E theo thứ tự tăng của độ dài Gia = 0 while E0 do { if(cạnh có thể chọn) //không tạo thành chu trình Chutrinh = chutrinh + [e] Gia = gia + đồdàicủa e } E = E – [e] }  Độ phức tạp của thuật toán: Với đồ thị n đỉnh đầy đủ ta có n(n-1)/2 cạnh. Hơn nữa thuật toán chỉ phụ thuộc vào việc sắp xếp theo sự không giảm theo độ dài của các cạnh. Nên độ phức tạp của thuật toán cỡ O(n) nếu chọn phương pháp sắp xếp QuickSort. Nguyễn Thanh Cẩm
THUẬT TOÁN THAM LAM 4.2 Một số bài toán minh họa 4.2.1 Bài toán đường đi của người giao hàng 4.2.2 Bài toán các đoạn thẳng không giao nhau 4.2.3 Bài toán cái ba lô 4.2.4 Bài toán cây khung nhỏ nhất Nguyễn Thanh Cẩm
4.2.2 Bài toán các đoạn thẳng không giao nhau  Bài toán  Đầu vào: Cho họ các đoạn thẳng mở  Đầu ra: Tập các đoạn thẳng không giao nhau có lực lượng lớn nhất.  Ứng dụng thực tế: Bài toán xếp thời gian biểu cho các hội thảo, bài toán phục vụ khách hành trên một máy, bài toán lựa chọn hành động (Ví dụ có n lời mời dự tiệc bắt đầu bởi ai kết thúc bởi bj, hãy lựa chọn sao cho đi đ-ược nhiều tiệc nhất). Nguyễn Thanh Cẩm
4.2.2 Bài toán các đoạn thẳng không giao nhau  Đề xuất các thuật toán:  Greedy 1: Sắp xếp các đoạn thẳng theo thứ tự tăng dần của đầu mút trái, bắt đầu từ tập S là tập rỗng, ta lần lượt xếp các đoạn thẳng trong danh sách đã sắp xếp và bổ sung đoạn thẳng đang xét vào S nếu nó không có điểm chung với bất cứ đoạn nào trong S. Thuật toán: void Greedy1; { S = ; //S là tập các đoạn thẳng cần tìm While (C  0) { (ai, bi)  đoạn đầu tiên trong C; C = C\(ai, bi); If () S = S  (ai, bi) } } Nguyễn Thanh Cẩm

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.