Bài toán tối ưu và thuật toán tham lam

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 ((((( 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 := (
While D <> ( 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 ((((( 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:=
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à