กำหนดการพลวัตและโครงสร้างย่อยที่เหมาะสมที่สุด

ทางลัด: ความแตกต่างความคล้ายคลึงกันค่าสัมประสิทธิ์การเปรียบเทียบ Jaccardการอ้างอิง

ความแตกต่างระหว่าง กำหนดการพลวัตและโครงสร้างย่อยที่เหมาะสมที่สุด

กำหนดการพลวัต vs. โครงสร้างย่อยที่เหมาะสมที่สุด

ในคณิตศาสตร์ วิทยาการคอมพิวเตอร์ และเศรษฐศาสตร์ กำหนดการพลวัต (dynamic programming) คือกระบวนการในการแก้ไขปัญหาที่ซับซ้อนโดยการแบ่งปัญหาให้เป็นปัญหาย่อยที่สามารถแก้ได้ง่ายกว่า คุณสมบัติพื้นฐานของปัญหาที่จะใช้กำหนดการพลวัตได้คือจะต้องมีปัญหาย่อยที่ทับซ้อนกัน (overlapping subproblem) และโครงสร้างย่อยที่เหมาะสมที่สุด (optimal substructure) ปัญหาที่ใช้กำหนดการพลวัตในการแก้ปัญหาจะใช้เวลาแก้รวดเร็วกว่าการแก้ปัญหาโดยตรงเป็นอย่างมาก หลักสำคัญของกำหนดการพลวัตมาจากการสังเกตว่าในการแก้ปัญหาที่ซับซ้อนนั้น จำเป็นที่จะต้องแก้ปัญหาที่เล็กกว่า (ปัญหาย่อย) และนำคำตอบของปัญหาย่อยเหล่านั้นมารวมกันเป็นคำตอบของปัญหาใหญ่ และในการดำเนินการแก้ปัญหาย่อยนี้ มีหลายปัญหาที่ปัญหาย่อยบางส่วนเหมือนกันทุกประการ ดังนั้นแทนที่จะแก้ไขปัญหาย่อยเหล่านี้ซ้ำอีกรอบ กระบวนการกำหนดการพลวัตจะใช้วิธีแก้ไขปัญหาย่อยเหล่านี้เพียงแค่ครั้งเดียว และเก็บคำตอบไว้ หรือที่เรียกว่าการจำ (memoization; ระวังสะกดเป็น memorization) เมื่อพบปัญหาย่อยดังกล่าวอีกครั้งก็ไม่จำเป็นต้องคำนวณซ้ำใหม่ แต่สามารถเรียกคำตอบที่เก็บไว้มาใช้ได้เลย กระบวนการนี้จะมีประสิทธิภาพดีเป็นอย่างยิ่งเมื่อปัญหาที่จะแก้มีจำนวนปัญหาย่อยที่ทับซ้อนกันเป็นจำนวนมาก ซึ่งหากไม่ได้ใช้กำหนดการพลวัตจะทำให้จำนวนครั้งในการแก้ปัญหาย่อยเติบโตแบบฟังก์ชันเลขชี้กำลัง ส่งผลให้เวลาในการแก้ไขปัญหาเพิ่มขึ้นเป็นอย่างมาก. ในสาขาวิทยาการคอมพิวเตอร์ เราจะกล่าวว่าปัญหาใด ๆ มี โครงสร้างย่อยที่เหมาะสมที่สุด (optimal substructure) ก็ต่อเมื่อปัญหานั้นสามารถหาคำตอบที่เหมาะสมที่สุดอย่างมีประสิทธิภาพ ได้จากคำตอบที่เหมาะสมที่สุดของปัญหาย่อยของมัน คุณสมบัตินี้มีความจำเป็นอย่างยิ่งในการแก้ปัญหาด้วยกำหนดการพลวัตและขั้นตอนวิธีแบบละโมบอย่างมีประสิทธิภาพ ขั้นตอนวิธีแบบละโมบสามารถใช้แก้ปัญหาที่มี โครงสร้างย่อยที่เหมาะสมที่สุด ได้ถ้าหากสามารถพิสูจน์โดยการอุปนัยเชิงคณิตศาสตร์ว่าแต่ละขั้นตอนในการแก้ปัญหานั้นจะสร้างคำตอบที่เหมาะสมที่สุด หากไม่เช่นนั้นปัญหานี้จะกล่าวได้ว่าเป็นปัญหาที่มีการทับซ้อนกันของปัญหาย่อยและสามารถหาผลเฉลยได้ด้วยกำหนดการพลวัต.

