KHOA CÔNG NGHỆ THÔNG TIN
-----  -----

BÀI TẬP LỚN

Bài toán phân phối áo áp dụng phương
pháp xấp xỉ

Giảng viên hướng dẫn: PGS.TS Đào Thanh Tĩnh
Học viên thực hiện: Lê Văn Hợp
Lớp: Cao học 25B - HTTT

Hà nội, 05/ 2014


Phân tích và đánh giá thuật toán

Mục lục

LỜI NÓI ĐẦU
Phân tích và đánh giá thuật toán là một trong những nhân tố quan
trọng xác định được hiệu năng hệ thống khi giải quyết bài toán tin học đặt
ra. Có nhiều bài toán (thuật toán) được đưa ra chỉ tốt ở một mức độ nào đó
chấp nhận được. Việc tính toán cho phép chấp nhận một sai số nào đó. Vì
vậy, thời gian gần đây phương pháp xấp xỉ được quan tâm và phát triển
trong một số ứng dụng. Có rất nhiều bài toán mà ta có thể giải bằng phương
pháp này. Trong đó phải đề cấp đến bài toán phân phối áo, đây là một bài
toán tối ưu hóa. Bài toán được đặt tên từ vấn đề lựa chọn cách phân phối áo
sao cho kết quả thu được là độ lệch cực tiểu.
Liên quan đến việc giải quyết bài toán này chúng ta có rất nhiều
phương án khác nhau như: Phương pháp sắp xếp (vun đống), phương pháp

, ) ≤ ρ ( n)
C* C

+ Bài toán cực tiểu hóa: C ≥ C* > 0, khi đó ρ(n)=C/C*
+ Bài toán cực đại hóa: C* ≥ C > 0, khi đó ρ(n)=C*/C

Một thuật toán với tỷ lệ xấp xỉ ρ(n) được gọi là thuật toán xấp xỉ-ρ(n). Ta
luôn có: ρ(n) ≥ 1
Lê Văn Hợp – Cao học 25B – HTTT

3


Phân tích và đánh giá thuật toán
Nếu ρ(n) càng nhỏ thì giải pháp xấp xỉ càng gần với giải pháp tối ưu.
Thuật toán xấp xỉ-1 cho giải pháp tối ưu (nghĩa là ρ(n)=1)
2. Yêu cầu của thuật toán xấp xỉ:
Một thuật toán xấp xỉ phải thoả mãn các yêu cầu sau đây:
−
−
−
−

II.

Dễ tính, dễ chương trình hoá.
Ước lượng được sai số gặp phải.
Tính được thời gian chạy của thuật toán.
Chứng minh được tính đúng đắn của thuật toán.


− Đánh giá được độ phức tạp của thuật toán.
− Khả năng nâng cao số phần tử tối đa của hai mảng dữ liệu đầu vào có

thể lên đến 1.000.000 phần tử. Do vậy, bài toán phải tính đến khả
năng không thể chứa hết trong bộ nhớ quy ước.
2. Các ví dụ minh họa
Ví dụ 1:
Kích thước vai áo có số thứ tự là: V(1,2…8) = {19, 8, 6, 11, 9, 13, 5, 14}
Kích thước vai học sinh có số thứ tự là: p(1,2..8) = {15, 4, 3, 2, 6, 5, 1, 10}

Phương án 1:
Phân phối các áo có kích thước vai V1, V2,...V8 tương ứng với các học
sinh kích thước vai p1, p2,...p8
Khi đó độ lệnh của phương án phân phối là .
d1 = max {|V(i) – p(π i)|, i=1,2,...,8}
d1 = max {(19–15), (8–4), (6–3), (11–2), (9–6), (13–5), (5–1), (14–10)} = 9
Phương án 2:
Sắp xếp kích thước vai áo, vai học sinh theo thứ tự tăng dần và đánh
số lại theo thứ tự, ta có:
Kích thước vai áo có số thứ tự là: V(1,2…8)= { 5, 6, 8, 9, 11, 13, 14, 19}
Kích thước vai học sinh có số thứ tự là: p(1,2..8)= { 1, 2, 3, 4, 5, 6, 10, 15}
Phân phối các áo có kích thước vai V1, V2,...V8 tương ứng với các học
sinh kích thước vai p1, p2,...p8
Khi đó độ lệnh của phương án phân phối là :
d2 = max {|V(i) – p(π i)|, i=1,2,...,8}
d2 = max {(5–1), (6–2), (8–3), (9–4), (11–5), (13–6), (14–10), (19–15)} = 7
Phương án 3 :
Tìm áo có kích thước nhỏ nhất trong dãy V1..V8 = Vmin1= 5
Lê Văn Hợp – Cao học 25B – HTTT


