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 -