ปัญหาการเลือกกิจกรรมเป็นปัญหาที่เราได้รับชุดกิจกรรมพร้อมเวลาเริ่มต้นและสิ้นสุด และเราจำเป็นต้องค้นหากิจกรรมทั้งหมดที่บุคคลสามารถทำกิจกรรมเดียวในแต่ละครั้งได้
ปัญหานี้กำหนดอัลกอริธึมที่โลภเพื่อเลือกกิจกรรมถัดไปที่จะดำเนินการ มาทำความเข้าใจอัลกอริทึมที่โลภ . กันก่อน .
อัลกอริทึมโลภ เป็นอัลกอริธึมที่พยายามค้นหาวิธีแก้ไขปัญหาโดยค้นหาวิธีแก้ปัญหาทีละขั้นตอน สำหรับการเลือกขั้นตอนต่อไป อัลกอริธึมยังเลือกขั้นตอนที่น่าจะเป็นไปได้มากที่สุด กล่าวคือ สามารถนำไปสู่โซลูชันที่ปรับให้เหมาะสมทันทีเมื่อเปรียบเทียบกับการพักผ่อน อัลกอริธึมที่โลภใช้เพื่อแก้ปัญหาการปรับให้เหมาะสมในขณะที่พยายามค้นหาโซลูชันที่เหมาะสมที่สุดสำหรับขั้นตอนกลางถัดไปที่นำไปสู่วิธีแก้ปัญหาที่เหมาะสมที่สุดสำหรับปัญหาทั้งหมด
แม้ว่าอัลกอริธึมที่โลภจะเป็นทางออกที่ดี แต่มีปัญหาบางอย่างที่ไม่สามารถนำมาใช้ได้ ตัวอย่างเช่น 0-1 เป้ไม่สามารถแก้ไขได้โดยใช้อัลกอริธึมโลภ
อัลกอริทึม
อัลกอริทึมโลภมาตรฐานบางอย่างคือ -
1) Dijkstrata’s Shortest Path
2) Minimum Spanning Tree (MST) {prim’s and kruskal’s}
3) Huffman coding ปัญหาการเลือกไม่ใช้งาน เราได้รับ n ปัญหาเกี่ยวกับเวลาเริ่มต้นและสิ้นสุด และเราจำเป็นต้องเลือกจำนวนกิจกรรมสูงสุดที่แต่ละคนสามารถทำได้ โดยกำหนดให้เขาทำกิจกรรมเดียวในช่วงเวลาหนึ่งได้
มี 3 กิจกรรม เรียงตามลำดับเวลาจบ
Start = [1 , 5 , 12 ] End = [10, 13, 23]
ที่นี่บุคคลจะสามารถทำกิจกรรมได้ไม่เกินสองกิจกรรม กิจกรรมที่ดำเนินการได้คือ [0, 2]
ตัวอย่าง
#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;
} ผลลัพธ์
Following activities are selected 0 2
