อัลกอริธึมโลภพร้อมตัวอย่าง: คืออะไร วิธีการ และแนวทาง

เพื่อทำความเข้าใจแนวทางโลภ คุณจะต้องมีความรู้ในการทำงานเกี่ยวกับการเรียกซ้ำและการสลับบริบท ซึ่งจะช่วยให้คุณเข้าใจวิธีการติดตามโค้ด คุณสามารถกำหนดกระบวนทัศน์แห่งความละโมบได้ในแง่ของข้อความที่จำเป็นและเพียงพอของคุณเอง

เงื่อนไขสองประการกำหนดกระบวนทัศน์แห่งความละโมบ

• วิธีแก้ปัญหาแต่ละขั้นตอนจะต้องสร้างโครงสร้างปัญหาให้สอดคล้องกับวิธีแก้ปัญหาที่ดีที่สุดที่ได้รับการยอมรับ
• ก็เพียงพอแล้วหากโครงสร้างของปัญหาสามารถหยุดได้ในขั้นตอนโลภจำนวนจำกัด

ในขณะที่การสร้างทฤษฎีดำเนินต่อไป เราจะอธิบายประวัติที่เกี่ยวข้องกับแนวทางการค้นหา Greedy

ประวัติศาสตร์แห่งความโลภ Algorithms

นี่คือจุดสังเกตสำคัญของอัลกอริทึมที่โลภ:

• อัลกอริธึมแบบโลภถูกคิดค้นขึ้นสำหรับอัลกอริธึมการเดินกราฟมากมายในช่วงทศวรรษปี 1950
• Esdger Djikstra วางแนวคิดเกี่ยวกับอัลกอริทึมเพื่อสร้างแผนผังที่ขยายน้อยที่สุด เขาตั้งเป้าที่จะย่นระยะเวลาเส้นทางภายในกรุงอัมสเตอร์ดัม เมืองหลวงของเนเธอร์แลนด์
• ในทศวรรษเดียวกัน Prim และ Kruskal บรรลุกลยุทธ์การปรับให้เหมาะสมซึ่งอิงจากการลดต้นทุนเส้นทางตามเส้นทางที่ชั่งน้ำหนักให้เหลือน้อยที่สุด
• ในทศวรรษ 70 นักวิจัยชาวอเมริกัน Cormen, Rivest และ Stein ได้เสนอโครงสร้างย่อยแบบเรียกซ้ำของโซลูชันที่โลภมากในหนังสือแนะนำอัลกอริทึมแบบคลาสสิกของพวกเขา
• กระบวนทัศน์การค้นหา Greedy ได้รับการบันทึกเป็นกลยุทธ์การปรับให้เหมาะสมประเภทอื่นในบันทึกของ NIST ในปี 2005
• จนถึงปัจจุบัน โปรโตคอลที่รันเว็บ เช่น open-shortest-path-first (OSPF) และโปรโตคอลการสลับแพ็กเก็ตเครือข่ายอื่นๆ จำนวนมากใช้กลยุทธ์ที่โลภเพื่อลดเวลาที่ใช้บนเครือข่าย

กลยุทธ์และการตัดสินใจที่โลภ

ตรรกะในรูปแบบที่ง่ายที่สุดถูกต้มจนเป็น "โลภ" หรือ "ไม่โลภ" ข้อความเหล่านี้ถูกกำหนดโดยแนวทางที่ใช้เพื่อความก้าวหน้าในแต่ละขั้นตอนของอัลกอริทึม

ตัวอย่างเช่น อัลกอริทึมของ Djikstra ใช้กลยุทธ์แบบทีละขั้นตอนในการระบุโฮสต์บนอินเทอร์เน็ตโดยคำนวณฟังก์ชันต้นทุน ค่าที่ส่งคืนโดยฟังก์ชันต้นทุนจะกำหนดว่าเส้นทางถัดไปจะเป็นแบบ "โลภ" หรือ "ไม่โลภ"

กล่าวโดยสรุป อัลกอริธึมจะไม่โลภหากขั้นตอนใดขั้นตอนหนึ่งที่ไม่โลภในท้องถิ่น ปัญหาความโลภยุติลงโดยไม่มีขอบเขตของความโลภอีกต่อไป

ลักษณะของอัลกอริทึม Greedy

ลักษณะสำคัญของอัลกอริทึม Greedy คือ:

