1. Lý thuyết
Nguyên lý tham lam (Greedy): Lấy tiêu chuẩn tối ưu (trên phạm vi toàn cục) của bài toán để làm tiêu chuẩn chọn lựa hành động cho phạm vi cục bộ của từng bước (hay từng giai đoạn) trong quá trình tìm kiếm lời giải.
Bài toán: Hãy tìm một hành trình cho một người giao hàng đi qua n điểm khác nhau, mỗi
điểm đi qua một lần và trở về điểm xuất phát sao cho tổng chiều dài đoạn đường cần đi là
ngắn nhất. Giả sử rằng có con đường nối trực tiếp từ giữa hai điểm bất kỳ.
Tất nhiên ta có thể giải bài toán này bằng cách liệt kê tất cả con đường có thể đi, tính
chiều dài của mỗi con đường đó rồi tìm con đường có chiều dài ngắn nhất. Tuy nhiên,
cách giải này lại có độ phức tạp 0(n!) (một hành trình là một hoán vị của n điểm, do đó,
tổng số hành trình là số lượng hoán vị của một tập n phần tử là n!). Do đó, khi số đại lý
tăng thì số con đường phải xét sẽ tăng lên rất nhanh.
Một cách giải đơn giản hơn nhiều và thường cho kết quả tương đối tốt là dùng một thuật
giải Heuristic ứng dụng nguyên lý Greedy. Tư tưởng của thuật giải như sau:
Từ điểm khởi đầu, ta liệt kê tất cả quãng đường từ điểm xuất phát cho đến n đại
lý rồi chọn đi theo con đường ngắn nhất.
Khi đã đi đến một đại lý, chọn đi đến đại lý kế tiếp cũng theo nguyên tắc trên.
Nghĩa là liệt kê tất cả con đường từ đại lý ta đang đứng đến những đại lý chưa đi
đến. Chọn con đường ngắn nhất. Lặp lại quá trình này cho đến lúc không còn đại
lý nào để đi.
Bạn có thể quan sát hình sau để thấy được quá trình chọn lựa. Theo nguyên lý Greedy, ta
lấy tiêu chuẩn hành trình ngắn nhất của bài toán làm tiêu chuẩn cho chọn lựa cục bộ. Ta
hy vọng rằng, khi đi trên n đoạn đường ngắn nhất thì cuối cùng ta sẽ có một hành trình
ngắn nhất. Điều này không phải lúc nào cũng đúng. Với điều kiện trong hình tiếp theo thì
thuật giải cho chúng ta một hành trình có chiều dài là 14 trong khi hành trình tối ưu là 13.
Kết quả của thuật giải Heuristic trong trường hợp này chỉ lệch 1 đơn vị so với kết quả tối
ưu. Trong khi đó, độ phức tạp của thuật giải Heuristic này chỉ là 0(n^2 ).
Tất nhiên, thuật giải theo kiểu Heuristic đôi lúc lại đưa ra kết quả không tốt, thậm chí rất tệ
Để hiểu hơn thì các bạn xem slide mình họa
Tại đây2. Demo
bài này viết theo ngôn ngữ C++ , môi trường thực hiện C-Free 4.0 , BOLAND C ++....
các bạn tham khảo
#include<iostream.h>
#include<fstream.h>
#include<stdio.h>
int n,v;
int Cost;
int Tour[20];
int mtTP[20][20];
int Flag[20];
void Input()
{
ifstream f; // tao file
f.open("Input.txt"); // mo file
if(f.bad()) // kiem tra file, neu file chua dc tao
{
printf("\n\t File khong ton tai. \n\n");
}
f>>n>>v;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
{
f>>mtTP[i][j];
}
for(int i=0;i<=n;i++)
Flag[i]=0;
f.close();
}
void Output()
{
ofstream g;
g.open("Output.txt");
g<<"Chi phi cho qua trinh :"<<Cost<<endl;
g<<"Hanh trinh nhu sau :";
for(int i=0;i<n;i++)
g<<Tour[i]<<" -->";
g<<Tour[0]<<endl;
}
// theo thuat giai
void GTS1()
{
int dem=0;
Tour[0]=v;
Flag[v]=1;
int tmp=v;
while(dem!=n-1)
{
int tmpCost=100;
int co;
for(int i=1;i<=n;i++)
{
if(tmpCost>mtTP[v][i] && Flag[i]==0 && mtTP[v][i]!=-1)
{
tmpCost=mtTP[v][i];
co=i;
}
}
dem++;
Tour[dem]=co;
Cost+=tmpCost;
Flag[v]=1;
v=co;
}
Cost+=mtTP[v][tmp];
}
int main()
{
printf("**************** TRI TUE NHAN TAO ******************* \n");
printf("| | \n");
printf("************ KHOA CNTT - DH GTVT TPHCM ************** \n");
printf("| bai toan ung dung giai thuat GTS1 | \n");
printf("***************************************************** \n\n\n\n\n");
Input();
GTS1();
Output();
return 0;
}
các bạn tạo file input.txt và output.txt nhé những bài viết về code của mình chỉ mang ý ngĩa tham khảo. cũng có những bài mình code và có những bài bạn bè học chung mình code
xem tiếp GTS2
