Bài toán tối ưu và Thuật toán tham lam
Trịnh Thanh Hải
Các dạng tìm phương án tối ưu như bài toán người du lịch, bài toán cái túi, bài toán cho thuê máy, bài toán phân công, bài toán lập lịch, v.v.. từ lâu đã trở nên quen thuộc và hấp dẫn đối với các bạn say mê bộ môn tin học. Chúng thuộc lớp các bài toán tối ưu tổ hợp là một trường hợp riêng của bài toán tối ưu. Các bài toán tối ưu tổ hợp có rất nhiều ứng dụng trong thực tiễn và việc ứng dụng chúng trở nên tuyệt vời hơn rất nhiều khi người ta nghiên cứu các thuật toán tối ưu và cài đặt trên máy tính điện tử. Một trong những thuật toán để giải quyết các bài toán trên là thuật toán tham lam.
1. Dạng tổng quát của bài toán tối ưu tổ hợp:
.
Cho phiếm hàm f(x) xác định trên một tập hữu hạn các phần tử D. Hãy tìm min (f), max(f)..
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 cộuht D gọi là một phương án. Tập D gọi là tập các phương án của bài toán.2. Thuật toán tham lam : Thuật toán tham lam được thiết kế dựa trên nguyên lý tham lam. Ta lấy tiêu chuẩn tối ưu của toàn bộ bài toán làm tiêu chuẩn để làm căn cứ cho việc xác định hành động trong phạm vi bộ phận của từng giai đoạn từ đó xác lập hàm lựa chọn. Các kết quả có được do thực hiện hàm chọn được lưu trữ trong tập kết quả. Ban đầu tập kết quả là tập trống. Tại mỗi bước hàm chọn sẽ chọn ra một phần tử "tốt nhất" trong các phần tử còn lại của D để đưa vào tập kết quả.
Phần tử được chọn sẽ được đưa ra khỏi tập D. Sau khi bổ xung thêm phần tử được chọn vào tập kết quả mà tập kết quả vẫn còn thoả mãn các điều kiện của bài toán thì ta tiếp tục mở rộng tập kết quả bằng cách tiếp tục bổ xung vào các phần tử được chọn.
Procedure Greedy Begin
Result := f While D <> f Do Begin
Chọn (x);
D:= D - [x];
if Result U [x] thoả mãn điều kiện Then Result := Result U [x]
end;
end;
3. Minh hoạ việc giải các bài toán bằng thuật toán tham lam
a, Bài toán người du lịch:
Có n thành phố được đánh số theo thứ tự từ 1 đến n. Người du lịch xuất phát từ một thành phố và ghé thăm các thành phố còn lại, mỗi thành phố thăm duy nhất một lần sau đó trở về nơi xuất phát.
Cho biết C(TPi,-TPj) là chi phí đi từ thành phố i tới thành phố j. Giả thiết C(TPi,-TPj) >0 với mọi i ≠ j, C(TPi,- TPi) =
¥
, có thể C(TPi,-TPj) ≠ C(TPi,-TPj). Hãy xác định chu trình đi sao cho tổng chi phí là nhỏ nhất.Không mất tính tổng quát ta giả sử người du lịch xuất phát từ thành phố 1. Mỗi chu trình TP1, TPi2, TPi3,..,TPin, TP1 có thể đặt tương ứng 1 - 1 với một hoán vị (i2,i3,...in) của 2, 3, ...n. Gọi C(ik-il) là chi phí đi từ thành phố ik đến thành phố il. Khi đó chi phí của một chu trình là tổng các chi phí từng
chặng:
Đặt f(x) = C(1-i1) + C(i1-i2)+....+C(in-1- in)+C(in- 1) Ký hiệu D là tập tất cả các hoán vị của n-1 số 2, 3, ...n, có thể phát biểu bài toán người du lịch dưới
dạng sau:
{f(x) -> min; x uhtộc D}
Giải quyết bài toán người du lịch bằng thuật toán tham lam, ta có thủ tục:
Procedure Dulich CTrinh:= f;
Chiphi:=0;
vitri:=1; { xuất phát từ thành phố 1}
For k:=1 to n-1 Do Begin
{Chọn thành phố X chưa tới sao cho chi phí C(vitri-X) nhỏ nhất; } Ctrinh:=Ctrinh+(vitri,X);
Chiphi:=Chiphi+C(vitri-X); vitri:=X;
end;
{Trở về nới xuất phát}
Ctrinh:=Ctrinh+(vitri,1);
Chiphi:=Chiphi+C(vitri-1);
end;
Ví dụ minh hoạ: Giải bài toán người du lịch với ma trận cước phí không đối xứng như sau:
Bước 1:Từ thành phố 1 ta chọn đích là thành phố 5 (chi phí=31 là thấp nhất.) Bước 2: Từ thành phố 5 ta chọn thành phố tiếp là 3 ( chi phí = 7 thấp nhất).
Bước 3:Từ thành phố 3 ta đi tiếp đến thành phố 4 (chi phí = 4 thấp nhất) Bước 4: Từ thành phố 4 ta đến thành phố 2 là thành phố cuối chưa đi đến Bước 5: Từ thành phố 2 ta quay về thành phố 1.
Vậy tổng chi phí sẽ là: 31+7+4+3+19+20 = 81.
b,Ví dụ bài toán cái túi:
Một nhà thám hiểm muốn chọn đem theo trong một cái túi có trọng lượng không vượt quá b một số vật trong n đồ vật khác nhau. Đồ vật thứ i có trọng lượng ai và có giá trị sử dụng là ci. Hãy tìm phương án lựa chọn những đồ vật mang theo sao cho tổng giá trị sử dụng là lớn nhất mà không vượt quá sức chứa của chiếc túi.
Nếu ta đặt xi = 1 nếu đồ vật i được chọn
xi = 0 nếu đồ vật i không được chọn Bài toán trên có phát biểu như sau:
{ f(x) = c1x1+c2x2+... + cnxn -->Max Điều kiện: a1x1+a2x2+... +anxn < b
xi cộuht {0,1} i=1..n }
Để thực hiện chiến lược tham lam trước tiên ta đánh số lại các đồ vật sao cho giá trị sử dụng trên một đơn vị (ci/ai) là giảm dần. Ta sẽ duyệt từ những đồ vật có giá trị đơn vị từ lớn đến bé.
Gọi Tl: tổng trọng lượng mà túi còn có thể chứa được Tgt: tổng giá trị tương ứng với những đồ vật đã chọn Procedute xeptui
Begin i:=1;
Tgt:=0;
Tl:=b;
While (i<=n) Do Begin
if ai <= Tl Then Begin
Tgt:=Tgt+ci;
Tl:=Tl -ai;
end;
inc(i);
end;
End;
Ví dụ có 4 đồ vật có trọng lượng lần lượt là: a1=4, a2=3, a3=2, a4=1 có giá trị sử dụng lần lượt là:
c1=8, c2=5, c3=3, c4=1. Hãy lựa chọn phương án để xếp vào một chiếc túi có sức chứa bằng 8 sao
cho giá trị sử dụng là lớn nhất?
Ta có 4 đồ vật đã được đánh só từ 1 đến 4 theo trình tự giảm dần của giá trị sử dụng trên một đơn vị trọng lượng. Gọi xi là phương án lựa chọn đồ vật thứ i, Từ giả thiết ta có bài toán:
f(x) = 8x1 + 5x2 + 3x3 + x4 ---> Max Điều kiện: 4x1 + 3x2 + 2x3 + x4 < 8
xi cộuht {0,1} i=1,2,3,4 Áp dụng thuật toán tham lam ta có:
Ban đầu: i=1, TL = 8; Tgt :=0
Thứ tự Sức chứa của túi Khối lượng vật Xét điều kiện xi
i =1 8 a1=4 4 < = 8 : đúng 1
i =2 4 a2=3 3<=4 : đúng 1
i =3 1 a3=2 2 <=1 : sai 0
i =4 1 a4=1 1<=1 : đúng 1
Vậy giá trị tối ưu lựa chọn được là : Tgt = 8+5+1 = 14 với phương án x=(1,1,0,1)
Với thuật toán tham ăn nếu ta xây dựng được một hàm chọn thích hợp thì sẽ được phương án tối ưu. Trong một số trường hợp ta chỉ tìm được phương án "tốt" gần đúng với phương án tối ưu. Điều đáng lưu tâm ở đây là một số bài toán tối ưu tổ hợp có thuật toán tìm nghiệm chính xác đòi hỏi thời gian mũ, khi cỡ bài toán lớn thì rất khó áp dụng. Trong trường hợp này ta sử dụng thuật toán tham lam cho nghiệm "tốt" gần với nghiệm tối ưu mà thời gian thực hiện rất nhanh đây cũng chính là lý do tại sao thuật toán tham lam lại được mọi người quan tâm.
