DANH SÁCH BÀI VIẾT Tìm hiểu thuật toán Quy hoạch động Tìm hiểu về Hàm đệ quy Thuật toán tìm kiếm nhị Tìm hiểu về Thuật toán quay lui (Backtracking) Tìm hiểu thuật toán Loang Tìm hiểu thuật toán chia để trị Tìm hiểu thuật toán tham lam trong lập trình Giải thuật tìm kiếm theo chiều sâu DFS (Depth First Search) Giải thuật tìm kiếm theo chiều rộng BFS (Breadth-first search) Tìm hiểu về thuật toán Sàng nguyên tố (sàng Eratosthenes)
Trong bài viết này chúng ta sẽ tìm hiểu về thuật toán tham lam.
Giải thuật tham lam
Giải thuật tham lam là giải thuật tối ưu hóa tổ hợp. Giải thuật tìm kiếm, lựa chọn giải pháp tối ưu tại thời điểm hiện tại từ đó nhằm đưa ra kết quả tối ưu cuối cùng cho bài toán.
Tham lam không dựa vào quyết định của bài toán trước đó để đưa ra quyết định mà tại mỗi bước nó tự ra quyết định tối ưu cục bộ và quyết định này sẽ quyết định đường đi của mọi bước tiếp theo, quyết định này cũng không thể quay lại hay phục hồi.
Vì giải thuật tham lam mỗi bước đi sẽ tự quyết định cách đi tối ưu nhất, vì thế giải thuật tham lam không đi qua hết tất cả các trường hợp đáp án có thể sảy ra. Chính vì vậy trong nhiều bài toán tham lam có thể không cho kết quả chính xác nhất nhất.
Ưu điểm của tham lam
- Thuật toán tham lam dễ dàng tiếp cận với các bài toán đặc biệt là các bài toán đồ thị.
- Độ phức tạp của tham lam là khá rõ ràng từ đó bạn có thể xem xét độ phù hợp của tham lam đối với thời gian chạy của bài toán cần giải quyết.
- Nếu có thể chứng minh rằng một thuật toán tham lam cho ra kết quả tối ưu toàn cục cho một lớp bài toán nào đó, thì thuật toán thường sẽ trở thành phương pháp được chọn lựa, vì nó chạy nhanh hơn các phương pháp giải thuật tối ưu hóa khác.
Nhược điểm
- Rất khó để hiểu hay chứng minh 1 lời giải tham lam là kết quả tối ưu ngay kể cả khi nó đưa ra lời giải tối ưu
- Rất nhiều bài toán các thuật toán tham lam đưa ra kết quả không được chính xác.
Bài toán minh họa tham lam
Một ví dụ về tham lam là bài toán xếp ba lô:
Một kẻ tham lam với một chiếc ba lô kích thước chứa tối đa là M, và có n vật phẩm. Mỗi một vật sẽ có kích thước là A[i] và có giá trị B[i]……Tìm giá trị lớn nhất mà kẻ đó có thể nhét vào balo với tổng kích thước các vật không vượt quá M.
Ví dụ: Balo anh ta chứa được 3kg, và có 3 vật phẩm lần lượt là [1,2], [2,2], [3,2] (Số thứ nhất là khối lượng của vật, số thứ 2 là giá trị vật phầm). Vì balo anh ta chỉ chứa được 3kg vậy anh ta chỉ có thể chọn chứa vật thứ 1 + vật thứ 2 sẽ có tổng kích thước là 3kg, và nếu anh ta chọn vật phẩm thứ ba thì vật phẩm 3 có kích thước là 3Kg. Vì vậy kẻ tham lam này sẽ chọn vật phẩm thứ 1 và thứ 2 vì tổng giá trị sẽ là 4, vật phẩm 3 chỉ có giá trị là 2.
Viết chương trình C bài toán balo như sau:
#include<stdio.h>
#include<conio.h>
template <class T>
void swap(T &a,T &b)
{
T t=a;a=b;b=t;
}
void sx(int n,int *a,int *b,int *&id)
{
int i,j;
id=new int[n+1];
float *t=new float[n+1];
for(i=1;i<=n;i++)
{
id[i]=i;
t[i]=(float)b[i]/a[i];
}
for(i=1;i<=n;i++)
for(j=i+1;j<=n;j++)
if(t[i]<t[j])
{
swap(a[i],a[j]);
swap(id[i],id[j]);
swap(b[i],b[j]);
swap(t[i],t[j]);
}
}
void balo(int n,int *a,int *b,int M)
{
int i,*id;
int tkt=0,tgt=0;
sx(n,a,b,id);
for(i=1;i<=n;i++)
if(tkt+a[i]<=M)
{
tgt+=b[i];
tkt+=a[i];
}
printf("\nTong kich thuoc la %d",tkt);
printf("\nTong gia tri lon nhat la %d",tgt);
delete id;
}
int main()
{
int n,m,*a,*b;
printf("Nhap so do vat n = ");
scanf("%d",&n);
printf("Nhap kich thuoc ba lo M = ");
scanf("%d",&m);
a=new int [n+1];
b=new int [n+1];
for(int i=1;i<=n;i++)
{
printf("Do vat 1",i);
printf("\n Kich thuoc:",i);
scanf("%d",&a[i]);
printf(" Gia tri:", i);
scanf("%d",&b[i]);
printf("\n\n");
}
balo(n,a,b,m);
return 0;
}
Cảm ơn bạn đã đọc bài viết chúc bạn học tốt!
[Xem tất cả bài viết chủ đề C/C++ tại đây]