d1 = max {|V(i) – p(π i)|, i=1,2,...,10}
d1 = max {(12–2), (8–5), (10–3), (17–6), (13–11), (27–23), (33–16), (42–
20), (19–9), (22–19)} = 22
Lê Văn Hợp – Cao học 25B – HTTT

6


Phân tích và đánh giá thuật toán
Phương án 2 :
Sắp xếp kích thước vai áo, vai học sinh theo thứ tự tăng dần và đánh
số lại theo thứ tự, ta có:
Kích thước vai áo có số thứ tự là:
V(1,2…10)= {2, 8, 10, 11, 17, 19, 19, 27, 33, 42}
Kích thước vai học sinh có số thứ tự là:
p(1,2..10) = {3, 5, 6, 9, 12, 13, 16, 20, 22, 23}
Phân phối các áo có kích thước vai V1, V2,...V10 tương ứng với các học sinh
kích thước vai p1, p2,...p10
Khi đó độ lệnh của phương án phân phối là:
d2 = max {|V(i) – p(π i)|, i=1,2,...,10}
d2 = max {(3–2), (8–5), (10–6), (11–9), (17–12), (19–13), (19–16), (27–20),
(33–22), (42–23)} = 19
Phương án 3 :
Tìm áo có kích thước nhỏ nhất trong dãy V1..V10 = Vmin1= 2
Tìm học sinh có kích thước vai nhỏ nhất trong dãy p1…p10 = pmin1= 3
Phát áo có kích thước Vmin1 cho học sinh có kích thước vai pmin1
Thực hiện tương tự với các dãy còn lại có kết quả :
Vmin2 = 8 , pmin2= 5
Vmin3 = 10 , pmin3= 6
Vmin4 = 11 , pmin4= 9

THUẬT TOÁN
1. Thuật giải cơ bản
1.1. Ý tưởng
Qua phân tích bài toán và cách xây dựng phương án phân phối áo như ở
trên, ta dự đoán một phương án phân phát áo cho học sinh như sau:
− Ý tưởng 1:

Sắp xếp n học sinh theo thứ tự tăng dần (không giảm) của kích
thước vai, đánh số từ 1 đến n theo thứ tự đó. Tương tự sắp xếp n cái
áo theo thứ tự tăng dần (không giảm) của kích thước vai, đánh số từ
1 đến n theo thứ tự đó.
Lần lượt phát áo cho học sinh theo quy tắc:
- Học sinh thứ 1 được nhận áo thứ 1;
- Học sinh thứ 2 được nhận áo thứ 2;
- ………
- Học sinh thứ n nhận áo thứ n.
Tính độ lệch của phương án.
− Ý tưởng 2 (Thuật toán tham lam)
+ Tìm học sinh có kích thước vai nhỏ nhất trong n học sinh
+ Tìm chiếc áo có kích thước vai nhỏ nhất trong n chiếc áo
+ Phát chiếc áo vừa tìm được cho học sinh vừa tìm được
+ Tìm học sinh có kích thước vai nhỏ nhất trong n-1 học sinh còn lại
Lê Văn Hợp – Cao học 25B – HTTT

8


Phân tích và đánh giá thuật toán
+ Tìm chiếc áo có kích thước vai nhỏ nhất trong n-1 chiếc áo còn lại
+ Phát chiếc áo vừa tìm được cho học sinh vừa tìm được

End;
Proc Adjust( X:mang,i:chi so,n:tri so)
j,flag:interger;
k:gia tri;
Begin
Lê Văn Hợp – Cao học 25B – HTTT

9


Phân tích và đánh giá thuật toán
1.k := X[i];flag := 1; j := 2 * i;
2. while(j = X[j]) then
flag :=0;
else
X[j/2] = X[j];
j := j *2;
end;
3. X[j/2] = k;
End;
proc Build_Initial_Heap( X:mang, n: tri so)
i: interger;
Begin
For i=n/2 down to 0
Adjust(X,i,n-1);
End;

d; V[1],p[1]; V[2],p[2]; …; V[n],p[n];
1.4. Thuật giải bằng lời cho ý tưởng 2:
−
−

