Thuật toán tham lam với ví dụ: Là gì, phương pháp và cách tiếp cận

Thuật toán tham lam là gì?

A Thuật toán tham lam Phân chia tập hợp tài nguyên một cách đệ quy dựa trên mức độ sẵn có tức thời tối đa của tài nguyên đó tại bất kỳ giai đoạn thực thi nào.

Giải quyết vấn đề bằng phương pháp tham lam gồm hai giai đoạn:

1. Quét danh sách các mục
2. Tối ưu hóa

Cả hai giai đoạn đều diễn ra song song khi mảng dữ liệu đầu vào được chia nhỏ dần.

Để áp dụng phương pháp tham lam, việc nắm vững kiến ​​thức về đệ quy và chuyển đổi ngữ cảnh sẽ rất hữu ích. tracMã lệnh. Mô hình tham lam có thể được mô tả bằng một cặp mệnh đề cần và đủ.

Hai điều kiện xác định mô hình tham lam.

• Mỗi bước lựa chọn phải hướng vấn đề đến giải pháp được chấp nhận rộng rãi nhất.
• Cấu trúc bài toán phải dừng lại trong một số bước tham lam hữu hạn.

Sau khi đã nắm vững lý thuyết, chúng ta hãy cùng xem xét lịch sử hình thành của phương pháp tìm kiếm tham lam.

Lịch sử của sự tham lam Algorithms

Dưới đây là những cột mốc quan trọng trong lịch sử của thuật toán tham lam:

• Các thuật toán tham lam lần đầu tiên được hình thành cho các thuật toán duyệt đồ thị vào những năm 1950.
• Edsger Dijkstra đã phát triển thuật toán tìm đường đi ngắn nhất của mình để rút ngắn các tuyến đường xuyên qua thủ đô Amsterdam của Hà Lan.
• Cũng trong thập kỷ đó, Prim và Kruskal đã phát triển các chiến lược tối ưu hóa nhằm giảm thiểu chi phí đường đi dọc theo các tuyến đường có trọng số để xây dựng cây bao trùm tối thiểu.
• Vào những năm 70, các nhà nghiên cứu người Mỹ Cormen, Leiserson, Rivest và Stein đã mô tả cấu trúc con đệ quy của các giải pháp tham lam trong công trình kinh điển của họ. Introduction to Algorithms sách giáo khoa.
• Mô hình tìm kiếm tham lam được ghi nhận là một chiến lược tối ưu hóa riêng biệt trong hồ sơ của NIST vào năm 2005.
• Cho đến ngày nay, các giao thức web như Open Shortest Path First (OSPF) và nhiều giao thức chuyển mạch gói vẫn sử dụng chiến lược tham lam để giảm thiểu thời gian truyền tải trên mạng.

Chiến lược và quyết định tham lam

Logic này được đơn giản hóa thành một lựa chọn nhị phân ở mỗi giai đoạn — "tham lam" hoặc "không tham lam" — dựa trên hướng mà thuật toán lựa chọn để tiến lên.

Ví dụ, thuật toán Dijkstra xác định các máy chủ trên Internet bằng cách đánh giá một hàm chi phí ở mỗi bước. Giá trị mà hàm chi phí trả về sẽ quyết định xem đường dẫn tiếp theo là "tham lam" hay "không tham lam".

Tóm lại, một thuật toán ngừng tham lam khi nó thực hiện một bước không tối ưu cục bộ, và các bài toán tham lam sẽ dừng lại khi không thể thực hiện thêm bất kỳ bước tham lam nào nữa.

Đặc điểm của thuật toán tham lam

Các đặc điểm quan trọng của thuật toán Greedy là:

• Một danh sách các nguồn lực được sắp xếp theo thứ tự sẽ mang theo các thuộc tính về chi phí hoặc giá trị, giúp định lượng các ràng buộc đối với hệ thống.
• Thuật toán này sẽ sử dụng lượng tài nguyên tối đa trong khoảng thời gian bị ràng buộc.
• Ví dụ, trong bài toán lập kế hoạch hoạt động, chi phí nguồn lực được đo bằng giờ và các hoạt động phải được thực hiện theo trình tự.

Tại sao nên sử dụng phương pháp tham lam?

Dưới đây là những lý do nên sử dụng phương pháp tham lam:

• Phương pháp tham lam có những sự đánh đổi khiến nó rất phù hợp với việc tối ưu hóa.
• Lý do rõ ràng nhất là để đưa ra một giải pháp khả thi ngay lập tức. Trong bài toán lựa chọn hoạt động được thảo luận bên dưới, nếu có nhiều hoạt động khác phù hợp trước khi hoạt động hiện tại kết thúc, chúng có thể được lên lịch trong cùng một khoảng thời gian.
• Một lý do khác là phương pháp này chia nhỏ vấn đề một cách đệ quy dựa trên một điều kiện, mà không cần phải hợp nhất các lời giải con.
• Trong bài toán lựa chọn hoạt động, bước phân chia đệ quy được thực hiện bằng cách quét danh sách một lần và chỉ xem xét các hoạt động đủ điều kiện.

