Tài liệu Báo cáo thực tập-phân tích và thiết kế thuật toán bài toán cái túi

  • Số trang: 11 |
  • Loại file: PDF |
  • Lượt xem: 319 |
  • Lượt tải: 4
quangtran

Đã đăng 3721 tài liệu

Mô tả:

TRƯỜNG ĐẠI HỌC BÁCH KHOA HÀ NỘI Viện Công nghệ Thông tin và Truyền thông BÀI TẬP LỚN MÔN PHÂN TÍCH VÀ THIẾT KẾ THUẬT TOÁN Đề tài: BÀI TOÁN CÁI TÚI Sinh viên thực hiện: Nguyễn Đăng Tuấn SHSV: 20073178 Mã lớp: 14489 Giáo viên hướng dẫn: PGS Nguyễn Đức Nghĩa HÀ NỘI 2010 1 Mục lục Mục lục............................................................................................................2 BÀI TOÁN ĐẶT RA............................................................................................2 Giới thiệu bài toán tối ưu:.............................................................................3 Bài toán cái túi..............................................................................................3 THUẬT TOÁN....................................................................................................4 Ý tưởng: phương pháp quy hoạch động........................................................5 Phương pháp tiến hành.................................................................................5 Kết quả cho một bài toán cụ thể..................................................................7 CHƯƠNG TRÌNH CÀI ĐẶT.................................................................................8 Listing của chương trình nguồn....................................................................8 Nhập dữ liệu vào cho chương trình...............................................................8 Hướng dẫn.................................................................................................8 Demo chương trình....................................................................................9 Chương trình giải bài toán cái túi..................................................................9 Hướng dẫn sử dụng: .................................................................................9 Demo chương trình..................................................................................10 KẾT LUẬN.......................................................................................................11 TÀI LIỆU THAM KHẢO.....................................................................................11 BÀI TOÁN ĐẶT RA 2 Giới thiệu bài toán tối ưu:  Trong rất nhiều vấn đề ứng dụng thực tế của tổ hợp các cấu hình tổ hợp còn được gán cho một giá trị bằng số đánh giá giá trị sử dụng của cấu hình đối với mục đích sử dụng cụ thể nào đó. Khi đó xuất hiện bài toán : Hãy lựa chọn trong số các cấu hình tổ hợp chấp nhận được cấu hình có giá trị sử dụng tốt nhất.Các bài toán như vậy được gọi là bài toán tối ưu tổ hợp.Dưới dạng tổng quát bài toán tối ưu tổ hợp có thể phát biểu như sau:  Tìm cực tiểu(hay cực đại) của phiếm hàm: f(x) →min(max), với điều kiện x € D, trong đó D là tập hữu hạn phần tử.  Hàm f(x) được gọi là hàm mục tiêu của bài toán,mỗi phần tử x € D được gọi là một phương án còn tập D gọi là tập các phương án của bài toán.  Thông thường tập D được mô tả như là tập các cấu hình tổ hợp thỏa mãn một số tính chất cho trước nào đó.  Phương án x‫ ٭‬€ D đem lại giá trị nhỏ nhất(lớn nhất) cho hàm mục tiêu được gọi là phương án tối ưu,khi đó giá trị f‫ = ٭‬f(x‫ )٭‬được gọi là giá trị tối ưu của bài toán. Bài toán cái túi Bài toán xếp cái túi (hay là bài toán ba lô) là một bài toán tối ưu hóa tổ hợp. Bài toán được đặt tên từ vấn đề chọn những gì quan trọng có thể nhét vừa vào trong một cái túi (với giới hạn khối lượng) để mang theo trong một chuyến đi. Các bài toán tương tự thường xuất hiện trong kinh doanh, toán tổ hợp, lý thuyết độ phức tạp tính toán, mật mã học và toán ứng dụng. Phát biểu bài toán: Đề bài :Một nhà thám hiểm cần đem theo 1 cái túi có trọng lượng ko quá L.Có N đồ vật đem theo, đồ vật thứ i có trọng lượng w i, có giá trị sử dụng vi. Hãy tìm cách đưa đồ vật vào túi cho nhà thám hiểm sao cho tổng giá trị sử dụng các đồ vật trong túi là lớn nhất. 3 Yêu cầu đặt ra là cực đại hóa hàm: F(x) = v1 x1 + v2 x2 + ..+ vN xN, với x = 0,1; Với: w1 x1 + w2 x2 + ..+ wN xN < = L THUẬT TOÁN 4 Ý tưởng: phương pháp quy hoạch động Phương pháp quy hoạch động dùng để giải bài toán tối ưu có bản chất đệ quy, tức là việc tìm phương án tối ưu cho bài toán đó có thể đưa về tìm phương án tối ưu của một số hữu hạn các bài toán con. Đối với nhiều thuật toán đệ quy chúng ta đã tìm hiểu, nguyên lý chia để trị (divide and conquer) thường đóng vai trò chủ đạo trong việc thiết kế thuật toán. Để giải quyết một bài toán lớn, ta chia nó làm nhiều bài toán con cùng dạng với nó để có thể giải quyết độc lập. Trong phương pháp quy hoạch động, nguyên lý này càng được thể hiện rõ: Khi không biết cần phải giải quyết những bàitoán con nào, ta sẽ đi giải quyết tất cả các bài toán con và lưu trữ những lời giải hay đáp số của chúng với mục đích sử dụng lại theo một sự phối hợp nào đó để giải quyết những bài toán tổng quát hơn. Đó chính là điểm khác nhau giữa Quy hoạch động và phép phân giải đệ quy và cũng là nội dung phương pháp quy hoạch động: • Phép phân giải đệ quy bắt đầu từ bài toán lớn phân rã thành nhiều bài toán con và đi giải từng bài toán con đó. Việc giải từng bài toán con lại đưa về phép phân rã tiếp thành nhiều bài toán nhỏ hơn và lại đi giải tiếp bài toán nhỏ hơn đó bất kể nó đã được giải hay chưa. • Quy hoạch động bắt đầu từ việc giải tất cả các bài toán nhỏ nhất ( bài toán cơ sở) để từ đó từng bước giải quyết những bài toán lớn hơn, cho tới khi giải được bài toán lớn nhất (bài toán ban đầu). Phương pháp tiến hành a) Phân rã Với mỗi 1 <=k<=N và 0<=S<=L, xét bài toán tính Value[ k, S ] là tổng giá trị lớn nhất của các đồ vật được chọn trong số k đồ vật đầu tiên và có trọng lượng không quá S Cơ sở quy hoạch động: • Có tất cả N(L+1) bài toán con • Bài toán cần giải là tính Value[ N, L] b) Tổng hợp lời giải Value [0, S] = 0 với S= 1,2,..,L 5 Value [k, 0] = 0 với k= 1….N Value [1,S]=v1 nếu S>=w1 Value [1,S]=v1 nếu S < w1 Giả sử đã tính được Value [i,j] với mọi 1<=i=wk, ta có 2 lựa chọn: • Chất đồ vật thứ k vào túi, khi đó giá trị của cách chất tối ưu là Value[k-1,S - wk] • Không chất đồ vật thứ k vào túi, do đó cách chất tối ưu chỉ có thể sử dụng k-1 đồ vật trước đó và có giá trị là Value [k-1,S] Vậy: Value[0, S] = 0 Value [k, 0] = 0 Value [k,S ] = Value[k - 1, S] nếu S=wk c) Đưa ra phương án chất đồ // lần ngược theo lời giải tối ưu Let k=N and S=L if Value [k,S] <> Value [k-1,S] then chất đồ vật thứ k vào túi k = k-1, S=S-wk else k = k-1 // duyệt tiếp đối với đồ vật tiếp theo // dừng khi k=0 và S=0 d) Đánh giá độ phức tạp 6 Bài toán cái túi có thời gian tính là O(NL). Thời gian này phụ thuộc tuyến tính vào dữ liệu vào L, nhưng nếu xét nó như hàm của độ dài dữ liệu vào thì l=[log L] thì sự phụ thuộc này lại là hàm mũ. Thuật toán làm việc hiệu quả khi L không qua lớn Kết quả cho một bài toán cụ thể Giải bài toán cái túi: STT 1 2 3 4 5 6 7 GIÁ TRỊ 6 4 4 5 6 12 3 TRỌNG LƯỢNG 7 9 2 7 3 4 4 Số đồ vật: N=7, trọng lượng cái túi: L= 12 Bảng kết quả tính Value[k,S] k S 0 1 2 3 4 5 6 7 8 9 10 11 12 0 1 2 3 4 5 6 7 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 6 6 6 6 6 6 0 0 0 0 0 0 0 6 6 6 6 6 6 0 0 4 4 4 4 4 6 6 10 10 10 10 0 0 4 4 4 4 4 6 6 10 10 10 10 0 0 4 6 6 10 10 10 10 10 12 12 16 0 0 4 6 12 12 16 18 18 22 22 22 22 0 0 4 6 12 12 16 18 18 22 22 22 22 Giá trị tối ưu là 22 Phương án chất các đồ vật: đồ vật thứ 3,5,6 7 CHƯƠNG TRÌNH CÀI ĐẶT Listing của chương trình nguồn • Input.txt: chứa dữ liệu vào cho chương trình • Knapsack.cpp, Knapsack.exe: Chương trình giải bài toán cái túi Nhập dữ liệu vào cho chương trình Hướng dẫn File Input.txt file này làm nhiệm vụ chứa dữ liệu vào cho chương trình, cách nhập dữ liệu vào như sau: • Dòng thứ nhất: trọng lượng cái túi • Dòng thứ hai: số lượng đồ vật 8 • Các dòng tiếp theo: thự tự gồm “giá trị đồ vật” và “trọng lượng đồ vật”. Mỗi đồ vật trên một dòng Kết quả: xem file ou Input.txt Demo chương trình Nhập thông tin vào input.txt Chương trình giải bài toán cái túi Hướng dẫn sử dụng: • Tạo hoặc sửa thông tin cho file dữ liệu đầu vào input.txt. Nhập tên file kết quả • Chạy file Knapsack.exe • Xem kết quả ở file output.txt 9 Demo chương trình 10 KẾT LUẬN Chương trình đã cơ bản hoàn thành được yêu cầu mà bài toán đặt ra Chương trình cần được mở rộng thành bài toán cái túi đầy đủ Em xin chân thành cám ơn thầy Nguyễn Đức Nghĩa vì sự tận tình giúp đỡ của thầy trong thời gian qua TÀI LIỆU THAM KHẢO Giáo trình phân tích và thiết kế thuật toán : Nguyễn Đức Nghĩa 11
- Xem thêm -