วิทยาการคอมพิวเตอร์

วิทยาการคอมพิวเตอร์ หรือ วิทยาศาสตร์คอมพิวเตอร์ (Computer science) เป็นศาสตร์เกี่ยวกับการศึกษาค้นคว้าทฤษฎีการคำนวณสำหรับคอมพิวเตอร์ และทฤษฎีการประมวลผลสารสนเทศ ทั้งด้านซอฟต์แวร์ ฮาร์ดแวร์ และ เครือข่าย ซึ่งวิทยาการคอมพิวเตอร์นั้นประกอบด้วยหลายหัวข้อที่เกี่ยวข้องกับคอมพิวเตอร์ ตั้งแต่ระดับนามธรรม หรือความคิดเชิงทฤษฎี เช่น การวิเคราะห์และสังเคราะห์ขั้นตอนวิธี ไปจนถึงระดับรูปธรรม เช่น ทฤษฎีภาษาโปรแกรม ทฤษฎีการพัฒนาซอฟต์แวร์ ทฤษฎีฮาร์ดแวร์คอมพิวเตอร์ และ ทฤษฎีเครือข่าย ในแง่ของศาสตร์เกี่ยวกับคอมพิวเตอร์นั้น วิทยาการคอมพิวเตอร์เป็นหนึ่งในห้าสาขาวิชาคอมพิวเตอร์ ซึ่งประกอบด้วย สาขาวิทยาการคอมพิวเตอร์ หรือวิทยาศาสตรคอมพิวเตอร์ สาขาวิศวกรรมคอมพิวเตอร์ สาขาวิศวกรรมซอฟต์แวร์ สาขาเทคโนโลยีสารสนเทศ หรือเทคโนโลยีสารสนเทศและการสือสาร และ สาขาคอมพิวเตอร์ธุรกิจ หรือ ระบบสารสนเทศทางธุรก.

กำหนดการพลวัตและวิทยาการคอมพิวเตอร์ · วิทยาการคอมพิวเตอร์และโครงสร้างย่อยที่เหมาะสมที่สุด · ดูเพิ่มเติม »

ปัญหาวิถีสั้นสุด

วิถีสั้นสุดบนกราฟไม่ระบุทิศทางที่ไม่ถ่วงน้ำหนักระหว่างจุดยอด 6 กับ 1 คือ (6, 4, 5, 1) ในทฤษฎีกราฟ ปัญหาวิถีสั้นสุด (shortest path problem)​ เป็นปัญหาที่ต้องการหาวิถีสั้นสุดระหว่างจุดยอด 2 จุดภายในกราฟ กล่าวคือในวิถีสั้นสุดนั้น ผลรวมของน้ำหนักในเส้นเชื่อมแต่ละเส้นรวมกันแล้วน้อยที่สุดในบรรดาวิถีทั้งหมด ตัวอย่างปัญหานี้เช่นการหาวิธีเดินทางจากจุดหนึ่งไปอีกจุดหนึ่งในแผนที่ ในกรณีนี้ จุดยอดแทนด้วยสถานที่ต่างๆ ส่วนเส้นเชื่อมแทนด้วยถนนหรือเส้นทาง และน้ำหนักบนเส้นเชื่อมแทนด้วยเวลาในการเดินทางด้วยถนนหรือเส้นทางนั้น.

กำหนดการพลวัตและปัญหาวิถีสั้นสุด · ปัญหาวิถีสั้นสุดและโครงสร้างย่อยที่เหมาะสมที่สุด · ดูเพิ่มเติม »