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ì?

In Thuật toán tham lam một tập hợp các tài nguyên được phân chia đệ quy dựa trên mức độ sẵn có tối đa, ngay lập tức của tài nguyên đó ở bất kỳ giai đoạn thực thi nhất định nào.

Để giải quyết vấn đề dựa trên cách tiếp cận tham lam, có hai giai đoạn

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

Các giai đoạn này được trình bày song song trong hướng dẫn thuật toán Tham lam này, trong quá trình phân chia mảng.

Để hiểu cách tiếp cận tham lam, bạn cần phải có kiến thức thực tế về đệ quy và chuyển đổi ngữ cảnh. Điều này giúp bạn hiểu cách theo dõi mã. Bạn có thể định nghĩa mô hình tham lam dựa trên những tuyên bố cần và đủ của riêng bạn.

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

Mỗi giải pháp từng bước phải xây dựng vấn đề theo hướng giải pháp được chấp nhận tốt nhất.
Sẽ là đủ nếu cấu trúc của bài toán có thể dừng lại ở một số hữu hạn các bước tham lam.

Tiếp tục lý thuyết hóa, chúng ta hãy mô tả lịch sử gắn liền với phương pháp tìm kiếm Tham lam.

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

Đây là một mốc quan trọng của thuật toán tham lam:

Thuật toán tham lam đã được khái niệm hóa cho nhiều thuật toán đồ thị đi bộ vào những năm 1950.
Esdger Djikstra đã khái niệm hóa thuật toán để tạo ra các cây bao trùm tối thiểu. Ông nhằm mục đích rút ngắn khoảng cách của các tuyến đường trong thủ đô Amsterdam của Hà Lan.
Trong cùng thập kỷ đó, Prim và Kruskal đã đạt được các chiến lược tối ưu hóa dựa trên việc giảm thiểu chi phí đường đi dọc theo các tuyến đường có cân nặng.
Vào những năm 70, các nhà nghiên cứu người Mỹ, Cormen, Rivest và Stein đã đề xuất một cấu trúc đệ quy của các giải pháp tham lam trong cuốn sách giới thiệu cổ điển về thuật toán của họ.
Mô hình tìm kiếm tham lam đã được đăng ký như một loại chiến lược tối ưu hóa khác trong hồ sơ NIST vào năm 2005.
Cho đến nay, các giao thức chạy web, chẳng hạn như open-shortest-path-first (OSPF) và nhiều giao thức chuyển mạch gói mạng khác sử dụng chiến lược tham lam để giảm thiểu thời gian sử dụng mạng.

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

Logic ở dạng đơn giản nhất được rút gọn thành “tham lam” hoặc “không tham lam”. Những tuyên bố này được xác định bằng cách tiếp cận được thực hiện để nâng cao trong từng giai đoạn thuật toán.

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

Nói tóm lại, một thuật toán không còn tham lam nếu ở bất kỳ giai đoạn nào nó thực hiện một bước không tham lam cục bộ. Các vấn đề tham lam dừng lại khi lòng tham không còn phạm vi 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à:

Có một danh sách các tài nguyên được sắp xếp theo thứ tự, kèm theo các phân bổ chi phí hoặc giá trị. Những hạn chế này định lượng trên một hệ thống.
Bạn sẽ lấy số lượng tài nguyên tối đa trong thời gian áp dụng hạn chế.
Ví dụ, trong bài toán lập kế hoạch hoạt động, chi phí tài nguyên được tính bằng giờ và các hoạt động cần được thực hiện theo thứ tự nối tiếp.

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:

Cách tiếp cận tham lam có một vài sự đánh đổi, điều này có thể khiến nó phù hợp để tối ưu hóa.
Một lý do nổi bật là để đạt được giải pháp khả thi nhất ngay lập tức. Trong bài toán lựa chọn hoạt động (Giải thích bên dưới), nếu có thể thực hiện nhiều hoạt động hơn trước khi kết thúc hoạt động hiện tại thì các hoạt động này có thể được thực hiện trong cùng một thời gian.
Một lý do khác là chia bài toán theo cách đệ quy dựa trên một điều kiện, không cần kết hợp tất cả các lời giải.
Trong bài toán lựa chọn hoạt động, bước “phân chia đệ quy” đạt được bằng cách quét danh sách các mục chỉ một lần và xem xét các hoạt động nhất định.

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