• มีรายการทรัพยากรที่เรียงลำดับพร้อมการระบุต้นทุนหรือมูลค่า ข้อจำกัดเหล่านี้เป็นปริมาณในระบบ
• คุณจะใช้ทรัพยากรในปริมาณสูงสุดในเวลาที่มีข้อจำกัด
• ตัวอย่างเช่น ในปัญหาการกำหนดตารางกิจกรรม ต้นทุนทรัพยากรจะคิดเป็นชั่วโมง และกิจกรรมต่างๆ จะต้องดำเนินการตามลำดับ

ทำไมต้องใช้วิธีโลภ?

ต่อไปนี้เป็นเหตุผลในการใช้วิธีการโลภ:

• แนวทางที่ละโมบมีข้อแลกเปลี่ยนอยู่บ้าง ซึ่งอาจจะทำให้เหมาะสำหรับการเพิ่มประสิทธิภาพได้
• เหตุผลสำคัญประการหนึ่งคือการบรรลุแนวทางแก้ไขที่เป็นไปได้มากที่สุดทันที ในปัญหาการเลือกกิจกรรม (อธิบายด้านล่าง) หากสามารถทำกิจกรรมเพิ่มเติมได้ก่อนที่จะทำกิจกรรมปัจจุบันเสร็จสิ้น กิจกรรมเหล่านี้ก็สามารถดำเนินการได้ภายในเวลาเดียวกัน
• อีกเหตุผลหนึ่งคือการแบ่งปัญหาแบบวนซ้ำตามเงื่อนไข โดยไม่จำเป็นต้องรวมวิธีแก้ปัญหาทั้งหมด
• ในปัญหาการเลือกกิจกรรม ขั้นตอน "การแบ่งแบบเรียกซ้ำ" ทำได้โดยการสแกนรายการข้อมูลเพียงครั้งเดียวและพิจารณากิจกรรมบางอย่าง

วิธีแก้ปัญหาการเลือกกิจกรรม

ในตัวอย่างการจัดกำหนดการกิจกรรม มีเวลา "เริ่มต้น" และ "สิ้นสุด" สำหรับทุกกิจกรรม แต่ละกิจกรรมจะถูกจัดทำดัชนีด้วยตัวเลขเพื่อใช้อ้างอิง กิจกรรมมีสองประเภท

1. ถือเป็นกิจกรรม: คือ Activity ซึ่งเป็นข้อมูลอ้างอิงที่ใช้วิเคราะห์ความสามารถในการทำกิจกรรมที่เหลือมากกว่าหนึ่งกิจกรรม
2. กิจกรรมที่เหลือ: กิจกรรมในดัชนีตั้งแต่หนึ่งรายการขึ้นไปก่อนกิจกรรมที่พิจารณา

ระยะเวลาทั้งหมดจะเป็นค่าใช้จ่ายในการดำเนินกิจกรรม นั่นคือ (เสร็จสิ้น – เริ่มต้น) ให้ระยะเวลาเป็นต้นทุนของกิจกรรม

คุณจะได้เรียนรู้ว่าขอบเขตความโลภคือจำนวนกิจกรรมที่เหลือที่คุณสามารถทำในช่วงเวลาของกิจกรรมที่พิจารณาได้

Archiการสอนแนวทาง Gredy

ขั้นตอนที่ 1) สแกนรายการต้นทุนกิจกรรม โดยเริ่มจากดัชนี 0 เป็นดัชนีที่พิจารณา

ขั้นตอนที่ 2) เมื่อสามารถทำกิจกรรมอื่น ๆ เสร็จได้ทันเวลา กิจกรรมที่พิจารณาเสร็จสิ้นแล้ว จึงเริ่มค้นหากิจกรรมที่เหลือหนึ่งรายการหรือหลายรายการ

ขั้นตอนที่ 3) หากไม่มีกิจกรรมเหลืออยู่ กิจกรรมที่เหลืออยู่ในปัจจุบันจะกลายเป็นกิจกรรมที่พิจารณาถัดไป ทำซ้ำขั้นตอนที่ 1 และขั้นตอนที่ 2 โดยมีกิจกรรมที่พิจารณาใหม่ หากไม่มีกิจกรรมเหลืออยู่ ให้ไปที่ขั้นตอนที่ 4

ขั้นตอนที่ 4 ) ส่งกลับการรวมดัชนีที่พิจารณา สิ่งเหล่านี้คือดัชนีกิจกรรมที่จะใช้เพื่อเพิ่มปริมาณงานสูงสุด

คำอธิบายรหัส

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