Cách giải quyết vấn đề lựa chọn hoạt động

Trong ví dụ lập kế hoạch hoạt động, mỗi hoạt động đều có thời gian bắt đầu và kết thúc, được đánh số để dễ tham khảo. Có hai loại hoạt động:

1. Hoạt động được xem xét: Hoạt động tham chiếu dùng để đánh giá khả năng thực hiện thêm các hoạt động còn lại.
2. Các hoạt động còn lại: hoạt động ở một hoặc nhiều chỉ số trước hoạt động được xem xét.

Chi phí thực hiện một hoạt động chính là thời gian thực hiện hoạt động đó, được tính bằng công thức (thời gian kết thúc – thời gian bắt đầu).

Mức độ tham lam đơn giản là số lượng các hoạt động còn lại có thể được thực hiện trong khoảng thời gian của một hoạt động được xem xét.

Archicấu trúc của Phương pháp Tham lam

Bước 1) Quét danh sách chi phí hoạt động bắt đầu từ chỉ số 0 làm chỉ số cần xem xét.

Bước 2) Khi có nhiều hoạt động khác có thể hoàn thành trước khi hoạt động đang xét kết thúc, hãy tìm kiếm những hoạt động còn lại đó.

Bước 3) Nếu không thể lên lịch thêm hoạt động nào nữa, hoạt động còn lại hiện tại sẽ trở thành hoạt động tiếp theo được xem xét. Lặp lại Bước 1 và Bước 2 với hoạt động mới được xem xét. Nếu không còn hoạt động nào, hãy chuyển sang Bước 4.

Bước 4) Trả về hợp của các chỉ số đã xem xét — đây là các chỉ số hoạt động giúp tối đa hóa thông lượng.

Archicấu trúc của Phương pháp Tham lam

Code Giải thích

#include<iostream>
#include<stdio.h>
#include<stdlib.h>

#define MAX_ACTIVITIES 12

Giải thích mã:

1. Các tệp/lớp tiêu đề được bao gồm
2. Số lượng tối đa các hoạt động mà người dùng có thể cấu hình.

using namespace std;

class TIME
{
    public:
    int hours;

    public: TIME()
    {
   	 hours = 0;
    }
};

Giải thích mã:

1. Khai báo không gian tên chuẩn cho các hoạt động truyền dữ liệu.
2. Một định nghĩa lớp cho TIME
3. Dấu thời gian một giờ.
4. Hàm tạo mặc định TIME
5. Biến giờ.

class Activity
{
    public:
    int index;
    TIME start;
    TIME finish;

    public: Activity()
    {
   	 start = finish = TIME();
    }
};

Giải thích mã:

1. Định nghĩa lớp cho Activity.
2. Các mốc thời gian kết hợp với nhau để xác định một khoảng thời gian.
3. Tất cả các dấu thời gian đều được khởi tạo bằng 0 trong hàm tạo mặc định.