Trong ví dụ về lập kế hoạch hoạt động, có thời gian “bắt đầu” và “kết thúc” cho mọi hoạt động. Mỗi Hoạt động được lập chỉ mục bằng một số để tham khảo. Có hai loại hoạt động.

hoạt động được coi là: là Hoạt động, là tham chiếu để phân tích khả năng thực hiện nhiều Hoạt động còn lại.
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.

Tổng thời lượng cho biết chi phí thực hiện hoạt động. Nghĩa là (kết thúc - bắt đầu) mang lại cho chúng ta thời lượng như chi phí của một hoạt động.

Bạn sẽ biết rằng mức độ tham lam là số hoạt động còn lại mà bạn có thể thực hiện trong thời gian của một hoạt động đang được cân nhắc.

Archicấu trúc của cách tiếp cận Tham lam

BƯỚC 1) Quét danh sách chi phí hoạt động, bắt đầu bằng chỉ số 0 làm Chỉ số được xem xét.

BƯỚC 2) Khi có thể hoàn thành nhiều hoạt động hơn vào thời điểm hoạt động đang xem xét kết thúc, hãy bắt đầu tìm kiếm một hoặc nhiều hoạt động còn lại.

BƯỚC 3) Nếu không còn hoạt động nào nữa thì hoạt động còn lại hiện tại sẽ trở thành hoạt động được xem xét tiếp theo. 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ề sự kết hợp của các chỉ số được xem xét. Đây là những chỉ số hoạt động sẽ được sử dụng để tối đa hóa thông lượng.

Giải thích mã

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

#define MAX_ACTIVITIES 12

Giải thích mã:

Các tệp/lớp tiêu đề được bao gồm
Số lượng hoạt động tối đa do người dùng cung cấp.

using namespace std;

class TIME
{
    public:
    int hours;

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

Giải thích mã:

Không gian tên cho các hoạt động phát trực tuyến.
Một định nghĩa lớp cho TIME
Dấu thời gian một giờ.
Hàm tạo mặc định TIME
Biến giờ.

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

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

Giải thích mã:

Một định nghĩa lớp từ hoạt động
Dấu thời gian xác định thời lượng
Tất cả các dấu thời gian được khởi tạo thành 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ã:

Phần 1 của định nghĩa lớp trình lập lịch trình.
Chỉ mục được coi là điểm khởi đầu để quét mảng.
Chỉ số khởi tạo được sử dụng để gán dấu thời gian ngẫu nhiên.
Một mảng đối tượng hoạt động được phân bổ động bằng toán tử mới.
Con trỏ được lập lịch xác định vị trí cơ sở hiện tại cho tham lam.

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

Giải thích mã:

Hàm tạo bộ lập lịch - phần 2 của định nghĩa lớp bộ lập lịch.
Chỉ mục được xem xét xác định thời điểm bắt đầu hiện tại của quá trình quét hiện tại.
Mức độ tham lam hiện tại không được xác định khi bắt đầu.

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);
 }
…
…

Giải thích mã:

Vòng lặp for để khởi tạo giờ bắt đầu và giờ kết thúc của từng hoạt động hiện đã được lên lịch.
Khởi tạo thời gian bắt đầu.
Việc khởi tạo thời gian kết thúc luôn sau hoặc chính xác vào giờ bắt đầu.
Một câu lệnh gỡ lỗi để in ra khoảng thời gian được phân bổ.

	public:
   		 Activity * activity_select(int);
};

Giải thích mã:

Phần 4 – phần cuối cùng của định nghĩa lớp trình lập lịch trình.
Hàm chọn hoạt động lấy chỉ số điểm bắt đầu làm cơ sở và chia nhiệm vụ tham lam thành các bài toán con tham lam.

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

Sử dụng toán tử phân giải phạm vi (::), định nghĩa hàm sẽ được cung cấp.
Chỉ số được xem xét là Chỉ mục được gọi theo giá trị. tham lam_extent chỉ là một chỉ mục được khởi tạo sau Chỉ mục được xem xét.

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++;
    	}