Input: Hai dãy số nguyên V1, V2, V3,… Vn; p1, p2, p3,…pn;
Ouput: Độ lệnh cực tiểu d; Phương án phân phối áo V(1),p(1);
V(2),p(2); … V(n),p(n) (kết quả này đã đánh thứ tự lại số thứ tự của học
sinh).
Thuật toán:
1. Bước 1: Tìm áo có kích thước vai áo nhỏ nhất.
2. Bước 2: Tìm học sinh có kích thước vai nhỏ nhất.
3. Bước 3: Tính độ lệch vai áo của cặp áo và kích thước vai tìm

được.
4. Bước 4: Thực hiện tương tự với số áo và học sinh còn lại.
1.5. Thuật giải giả mã cho ý tưởng 2:

* Input: Mảng số nguyên V[1..n],p[1..n] số nguyên n
* Output: Độ lệnh cực tiểu d; Phương án phân phối áo V(1),p(1); V(2),p(2);
…; V(n),p(n) (kết quả này đã đánh thứ tự lại số thứ tự của học sinh).
Proc Greedy(X,Y: mảng,n:chỉ số)
If (n>0) then
1.i=0; j=0; l=0; m=0; d=0;
V=X[0];p=p[0];
Lê Văn Hợp – Cao học 25B – HTTT

11



toàn bộ mỗi dãy con. Khi đó, ta sẽ áp dụng thuật giải HeapSort cho các dãy
con này.
Đối với ý tưởng 2: Thuật toán có thể giải quyết được với số lượng lớn
của bộ dữ liệu đầu vào bằng việc xét từng phần tử. Tuy nhiên thuật toán sẽ
phải trả giá bằng độ phức tạp lớn hơn.
Nhận xét: Qua hai thuật toán xây dựng được thì việc giải quyết bài toán tùy
thuộc vào đặc thù bài toán cụ thể đặt ra, dữ liệu đầu vào ta có thể chọn thuật
Lê Văn Hợp – Cao học 25B – HTTT

12


Phân tích và đánh giá thuật toán
toán cho phù hợp. Xét về độ phức tạp của thuật toán thì thuật toán 1 xây
dựng được có độ phức tạp nhỏ hơn so với thuật toán 2.
3. Chứng minh tính đúng đắn
Sắp xếp tập p và V theo thứ tự tăng dần (không giảm).
Không mất tính tổng quát, giả sử theo thứ tự p(i), V(i), i=1…n là thứ tự sau
khi đã được sắp xếp.
Khi đó, ghép các cặp tương ứng p(i) với V(i) sẽ cho ta lời giải bài toán.
Chứng minh:
3.1. Xét các phương án phân phối áo với n =2 nghĩa là cho áo có kích

thước V(1),V(2) và học sinh có kích thước vai là p(1), p(2) và ta có độ
lệch.
d = max{|V(i)- p(π i)|, i=1,2}.
Ta có các độ lệch vai tương ứng như sau:
d1= max{|V(1)- p(1) |,|V(2)- p(2) |} và d2= Max{|V(2)- p(1) |,|V(1)- p(2) |}
Giả sử p(1) ≤ p(2) và V(1)≤ V(2) thì ta chứng minh được: d 1 ≤ d2 trong mọi
trường hợp.


Ta có |V(1)- p(1)|≤|V(2)- p(1) |  d1 ≤ d2.
− Nếu |V(1) - p(1)|≤|V(2) - p(2)| thì d1 =|V(2)- p(2)|

Ta có |V(2)- p(2)|≤|V(1)- p(2)|  d1 ≤ d2.
Vậy d1 ≤ d2.
TH5: V(1)≤ p(1) ≤ V(2) ≤ p(2)
− Nếu |V(2) - p(2)|≤|V(1)- p(1)| thì d1=|V(1)- p(1)|

Ta có |V(1)- p(1)|≤|V(1)- p(2) |  d1 ≤ d2.
− Nếu |V(1)- p(1) |≤|V(2)- p(2) | thì d1=|V(2)- p(2)|

Ta có |V(2)- p(2)|≤|V(1)- p(2) |  d1 ≤ d2.
TH6: V(1) ≤ V(2)≤ p(1) ≤ p(2)
− Nếu |V(2)- p(2) |≤|V(1)- p(1)| thì d1=|V(1)- p(1)|

Ta có |V(1)- p(1)|≤|V(1)- p(2) |  d1 ≤ d2.
− Nếu |V(1)- p(1)|≤|V(2)- p(2)| thì d1 = |V(2)- p(2)|

