อัลกอริทึมแบบคู่ขนาน - เทคนิคการออกแบบ

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

• แบ่งและพิชิต
• วิธีโลภ
• การเขียนโปรแกรมแบบไดนามิก
• Backtracking
• สาขา & ผูกพัน
• การเขียนโปรแกรมเชิงเส้น

วิธีหารและพิชิต

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

แนวทางการแบ่งแยกและพิชิตเกี่ยวข้องกับขั้นตอนต่อไปนี้ในแต่ละระดับ -

• Divide - ปัญหาเดิมแบ่งเป็นปัญหาย่อย

• Conquer - ปัญหาย่อยได้รับการแก้ไขแบบวนซ้ำ

• Combine - นำแนวทางแก้ไขปัญหาย่อยมารวมกันเพื่อหาทางออกของปัญหาเดิม

แนวทางการแบ่งและพิชิตถูกนำไปใช้ในอัลกอริทึมต่อไปนี้ -

• การค้นหาแบบไบนารี
• จัดเรียงด่วน
• ผสานการจัดเรียง
• การคูณจำนวนเต็ม
• การผกผันของเมทริกซ์
• การคูณเมทริกซ์

วิธีโลภ

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

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

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

การเขียนโปรแกรมแบบไดนามิก

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

อัลกอริทึมแบบเรียกซ้ำสำหรับ Fibonacci Series เป็นตัวอย่างของการเขียนโปรแกรมแบบไดนามิก

Backtracking Algorithm

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

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

สาขาและขอบเขต

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

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

การเขียนโปรแกรมเชิงเส้น

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

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