Bài toán lựa chọn hoạt động là một bài toán trong đó chúng ta được đưa ra một tập hợp các hoạt động với thời gian bắt đầu và kết thúc của chúng. Và chúng tôi cần tìm tất cả những hoạt động mà một người có thể thực hiện khi thực hiện một hoạt động duy nhất tại một thời điểm.
Thuật toán tham lam được chỉ định trong bài toán này để chọn hoạt động tiếp theo sẽ được thực hiện. Đầu tiên chúng ta hãy hiểu thuật toán tham lam .
Thuật toán tham lam là một thuật toán cố gắng tìm giải pháp cho một vấn đề bằng cách tìm giải pháp từng bước. Để chọn bước tiếp theo, thuật toán cũng đã chọn bước có vẻ hứa hẹn nhất, tức là có thể dẫn đến giải pháp được tối ưu hóa ngay lập tức so với bước còn lại. Thuật toán tham lam được sử dụng để giải quyết các vấn đề tối ưu hóa vì nó cố gắng tìm ra giải pháp tối ưu hóa nhất cho bước trung gian tiếp theo dẫn đến giải pháp tối ưu cho toàn bộ vấn đề.
Mặc dù thuật toán tham lam là một giải pháp tốt nhưng có một số vấn đề mà nó không thể áp dụng được. Ví dụ:không thể giải quyết cặp 0-1 bằng thuật toán tham lam.
Thuật toán
Một số thuật toán tham lam tiêu chuẩn là -
1) Dijkstrata’s Shortest Path
2) Minimum Spanning Tree (MST) {prim’s and kruskal’s}
3) Huffman coding Vấn đề lựa chọn không hoạt động, chúng tôi có n vấn đề với thời gian bắt đầu và kết thúc. Và chúng tôi cần chọn số lượng tối đa các hoạt động có thể được thực hiện bởi một cá nhân mà anh ta có thể thực hiện một hoạt động duy nhất tại một thời điểm.
Có 3 hoạt động được sắp xếp theo thứ tự thời gian kết thúc,
Start = [1 , 5 , 12 ] End = [10, 13, 23]
Ở đây, người đó sẽ có thể thực hiện nhiều nhất hai hoạt động. Các hoạt động có thể được thực hiện là [0, 2].
Ví dụ
#include<stdio.h>
int main(){
int start[] = {1 , 5 , 12};
int finish[] = {10, 13, 23};
int activities = sizeof(start)/sizeof(start[0]);
int i, j;
printf ("Following activities are selected \t");
i = 0;
printf("%d\t", i);
for (j = 1; j < activities; j++){
if (start[j] >= finish[i]){
printf ("%d ", j);
i = j;
}
}
return 0;
} Đầu ra
Following activities are selected 0 2