Thuật toán tham lam là gì?
Trong Thuật toán tham lam, một tập hợp các tài nguyên được phân chia một cách đệ quy dựa trên mức độ sẵn có tối đa, tức thời của tài nguyên đó ở bất kỳ giai đoạn thực thi nào.
Để giải quyết mộ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 đề cập 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 sẽ cần phải có kiến thức làm việc 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ể xác định mô hình tham lam theo các 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 cấu trúc một vấn đề theo hướng giải quyết được chấp nhận tốt nhất của nó.
- Nó là đủ nếu cấu trúc của vấn đề có thể dừng lại trong một số lượng hữu hạn các bước tham lam.
Với việc tiếp tục lý thuyết, chúng ta hãy mô tả lịch sử liên quan đến phương pháp tìm kiếm Tham lam.
Trong hướng dẫn thuật toán Tham lam này, bạn sẽ học:
- Lịch sử của các thuật toán tham lam
- Các chiến lược và quyết định tham lam
- Đặc điểm của phương pháp tiếp cận tham lam
- Tại sao sử dụng Phương pháp tiếp cận Tham lam?
- Cách giải quyết vấn đề lựa chọn hoạt động
- Kiến trúc của cách tiếp cận Tham lam
- Nhược điểm của thuật toán tham lam
Lịch sử của các thuật toán tham lam
Đây là một mốc quan trọng của các thuật toán tham lam:
- Các thuật toán tham lam đã được hình thành cho nhiều thuật toán đi bộ đồ thị vào những năm 1950.
- Esdger Djikstra đã hình thành thuật toán để tạo ra cây khung tối thiểu. Ông nhắm đến việc 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 một 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 nhắc.
- 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 con đệ 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 ngày nay, các giao thức chạy web, chẳng hạn như đường dẫn mở đầu tiên (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 dành cho mạng.
Các chiến lược và quyết định tham lam
Logic ở dạng đơn giản nhất của nó đã bị biến thành "tham lam" hoặc "không tham lam". Các câu lệnh này được xác định theo cách tiếp cận được thực hiện để nâng cao trong mỗi 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 các máy chủ lưu trữ trên Internet bằng cách tính toán một hàm chi phí. Giá trị được trả về bởi hàm chi phí xác định xem đườ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ộ. Vấn đề tham lam dừng lại mà không còn phạm vi tham lam nào nữa.
Đặc điểm của phương pháp tiếp cận tham lam
Các đặc điểm quan trọng của thuật toán phương pháp Tham lam là:
- Có một danh sách có thứ tự các nguồn lực, với chi phí hoặc giá trị phân bổ. Những ràng buộc định lượng này trên một hệ thống.
- Bạn sẽ sử dụng số lượng tài nguyên tối đa trong thời gian áp dụng ràng buộc.
- Ví dụ, trong bài toán lập lịch hoạt động, chi phí tài nguyên tính theo giờ và các hoạt động cần được thực hiện theo thứ tự nối tiếp.
Tại sao sử dụng Phương pháp tiếp cận Tham lam?
Dưới đây là những lý do để sử dụng phương pháp tham lam:
- Cách tiếp cận tham lam có một số điểm cân bằng, 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à để phân chia một bài toán một 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 giải pháp.
- 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ụ lập lị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ởi một số để tham khảo. Có hai hạng mục hoạt động.
- Hoạt động được coi là : là Hoạt động, là tham chiếu mà từ đó khả năng thực hiện nhiều hơn một Hoạt động còn lại được phân tích.
- các hoạt động còn lại: các hoạt động ở một hoặc nhiều chỉ mục 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. Đó là (kết thúc - bắt đầu) cho chúng ta giá trị hợp lý như chi phí của một hoạt động.
Bạn sẽ biết rằng mức độ tham lam là số lượng hoạt động còn lại bạn có thể thực hiện trong thời gian của một hoạt động được xem xét.
Kiến 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 với chỉ số 0 là Chỉ mục được xem xét.
BƯỚC 2)
Khi có thể kết thúc nhiều hoạt động hơn vào thời điểm, hoạt động được 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 còn lại, 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 còn lại, hãy chuyển sang bước 4.
BƯỚC 4 )
Trả lại sự kết hợp của các chỉ số được xem xét. Đây là các 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#include #include #define MAX_ACTIVITIES 12
Giải thích mã:
- Các lớp / tệp tiêu đề được bao gồm
- Số lượng tối đa các hoạt động 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.
- Định nghĩa lớp cho TIME
- Dấu thời gian một giờ.
- Một hàm tạo mặc định TIME
- Các biến số 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 bộ lập lịch.
- Chỉ mục được coi là điểm bắt đầ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 các đối tượng hoạt động được cấp phát động bằng cách sử dụng toán tử mới.
- Con trỏ đã lên 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 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 mỗi hoạt động hiện đang được lên lịch.
- Thời gian bắt đầu khởi tạo.
- Thời gian kết thúc khởi tạo 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 các thời lượng đượ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 bộ lập lịch.
- Hàm chọn hoạt động lấy chỉ mục đ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 được cung cấp.
- Chỉ số được coi là Chỉ số được gọi theo giá trị. Tham_số_gồm 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 cung cấp bởi chỉ mục được xem xét) sẽ kết thúc.
- Miễn là có thể, một câu lệnh gỡ lỗi tùy chọn sẽ được in.
- Chuyển đến 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ã:
- Kiểm tra có điều kiện nếu tất cả các hoạt động đã được bảo hiểm.
- Nếu không, bạn có thể bắt đầu 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 phân chia một cách tham lam câu lệnh vấn đề.
- Nếu có, nó sẽ trả về người gọi 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 mới được khởi tạo.
- Hàm chọn hoạt động, trả về một con trỏ của hoạt động kiểu quay trở lại người gọi sau khi nhiệm vụ tham lam kết thúc.
Đầu ra:
START:7 END 7START:9 END 10START:5 END 6START:10 END 10START:9 END 10Schedule start:5finish6activity:3Schedule start:9finish10activity:5
Nhược điểm của thuật toán tham lam
Nó không phù hợp với các bài toán Tham lam nơi cần có giải pháp cho mọi vấn đề con như sắp xếp.
Trong các bài toán thực hành thuật toán Tham lam như vậy, phương pháp Tham lam có thể sai; trong trường hợp xấu nhất thậm chí dẫn đến một giải pháp không tối ưu.
Do đó, nhược điểm của các thuật toán tham lam là sử dụng không biết những gì nằm trước trạng thái tham lam hiện tại.
Dưới đây là mô tả 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 (tham lam có giá trị cao hơn), trạng thái thuật toán ở giá trị: 40, có khả năng lấy 29 làm giá trị tiếp theo. Hơn nữa, nhiệm vụ của nó kết thúc ở 12. Con số này tương đương với giá trị 41.
Tuy nhiên, nếu thuật toán đi theo con đường dưới tối ưu hoặc áp dụng chiến lược chinh phục. sau đó 25 sẽ tiếp theo là 40, và chi phí cải thiện tổng thể sẽ là 65, được đánh giá cao hơn 24 điểm như một quyết định không tối ưu.
Ví dụ về thuật toán tham lam
Hầu hết các thuật toán mạng 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 Tham lam:
- Thuật toán cây kéo dài tối thiểu của Prim
- Vấn đề về nhân viên bán hàng đi du lịch
- Biểu đồ - Tô màu bản đồ
- Thuật toán cây kéo dài tối thiểu của Kruskal
- Thuật toán cây kéo dài tối thiểu của Dijkstra
- Đồ thị - Bìa đỉnh
- Vấn đề về Knapsack
- Vấn đề lên lịch công việc
Tóm lược:
Tóm lại, bài báo đã định nghĩa mô hình tham lam, cho thấy cách tối ưu hóa tham lam và đệ quy, có thể giúp bạn có được giải pháp tốt nhất cho đến thời điểm nào. Thuật toán Tham lam được sử dụng rộng rãi để giải quyết vấn đề bằng nhiều ngôn ngữ như Thuật toán tham lam 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 bài toán chiến lược có thể đạt được thông lượng tối đa bằng cách sử dụng thuật toán Tham lam tiếp cận. Cuối cùng, điểm yếu của việc sử dụng phương pháp tham lam đã được giải thích.