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

อัลกอริทึม Greedy คืออะไร?

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

การแก้ปัญหาด้วยวิธีการแบบโลภ (greedy approach) มีสองขั้นตอน:

1. กำลังสแกนรายการสินค้า
2. การเพิ่มประสิทธิภาพ

ทั้งสองขั้นตอนทำงานพร้อมกันในขณะที่อาร์เรย์อินพุตถูกแบ่งออกไปเรื่อยๆ

เพื่อให้สามารถใช้แนวทางแบบโลภ (greedy approach) ได้ ความรู้พื้นฐานเกี่ยวกับการเรียกซ้ำ (recursion) และการสลับบริบท (context switching) จะช่วยคุณได้ trace. โค้ด รูปแบบโลภ (greedy paradigm) สามารถอธิบายได้ด้วยข้อความจำเป็นและข้อความเพียงพอสองข้อ

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

• แต่ละทางเลือกในแต่ละขั้นตอนจะต้องนำพาปัญหาไปสู่ทางออกที่ดีที่สุดที่ได้รับการยอมรับ
• โครงสร้างของปัญหาจะต้องหยุดลงภายในจำนวนขั้นตอนแบบโลภ (greedy steps) ที่จำกัด

เมื่อเข้าใจทฤษฎีแล้ว เรามาดูประวัติความเป็นมาของวิธีการค้นหาแบบโลภ (greedy search) กัน

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

ต่อไปนี้คือเหตุการณ์สำคัญในประวัติศาสตร์ของอัลกอริทึมแบบโลภ:

• แนวคิดของอัลกอริทึมแบบโลภ (Greedy algorithms) ถูกคิดค้นขึ้นครั้งแรกสำหรับอัลกอริทึมการเดินบนกราฟในช่วงทศวรรษ 1950
• เอ็ดสเกอร์ ไดจ์กสตรา พัฒนาอัลกอริทึมหาเส้นทางที่สั้นที่สุดเพื่อย่นระยะทางในการเดินทางทั่วเมืองหลวงของเนเธอร์แลนด์อย่างอัมสเตอร์ดัม
• ในทศวรรษเดียวกันนั้น Prim และ Kruskal ได้พัฒนากลยุทธ์การปรับให้เหมาะสมที่สุดซึ่งลดต้นทุนเส้นทางตามเส้นทางที่มีน้ำหนักเพื่อสร้างต้นไม้ครอบคลุมขั้นต่ำ
• ในช่วงทศวรรษ 70 นักวิจัยชาวอเมริกัน Cormen, Leiserson, Rivest และ Stein ได้อธิบายถึงโครงสร้างย่อยแบบเรียกซ้ำของวิธีแก้ปัญหาแบบโลภในงานวิจัยคลาสสิกของพวกเขา Introduction to Algorithms หนังสือเรียน.
• รูปแบบการค้นหาแบบโลภ (greedy search paradigm) ถูกจัดอยู่ในหมวดหมู่กลยุทธ์การเพิ่มประสิทธิภาพที่แตกต่างในบันทึกของ NIST ในปี 2005
• จนถึงปัจจุบัน โปรโตคอลเว็บ เช่น Open Shortest Path First (OSPF) และโปรโตคอลการสลับแพ็กเก็ตจำนวนมากยังคงใช้กลยุทธ์แบบโลภ (greedy strategy) เพื่อลดเวลาการส่งผ่านข้อมูลบนเครือข่ายให้เหลือน้อยที่สุด

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

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

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

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

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

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

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

เหตุใดจึงใช้วิธีการแบบโลภ?

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

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

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

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

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

ต้นทุนในการดำเนินกิจกรรมคือระยะเวลาของกิจกรรมนั้น ซึ่งคำนวณได้จาก (เวลาสิ้นสุด – เวลาเริ่มต้น)

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

Archiการสอนเรื่องแนวทางโลภ

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

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

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

ขั้นตอน 4) ส่งคืนค่ารวมของดัชนีที่พิจารณา — ซึ่งก็คือดัชนีกิจกรรมที่ทำให้ได้ผลผลิตสูงสุด

Archiการสอนเรื่องแนวทางโลภ

Code คำอธิบาย

#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. นิยามคลาสสำหรับกิจกรรม (Activity)
2. ช่วงเวลาที่นำมารวมกันจะกำหนดระยะเวลา
3. ในคอนสตรัคเตอร์เริ่มต้น ค่าเวลาทั้งหมดจะถูกกำหนดให้เป็น 0

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

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

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

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

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

1. ตัวสร้างคลาส Scheduler — ส่วนที่ 2 ของคำจำกัดความคลาส
2. considered_index ระบุจุดเริ่มต้นของการสแกนปัจจุบัน
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);
 }
&#8230;
&#8230;

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

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

	public:
   		 Activity * activity_select(int);
};

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

1. ส่วนที่ 4 — ส่วนสุดท้ายของคำจำกัดความคลาส Scheduler
2. activity_select() รับดัชนีเริ่มต้นเป็นฐานและแบ่งภารกิจแบบโลภ (greedy quest) ออกเป็นปัญหาย่อย

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

1. ตัวดำเนินการกำหนดขอบเขต (::) เชื่อมโยงคำจำกัดความของฟังก์ชันเข้ากับคลาส Scheduler
2. considered_index จะถูกส่งผ่านค่า และ 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++;
    	}
&#8230;
...

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

1. หลักการพื้นฐานคือ ขอบเขตการเข้าถึงแบบโลภ (greedy extent) จะถูกจำกัดไว้ที่ MAX_ACTIVITIES
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. ฟังก์ชันหลักจะเรียกใช้ตัวกำหนดตารางเวลา (Scheduler)
2. มีการสร้างอ็อบเจ็กต์ Scheduler ใหม่ขึ้นมา
3. ฟังก์ชัน activity_select() จะส่งคืนพอยเตอร์ของ Activity ให้กับผู้เรียกเมื่อการค้นหาแบบโลภสิ้นสุดลง

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 approach) ไม่เหมาะสมกับปัญหาที่ต้องการคำตอบที่ดีที่สุดสำหรับทุกปัญหาย่อย เช่น การเรียงลำดับ

ในกรณีเช่นนี้ วิธีการแบบโลภอาจผิดพลาดได้ — ในกรณีที่แย่ที่สุด มันอาจให้ผลลัพธ์ที่ไม่เหมาะสมที่สุด

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

แผนภาพด้านล่างนี้แสดงให้เห็นถึงข้อเสียของวิธีการแบบโลภ (greedy method)

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

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

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

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

• อัลกอริทึมต้นไม้ครอบคลุมขั้นต่ำของ Prim
• ปัญหาพนักงานขายเดินทาง (โดยประมาณ)
• การระบายสีแผนที่กราฟ
• อัลกอริทึมต้นไม้แผ่คลุมขั้นต่ำของครัสกัล
• อัลกอริทึมเส้นทางที่สั้นที่สุดของไดจ์กสตรา
• การครอบคลุมจุดยอดของกราฟ
• ปัญหากระเป๋าเป้สะพายหลัง
• การจัดลำดับงานพร้อมกำหนดเวลา

คำถามที่พบบ่อย