Ta có |V(2)- p(2)|≤|V(1)- p(2) |  d1 ≤ d2.
Vậy d1 ≤ d2.
Nhận xét: Như vậy trong tất cả các trường hợp thì ta luôn được d1 ≤ d2.
3.2. Xét các phương án phân phối áo với n nghĩa là cho áo có kích thước

V(1),V(2)…V(n) và học sinh có kích thước vai là p(1), p(2),…,p(n) và
ta có độ lệch.
Gọi độ lệch của phương án sắp xếp hai mảng kích thước áo và kích
thước vai áo là d= max{|V(i)- p(i)|, k=1,n}=|V(k)-p(k)|.Giả sử tồn tại một
phương án phân phối áo khác mà cho ta giá trị d’= max{|V(i)- p(i)|,
k=1,n}=V(j)-p(j) nhỏ hơn d như vậy theo chứng minh trên thì chỉ V(k),V(j)


chỉ bao gồm 3 phép toán: phép so sánh, phép gán và phép trừ. Đó là
các phép so sánh để sắp xếp các dãy số nguyên, tính độ lệch của
phương án sắp xếp.
− Tính khả khi: Các phép toán của thuật toán chỉ sử dụng phép gán,

phép so sánh và phép trừ trên tập số nguyên, đều là những phép toán
thông thường.
− Tính dừng: Dữ liệu vào là dãy số nguyên có kích thước n thì theo cả

thuật toán trình bày ở trên ta luôn đưa ra kết quả.
2. Độ phức tạp thuật toán
Trong thuật giải 1, Thuật toán gồm 2 bước chính là sắp xếp dãy số không
giảm (2 dãy) và so sánh giá trị phần tử thứ k của dãy 1 với phần tử thứ k của
dãy 2 (k =1,2,… n).

Lê Văn Hợp – Cao học 25B – HTTT

15


Phân tích và đánh giá thuật toán
Để giảm độ phức tạp của thuật toán, ta chọn phương pháp sắp xếp vun đống
(Heapsort) với số phép so sánh đối với mỗi dãy là = nlog2n
Ở bước so sánh có n cặp phần tử nên số phép so sánh là n.
Bảng thống kê các phép so sánh của từng dòng lệnh:
Dòng lệnh

Số phép so sánh


Dòng lệnh

Số phép so sánh

Số vòng lặp

Tổng phép so sánh

while số 2

N

N

while số 3

N

N

if số 5

1

1

Số 7

n


Lê Văn Hợp – Cao học 25B – HTTT

17


Phân tích và đánh giá thuật toán
− Chọn chức năng: Nhấn phím 1 để phân phối áo dựa trên 1 file lưu

trữ kích thước vai áo và kích thước vai học sinh có sẵn bằng thuật
toán 1 (*.txt).
− Chọn chức năng:Nhấn phím 2 phân phối áo dựa trên thuật toán 1 cho

bộ dữ liệu ngẫu nhiên với kích thước được nhập từ bàn phím.
− Chọn chức năng:Nhấn phím 3 để phân phối áo dựa trên 1 file lưu trữ

kích thước vai áo và kích thước vai học sinh có sẵn bằng thuật toán 2
(*.txt).
− Chọn chức năng:Nhấn phím 4 phân phối áo dựa trên thuật toán 2 cho

bộ dữ liệu ngẫu nhiên với kích thước được nhập từ bàn phím.
− Chọn chức năng: Nhấn phím 5 để thoát chương trình.

2. Các ví dụ thử nghiệm
Trong các ví dụ thử nghiệm, nếu cho dãy đầu vào là X1, X2, … Xn trong các
file *.txt có cấu trúc sau:
− Dòng đầu tiên: Số phần tử n
− Dòng tiếp theo là các giá trị V[1],p[1] các giá trị cách nhau bởi dấu

cách.
− Các dòng tiếp theo là các giá trị V[i],p[i]; i = 2,3, … n.

Lê Văn Hợp – Cao học 25B – HTTT

20


Phân tích và đánh giá thuật toán
Chọn chức năng: 1

-

File: 100000.txt (Thời gian chạy 46220ms)

Lê Văn Hợp – Cao học 25B – HTTT

21


Phân tích và đánh giá thuật toán

Chọn chức năng: 2

-

Nhập 20 (Thời gian chạy 18ms)

Lê Văn Hợp – Cao học 25B – HTTT

22



25