Greedy Algorithms อธิบายด้วยตัวอย่าง

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

คุณอาจเคยได้ยินเกี่ยวกับเทคนิคการออกแบบอัลกอริทึมมากมายในขณะที่กลั่นกรองบทความบางส่วนที่นี่ บางส่วน ได้แก่ :

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

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

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

นิยามอย่างเป็นทางการ

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

อัลกอริทึมโลภมีข้อดีและข้อเสีย:

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

ปัญหาการจัดกำหนดการช่วงเวลา

มาดำดิ่งสู่ปัญหาที่น่าสนใจที่คุณสามารถพบได้ในเกือบทุกอุตสาหกรรมหรือทุกเส้นทางของชีวิต บางกรณีของปัญหามีดังนี้:

  • คุณจะได้รับตารางการบรรยาย N ชุดสำหรับหนึ่งวันที่มหาวิทยาลัย กำหนดการสำหรับการบรรยายเฉพาะเป็นรูปแบบ (s time, f time) โดยที่เวลา s หมายถึงเวลาเริ่มต้นสำหรับการบรรยายนั้นและเวลาfแทนเวลาจบ จากรายการตารางการบรรยาย N เราจำเป็นต้องเลือกชุดการบรรยายสูงสุดที่จะจัดขึ้นในระหว่างวันเพื่อให้   ไม่มีการบรรยายทับซ้อนกันเช่นถ้าการบรรยาย Li และ Lj รวมอยู่ในการเลือกของเราแล้วเวลาเริ่มต้นของ j > = เสร็จสิ้นเวลาของฉันหรือในทางกลับกัน
  • เพื่อนของคุณทำงานเป็นที่ปรึกษาค่ายและเขารับผิดชอบในการจัดกิจกรรมสำหรับผู้เข้าค่าย แผนการอย่างหนึ่งของเขาคือการออกกำลังกายแบบมินิไตรกีฬาดังต่อไปนี้ผู้เข้าแข่งขันแต่ละคนต้องว่ายน้ำ 20 รอบจากนั้นปั่นจักรยาน 10 ไมล์จากนั้นวิ่ง 3 ไมล์
  • แผนการส่งผู้เข้าแข่งขันออกไปในลักษณะเซโดยใช้กฎต่อไปนี้: ผู้เข้าแข่งขันจะต้องใช้สระว่ายน้ำทีละคน กล่าวอีกนัยหนึ่งผู้เข้าแข่งขันคนแรกว่ายน้ำครบ 20 รอบวิ่งออกไปและเริ่มขี่จักรยาน
  • ทันทีที่คนแรกขึ้นจากสระว่ายน้ำผู้เข้าแข่งขันคนที่สองเริ่มว่ายน้ำ 20 รอบ ทันทีที่เขาหรือเธอออกไปและเริ่มขี่จักรยานผู้เข้าแข่งขันคนที่สามจะเริ่มว่ายน้ำและอื่น ๆ
  • ผู้เข้าแข่งขันแต่ละคนมีเวลาว่ายน้ำที่คาดการณ์ไว้เวลาปั่นจักรยานที่คาดการณ์ไว้และเวลาวิ่งที่คาดการณ์ไว้ เพื่อนของคุณต้องการตัดสินใจเกี่ยวกับกำหนดการสำหรับไตรกีฬา: ลำดับที่จะจัดลำดับการเริ่มต้นของผู้เข้าแข่งขัน
  • สมมติว่าเวลาเสร็จสิ้นของตารางเป็นเวลาที่เร็วที่สุดที่ผู้เข้าแข่งขันทุกคนจะต้องจบไตรกีฬาทั้งสามขาโดยสมมติว่าการคาดการณ์เวลานั้นแม่นยำ อะไรคือคำสั่งที่ดีที่สุดในการส่งผู้คนออกไปหากต้องการให้การแข่งขันทั้งหมดจบลงโดยเร็วที่สุด? แม่นยำยิ่งขึ้นให้อัลกอริทึมที่มีประสิทธิภาพซึ่งสร้างตารางเวลาที่มีเวลาเสร็จสิ้นน้อยที่สุด

ปัญหาการจัดตารางการบรรยาย

ลองดูแนวทางต่างๆในการแก้ปัญหานี้

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

เวลาเริ่มต้นที่เร็วที่สุดก่อน

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

ช่วงเวลาที่สั้นที่สุดก่อน

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

ช่วงเวลาที่ขัดแย้งน้อยที่สุดอันดับแรก  คือคุณควรดูช่วงเวลาที่ก่อให้เกิดความขัดแย้งน้อยที่สุด อีกครั้งเรามีตัวอย่างที่วิธีนี้ไม่สามารถหาทางออกที่ดีที่สุดได้

ช่วงเวลาที่ขัดแย้งกันน้อยที่สุดก่อน

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

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

function interval_scheduling_problem(requests) schedule \gets \{\} while requests is not yet empty choose a request i_r \in requests that has the lowest finishing time schedule \gets schedule \cup \{i_r\} delete all requests in requests that are not compatible with i_r end return schedule end 

เมื่อใดที่เราใช้ Greedy Algorithms

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

Greedy Algorithms ช่วยเราแก้ปัญหาต่างๆมากมายเช่น:

ปัญหาเส้นทางที่สั้นที่สุด:

ปัญหาขั้นต่ำของ Spanning Tree ในกราฟ

ปัญหาการเข้ารหัส Huffman

ปัญหาศูนย์ K