#define MAX_ACTIVITIES 12

คำอธิบายของรหัส:

1. รวมไฟล์ส่วนหัว/คลาส
2. จำนวนกิจกรรมสูงสุดที่ผู้ใช้ให้ไว้

using namespace std;

class TIME
{
    public:
    int hours;

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

คำอธิบายของรหัส:

1. เนมสเปซสำหรับการดำเนินการสตรีมมิ่ง
2. คำจำกัดความของคลาสสำหรับ TIME
3. การประทับเวลาหนึ่งชั่วโมง
4. ตัวสร้างเริ่มต้นของ TIME
5. เวลามีการเปลี่ยนแปลง

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

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

คำอธิบายของรหัส:

1. คำจำกัดความของชั้นเรียนจากกิจกรรม
2. การประทับเวลาซึ่งกำหนดระยะเวลา
3. การประทับเวลาทั้งหมดจะเริ่มต้นเป็น 0 ในตัวสร้างเริ่มต้น

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

คำอธิบายของรหัส:

1. ส่วนที่ 1 ของคำจำกัดความคลาสตัวกำหนดเวลา
2. ดัชนีที่พิจารณาเป็นจุดเริ่มต้นในการสแกน แถว.
3. ดัชนีการเริ่มต้นใช้เพื่อกำหนดการประทับเวลาแบบสุ่ม
4. อาร์เรย์ของวัตถุกิจกรรมจะถูกจัดสรรแบบไดนามิกโดยใช้ตัวดำเนินการใหม่
5. ตัวชี้ที่กำหนดเวลาไว้จะกำหนดตำแหน่งฐานปัจจุบันสำหรับความโลภ

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

คำอธิบายของรหัส:

1. ตัวสร้างตัวจัดกำหนดการ - ส่วนที่ 2 ของคำจำกัดความคลาสตัวจัดกำหนดการ
2. ดัชนีที่พิจารณาจะกำหนดการเริ่มการสแกนในปัจจุบัน
3. ขอบเขตความโลภในปัจจุบันไม่ได้ถูกกำหนดไว้ตั้งแต่เริ่มต้น

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

คำอธิบายของรหัส:

1. วงจรสำหรับการเริ่มต้นชั่วโมงเริ่มต้นและชั่วโมงสิ้นสุดของกิจกรรมแต่ละกิจกรรมที่จัดกำหนดการไว้ในปัจจุบัน
2. การเริ่มต้นเวลาเริ่มต้น
3. การเริ่มต้นเวลาสิ้นสุดจะอยู่หลังหรือที่ชั่วโมงเริ่มต้นเสมอ
4. คำสั่งแก้ไขข้อบกพร่องเพื่อพิมพ์ระยะเวลาที่จัดสรร

	public:
   		 Activity * activity_select(int);
};

คำอธิบายของรหัส:

1. ส่วนที่ 4 – ส่วนสุดท้ายของคำจำกัดความคลาสตัวจัดกำหนดการ
2. ฟังก์ชั่นการเลือกกิจกรรมจะใช้ดัชนีจุดเริ่มต้นเป็นฐานและแบ่งภารกิจที่โลภออกเป็นปัญหาย่อยที่โลภ

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

1. การใช้ตัวดำเนินการการแก้ไขขอบเขต (::) จะทำให้สามารถกำหนดฟังก์ชันได้
2. ดัชนีที่พิจารณาคือดัชนีที่เรียกตามค่า greedy_extent เป็นค่าเริ่มต้นเพียงดัชนีหลังจากดัชนีที่พิจารณา

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

คำอธิบายของรหัส:

1. ตรรกะหลัก - ความโลภนั้นจำกัดอยู่ที่จำนวนกิจกรรม
2. ชั่วโมงเริ่มต้นของกิจกรรมปัจจุบันจะถูกตรวจสอบว่าสามารถจัดกำหนดการได้ก่อนที่กิจกรรมที่พิจารณา (ให้โดยดัชนีที่พิจารณา) จะเสร็จสิ้น
3. ตราบเท่าที่เป็นไปได้ คำสั่งดีบักเผื่อเลือกจะถูกพิมพ์
4. เลื่อนไปยังดัชนีถัดไปในอาร์เรย์กิจกรรม

