ผลต่างระหว่างรุ่นของ "ขั้นตอนวิธี/กำหนดการพลวัต"

จาก วิกิตำรา
เนื้อหาที่ลบ เนื้อหาที่เพิ่ม
Nullzero (คุย | ส่วนร่วม)
Pitpisit (คุย | ส่วนร่วม)
ไม่มีความย่อการแก้ไข
 
บรรทัดที่ 2: บรรทัดที่ 2:


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

== สารบัญ ==
* [[ขั้นตอนวิธี/การแบ่งแยกและเอาชนะ|/การแบ่งแยกและเอาชนะ]]
* [[ขั้นตอนวิธี/กำหนดการพลวัต|/กำหนดการพลวัต]]
* [[ขั้นตอนวิธี/ขั้นตอนวิธีเชิงละโมบ|/ขั้นตอนวิธีเชิงละโมบ]]


[[หมวดหมู่:ขั้นตอนวิธี]]
[[หมวดหมู่:ขั้นตอนวิธี]]

รุ่นแก้ไขปัจจุบันเมื่อ 19:17, 21 เมษายน 2560

กำหนดการพลวัต (Dynamic programming)

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

สารบัญ[แก้ไข | แก้ไขต้นฉบับ]