class Scheduler
{
    public:
    int considered_index,init_index;
    Activity *current_activities = new    Activity[MAX_ACTIVITIES];
    Activity *scheduled;

Giải thích mã:

1. Phần 1 của định nghĩa lớp trình lập lịch trình.
2. considered_index là điểm bắt đầu để quét mảng.
3. init_index được sử dụng để gán các dấu thời gian ngẫu nhiên trong quá trình thiết lập.
4. Một mảng các đối tượng Activity được cấp phát động bằng toán tử new.
5. Con trỏ đã lên lịch chứa kết quả tham lam hiện tại.

Scheduler()
{
   	 considered_index = 0;
   	 scheduled = NULL;
...
...

Giải thích mã:

1. Hàm tạo của Scheduler — phần 2 của định nghĩa lớp.
2. considered_index đánh dấu điểm bắt đầu của quá trình quét hiện tại.
3. Phạm vi tham lam ban đầu chưa được xác định.

for(init_index = 0; init_index < MAX_ACTIVITIES; init_index++)
 {
   		 current_activities[init_index].start.hours =
   			 rand() % 12;

   		 current_activities[init_index].finish.hours =
   			 current_activities[init_index].start.hours +
   				 (rand() % 2);

   		 printf("\nSTART:%d END %d\n",
   		 current_activities[init_index].start.hours
   		 ,current_activities[init_index].finish.hours);
 }
&#8230;
&#8230;

Giải thích mã:

1. Vòng lặp for khởi tạo thời gian bắt đầu và kết thúc cho mỗi hoạt động đã lên lịch.
2. Khởi tạo thời gian bắt đầu.
3. Khởi tạo thời gian kết thúc trùng với hoặc sau giờ bắt đầu.
4. Lệnh gỡ lỗi sẽ in ra thời lượng đã được cấp phát.

	public:
   		 Activity * activity_select(int);
};

Giải thích mã:

1. Phần 4 — phần cuối cùng của định nghĩa lớp Scheduler.
2. Hàm activity_select() lấy chỉ số bắt đầu làm cơ sở và chia nhiệm vụ tham lam thành các bài toán con.

Activity * Scheduler :: activity_select(int considered_index)
{
    this->considered_index = considered_index;
    int greedy_extent = this->considered_index + 1;
…
…

1. Toán tử phân giải phạm vi (::) liên kết định nghĩa hàm với lớp Scheduler.
2. considered_index được truyền theo giá trị, và greedy_extent được khởi tạo bằng chỉ số ngay sau đó.

Activity * Scheduler :: activity_select(int considered_index)
{
    	while( (greedy_extent < MAX_ACTIVITIES ) &&
   	 ((this->current_activities[greedy_extent]).start.hours <
   		 (this->current_activities[considered_index]).finish.hours ))
    	{
   	 printf("\nSchedule start:%d \nfinish%d\n activity:%d\n",
   	 (this->current_activities[greedy_extent]).start.hours,
   	 (this->current_activities[greedy_extent]).finish.hours,
   	 greedy_extent + 1);
   	 greedy_extent++;
    	}
&#8230;
...

Giải thích mã:

1. Nguyên tắc cốt lõi là phạm vi tham lam được giới hạn ở mức MAX_ACTIVITIES.
2. Giờ bắt đầu của hoạt động hiện tại được so sánh với giờ kết thúc của hoạt động đang xét.
3. Trong khi điều kiện vẫn còn, một câu lệnh gỡ lỗi tùy chọn sẽ được in ra.
4. Sau đó, thuật toán tham lam sẽ chuyển sang chỉ mục tiếp theo trong mảng hoạt động.

...
if ( greedy_extent <= MAX_ACTIVITIES )
    {

   	 return activity_select(greedy_extent);
    }
    else
    {
   	 return NULL;
    }
}

Giải thích mã:

1. Điều kiện kiểm tra xem tất cả các hoạt động đã được thực hiện hay chưa.
2. Nếu không, thuật toán sẽ khởi động lại quá trình tìm kiếm tham lam từ chỉ số hiện tại — một bước đệ quy chia nhỏ vấn đề một cách tham lam.
3. Nếu câu trả lời là có, quyền điều khiển sẽ trở lại cho bên gọi mà không có khả năng mở rộng tham lam.

int main()
{
    Scheduler *activity_sched = new Scheduler();
    activity_sched->scheduled = activity_sched->activity_select(
   				activity_sched->considered_index);
    return 0;
}

Giải thích mã:

1. Hàm chính gọi bộ lập lịch.
2. Một đối tượng Scheduler mới được khởi tạo.
3. Hàm activity_select() trả về một con trỏ Activity cho người gọi sau khi nhiệm vụ tham lam kết thúc.

Đầu ra:

START:7 END 7

START:9 END 10

START:5 END 6

START:10 END 10

START:9 END 10

Schedule start:5
finish6
 activity:3

Schedule start:9
finish10
 activity:5

Hạn chế của kỹ thuật tham lam

Phương pháp tham lam không phù hợp với các bài toán yêu cầu giải pháp tối ưu cho mọi bài toán con, chẳng hạn như bài toán sắp xếp.

Trong những trường hợp như vậy, phương pháp tham lam có thể sai — trong trường hợp xấu nhất, nó tạo ra một giải pháp không tối ưu.

Nhược điểm cốt lõi của các thuật toán tham lam là chúng lựa chọn mà không biết điều gì sẽ xảy ra tiếp theo sau trạng thái tham lam hiện tại.

Sơ đồ dưới đây minh họa nhược điểm này của phương pháp tham lam.

Trong thuật toán quét tham lam được thể hiện dưới dạng cây (giá trị càng cao nghĩa là mức độ tham lam càng lớn), một thuật toán ở giá trị 40 sẽ chọn số 29 tiếp theo, sau đó kết thúc ở số 12, tổng cộng là 41.

Ngược lại, chiến lược chia để trị sẽ theo sau 25 với 40, tổng cộng là 65, cao hơn 24 điểm so với lựa chọn tham lam cục bộ.

Ví dụ về tham lam Algorithms

Hầu hết các thuật toán mạng đều dựa trên phương pháp tham lam. Một số ví dụ phổ biến về thuật toán tham lam bao gồm:

• Thuật toán cây bao trùm tối thiểu của Prim
• Bài toán người bán hàng rong (xấp xỉ)
• Tô màu bản đồ đồ thị
• Thuật toán cây bao trùm tối thiểu Kruskal
• Thuật toán đường đi ngắn nhất của Dijkstra
• Phủ đỉnh đồ thị
• Vấn đề về Knapsack
• Sắp xếp thứ tự công việc theo thời hạn

Câu Hỏi Thường Gặp