...
if ( greedy_extent <= MAX_ACTIVITIES )
    {

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

คำอธิบายของรหัส:

1. การตรวจสอบแบบมีเงื่อนไขว่ากิจกรรมทั้งหมดได้รับการคุ้มครองหรือไม่
2. ถ้าไม่เช่นนั้น คุณสามารถเริ่มต้นความโลภของคุณใหม่โดยให้ดัชนีที่พิจารณาเป็นจุดปัจจุบัน นี่เป็นขั้นตอนการเรียกซ้ำที่แบ่งคำชี้แจงปัญหาอย่างตะกละตะกลาม
3. ถ้าใช่ มันจะกลับไปหาผู้โทรโดยไม่มีขอบเขตที่จะขยายความโลภ

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

คำอธิบายของรหัส:

1. ฟังก์ชั่นหลักที่ใช้ในการเรียกใช้ตัวกำหนดตารางเวลา
2. ตัวกำหนดเวลาใหม่จะถูกสร้างขึ้นทันที
3. ฟังก์ชั่นเลือกกิจกรรมซึ่งส่งคืนพอยน์เตอร์ประเภทกิจกรรมจะกลับมาหาผู้เรียกหลังจากภารกิจโลภสิ้นสุดลง

Output:

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

ข้อจำกัดของเทคนิคโลภ

ไม่เหมาะกับปัญหา Greedy ที่จำเป็นต้องมีวิธีแก้ไขสำหรับทุกปัญหาย่อย เช่น การเรียงลำดับ

ในปัญหาการฝึกหัดอัลกอริทึม Greedy วิธี Greedy อาจผิดได้ ในกรณีที่เลวร้ายที่สุดอาจนำไปสู่วิธีแก้ปัญหาที่ไม่เหมาะที่สุดด้วยซ้ำ

ดังนั้นข้อเสียของอัลกอริทึมแบบโลภก็คือ การไม่รู้ว่าสถานะโลภในปัจจุบันจะเป็นอย่างไรต่อไป

ด้านล่างนี้เป็นภาพข้อเสียของวิธี Greedy:

ในการสแกนแบบโลภที่แสดงที่นี่เป็นต้นไม้ (ค่าที่สูงกว่าความโลภที่สูงกว่า) สถานะอัลกอริทึมที่ค่า: 40 มีแนวโน้มว่าจะใช้ 29 เป็นค่าถัดไป นอกจากนี้ ภารกิจสิ้นสุดที่ 12 ซึ่งมีค่าเท่ากับ 41

อย่างไรก็ตาม หากอัลกอริทึมใช้เส้นทางที่ไม่เหมาะสมหรือใช้กลยุทธ์ในการพิชิต จากนั้น 25 จะตามมาด้วย 40 และการปรับปรุงต้นทุนโดยรวมจะเป็น 65 ซึ่งมีมูลค่าสูงกว่า 24 คะแนนในฐานะการตัดสินใจที่ไม่ดีนัก

ตัวอย่างของ Gredy Algorithms

อัลกอริทึมเครือข่ายส่วนใหญ่ใช้แนวทางแบบโลภ นี่คือรายการตัวอย่างอัลกอริทึมแบบโลภบางส่วน:

• อัลกอริทึม Spanning Tree ขั้นต่ำของ Prim
• ปัญหาพนักงานขายในการเดินทาง
• กราฟ – การระบายสีแผนที่
• อัลกอริทึม Spanning Tree ขั้นต่ำของ Kruskal
• อัลกอริทึม Spanning Tree ขั้นต่ำของ Dijkstra
• กราฟ – ฝาครอบจุดยอด
• ปัญหากระเป๋าเป้สะพายหลัง
• ปัญหาการจัดตารางเวลางาน

สรุป

โดยสรุป บทความนี้ได้อธิบายถึงแนวคิดแบบโลภะ แสดงให้เห็นว่าการเพิ่มประสิทธิภาพแบบโลภะและการเรียกซ้ำสามารถช่วยให้คุณได้รับโซลูชันที่ดีที่สุดได้ในระดับหนึ่ง อัลกอริทึมแบบโลภะถูกนำไปใช้ในการแก้ปัญหาในหลายภาษาอย่างแพร่หลาย เช่น อัลกอริทึมแบบโลภะ Python, C, C#, PHP, Javaฯลฯ การเลือกกิจกรรมของตัวอย่างอัลกอริทึม Greedy ได้รับการอธิบายว่าเป็นปัญหาเชิงกลยุทธ์ที่สามารถบรรลุปริมาณงานสูงสุดโดยใช้แนวทาง greedy ในที่สุดก็มีการอธิบายข้อเสียของการใช้แนวทางโลภแล้ว