การเขียนโปรแกรมแบบไดนามิกหลักการพื้นฐาน

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

สาระสำคัญของวิธีการ

การเขียนโปรแกรมแบบไดนามิกประกอบด้วยการหาทางออกที่ดีที่สุดของปัญหา n มิติโดยแบ่งขั้นตอนแยกกัน n แต่ละคนเป็นแบบย่อยสำหรับหนึ่งตัวแปร

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

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

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

วิธีนี้ช่วยปรับปรุงประสิทธิภาพของงานที่แก้ไขได้โดยการค้นหาตัวแปรหรือการแย่งชิง

การสร้างอัลกอริทึมของปัญหา

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

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

การประยุกต์ใช้วิธีการ

การเขียนโปรแกรมแบบไดนามิกจะใช้เมื่อมีคุณลักษณะเฉพาะสองอย่าง:

• ความเหมาะสมสำหรับงานย่อย
• การแสดงตนของงานย่อยที่ทับซ้อนกันในปัญหา

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

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

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