…
...

Giải thích mã:

Logic cốt lõi- Mức độ tham lam được giới hạn ở số lượng hoạt động.
Giờ bắt đầu của Hoạt động hiện tại được kiểm tra là có thể lên lịch trước khi Hoạt động được xem xét (được đưa ra bởi chỉ mục được xem xét) kết thúc.
Miễn là điều này có thể, một câu lệnh gỡ lỗi tùy chọn sẽ được in.
Chuyển tới chỉ mục tiếp theo trên mảng hoạt động

...
if ( greedy_extent <= MAX_ACTIVITIES )
    {

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

Giải thích mã:

Việc kiểm tra có điều kiện nếu tất cả các hoạt động đã được thực hiện.
Nếu không, bạn có thể khởi động lại sự tham lam của mình với Chỉ số được coi là điểm hiện tại. Đây là một bước đệ quy nhằm phân chia câu lệnh vấn đề một cách tham lam.
Nếu có, nó sẽ trả về người gọi mà không có phạm vi để mở rộng lòng tham.

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ã:

Chức năng chính được sử dụng để gọi bộ lập lịch.
Trình lập lịch biểu mới được khởi tạo.
Hàm chọn hoạt động trả về một con trỏ thuộc loại hoạt động sẽ quay lại 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

Nó không phù hợp với các bài toán Tham lam trong đó cần có giải pháp cho mọi bài toán con như sắp xếp.

Trong các bài toán thực hành thuật toán Greedy như vậy, phương pháp Greedy có thể sai; trong trường hợp xấu nhất thậm chí dẫn đến lời giải không tối ưu.

Do đó, nhược điểm của thuật toán tham lam là không biết điều gì sẽ xảy ra trước trạng thái tham lam hiện tại.

Dưới đây là mô tả về nhược điểm của phương pháp Tham lam:

Trong quá trình quét tham lam được hiển thị ở đây dưới dạng cây (giá trị tham lam càng cao), trạng thái thuật toán ở giá trị: 40, có thể lấy 29 làm giá trị tiếp theo. Hơn nữa, nhiệm vụ của nó kết thúc ở con số 12. Con số này có giá trị là 41.

Tuy nhiên, nếu thuật toán đi theo con đường dưới mức tối ưu hoặc áp dụng chiến lược chinh phục. sau đó 25 sẽ là 40, và mức cải thiện chi phí tổng thể sẽ là 65, được đánh giá cao hơn 24 điểm khi là một quyết định dưới mức tối ưu.

Ví dụ về tham lam Algorithms

Hầu hết các thuật toán mạng đều sử dụng cách tiếp cận tham lam. Dưới đây là danh sách một số ví dụ về thuật toán Greedy:

Thuật toán cây khung tối thiểu của Prim
Vấn đề nhân viên bán hàng đi du lịch
Đồ thị – Tô màu bản đồ
Thuật toán cây bao trùm tối thiểu của Kruskal
Thuật toán cây bao trùm tối thiểu của Dijkstra
Đồ thị – Vertex Cover
Vấn đề về Knapsack
Vấn đề lập kế hoạch công việc

Tổng kết

Tóm lại, bài viết đã định nghĩa mô hình tham lam, chỉ ra cách tối ưu hóa và đệ quy tham lam có thể giúp bạn có được giải pháp tốt nhất cho đến một thời điểm. Thuật toán Greedy được đưa vào ứng dụng rộng rãi để giải bài toán bằng nhiều ngôn ngữ như thuật toán Greedy Python, C, C#, PHP, Java, v.v. Việc lựa chọn hoạt động của ví dụ thuật toán Tham lam được mô tả là một vấn đề chiến lược có thể đạt được thông lượng tối đa bằng cách sử dụng phương pháp tham lam. Cuối cùng, những nhược điểm của việc sử dụng phương pháp tham lam đã được giải thích.

Bạn có thể thích:

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

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

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

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

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

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

NHỮNG BÀI VIẾT LIÊN QUAN

Archicấu trúc của cách tiếp cận Tham lam

Giải thích mã

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

Ví dụ về tham lam Algorithms

Tổng kết