Thứ Tư, 30 Tháng Mười Một 2022
Trang chủLập trìnhCTDL & Thuật toánTìm hiểu thuật toán tham lam trong lập trình

Tìm hiểu thuật toán tham lam trong lập trình

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]

0 0 Phiếu bình chọn
Xếp hạng bài viết
BÀI VIẾT LIÊN QUAN
Đăng ký nhận thông báo
Thông báo email khi
guest
0 Bình luận
Không thể gửi email
Phản hồi nội tuyến

NÊN ĐỌC THÊM

Bạn muốn tìm kiếm gì?


0
Giáo sư! có thể ném gạch bên dưới nhé!x
()
x