Đề Tài: Thiết Kế Thuật Toán Vét Cạn Và Tham Lam - Tài Liệu Text - 123doc

Tải bản đầy đủ (.pdf) (29 trang)

1. Trang chủ
>>
2. Luận Văn - Báo Cáo
>>
3. Công nghệ thông tin

Đề tài: Thiết kế thuật toán vét cạn và tham lam

Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (387.24 KB, 29 trang )

THIẾT KẾ GIẢI THUẬTNội dung của chương này trình bày hai chiến lược thiết kế thuật giải thôngdụng là vét cạn và tham lam. Nội dung của chương, ngoài phần trình bày về cácphương pháp còn có những ví dụ cụ thể, cả thuật giải và cài đặt, để người đọc cómột cái nhìn chi tiết về việc từ thuật toán đến chương trình.1. Vét cạn (Exhausted search)Vét cạn, duyệt, quay lui… là một số tên gọi tuy không đồng nghĩa nhưngcùng chỉ một phương pháp rất đơn giản trong tin học: tìm nghiệm của một bàitoán bằng cách xem xét tất cả các phương án có thể. Đối với con người phươngpháp này thường là không khả thi vì số phương án cần kiểm tra quá lớn. Tuy nhiênđối với máy tính, nhờ tốc độ xử lí nhanh, máy tính có thể giải rất nhiều bài toánbằng phương pháp vét cạn.Ưu điểm lớn nhất của phương pháp vét cạn là luôn đảm bảo tìm ra nghiệmchính xác. Ngoài ra phương pháp vét cạn còn có một số ưu điểm so với cácphương pháp khác là đòi hỏi rất ít bộ nhớ và cài đặt đơn giản. Hạn chế duy nhấtcủa phương pháp này là thời gian thực thi rất lớn, độ phức tạp thường ở bậc mũ.Do đó vét cạn thường chỉ áp dụng tốt với các bài toán có kích thước nhỏ.1.1. Bài toán tìm cấu hình tổ hợpThường những bài toán trong Tin học có yêu cầu dạng: tìm các đối tượng xthoả mãn những điều kiện nhất định trong một tập S các đối tượng cho trước. Bàitoán tìm cấu hình tổ hợp là bài toán yêu cầu tìm các đối tượng x có dạng là mộtvector thoả mãn các điều kiện sau:1. Đối tượng x gồm n phần tử: x = (x1,x2,…xn).2. Mỗi phần tử xi có thể nhận một trong các giá trị rời rạc a1, a2, … am.3. x thoả mãn các ràng buộc có thể cho bởi hàm logic G(x).Tuỳ từng trường hợp mà bài toán có thể yêu cầu: tìm một nghiệm, tìm tất cảnghiệm hoặc đếm số nghiệm.Trước hết chúng ta nhắc lại một số cấu hình tổ hợp cơ bản.a) Tổ hợpMột tổ hợp chập k của n là một tập con k phần tử của tập n phần tử.Chẳng hạn tập {1,2,3,4} có các tổ hợp chập 2 là: {1,2}, {1,3, {1,4, {2,3}, {2,4},{3,4}. Vì trong tập hợp các phần tử không phân biệt thứ tự nên tập {1,2} cũng làtập {2,1} và do đó, ta coi chúng chỉ là một tổ hợp.Bài toán đặt ra cho chúng ta là hãy xác định tất cả các tổ hợp châp k củatập n phần tử. Để đơn giản ta chỉ xét bài toán tìm các tổ hợp của tập các sốnguyên từ 1 đến n. Đối với một tập hữu hạn bất kì, bằng cách đánh số thứ tự củacác phần tử, ta cũng đưa được về bài toán đối với tập các số nguyên từ 1 đến n.Nghiệm cần tìm của bài toán tìm các tổ hợp chập k của n phần tử phải thoả mãncác điều kiện sau:1. Là một vector x =(x1,x2,…xk)2. xi lấy giá trị trong tập {1,2,…n}3. Ràng buộc: xi= w[i] then beginm := m - w[i];t := t + v[i];s := s + [id[i]];end;end;end;Kết quả: S là tập các đồ vật được chọn, T là tổng giá trị của chúng. Thuậtgiải này có độ phức tạp O(nlogn) do thao tác chủ yếu ở phần sắp xếp.2.3. Bài toán người du lịchCó nhiều giải thuật tham lam khác nhau giải bài toán này. Chúng tôi xintrình bày một giải thuật theo chiến lược chọn cái tốt trước và một giải thuật theochiến lược cải tiến cái hiện có.Giải thuật theo chiến lược chọn cái tốt nhất trước có ý tưởng rất đơn giản:tại mỗi bước ta sẽ chọn thành phố tiếp theo là thành phố chưa đến thăm mà chi phítừ thành phố hiện tại đến thành phố đó là thấp nhất.Giải thuật theo chiến lược cải tiến cái hiện có cũng có ý tưởng rất đơn giản:xuất phát từ một lộ trình nào đó (1,2,..n chẳng hạn), ta cải tiến lộ trình hiện cóbằng cách tìm 2 thành phố mà đổi chỗ chúng cho nhau thì tổng chi phí giảm đi.Quá trình đó dừng lại khi không còn cải tiến được hơn nữa.Dựa trên 2 ý tưởng đó, bạn đọc có thể dễ dàng xây dựng được các thuật giải.Thuật giải thứ nhất có độ phức tạp tính toán là O(n2), thuật giải thứ hai có độ phứctạp tính toán là O(n3).Ngoài 2 giải thuật trên, người ta còn xây dựng được giải thuật di truyền chobài toán này. ý tưởng cơ bản là thay vì xuất phát từ một phương án, chúng ta xử línhiều phương án đồng thời, cải tiến chúng bằng việc mô phỏng quá trình di truyền,thích nghi và tiến hoá của sinh vật để có được những phương án ngày một tốt hơn.Tuy nhiên vấn đề đó nằm ngoài khuôn khổ của cuốn giáo trình này.Đối với đồ thị metric (tức là có bất đẳng thức tam giác d[i,j]