กำหนดการพลวัตและขั้นตอนวิธีของฟลอยด์-วอร์แชล

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

ความแตกต่างระหว่าง กำหนดการพลวัตและขั้นตอนวิธีของฟลอยด์-วอร์แชล

กำหนดการพลวัต vs. ขั้นตอนวิธีของฟลอยด์-วอร์แชล

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

ภาษาซีพลัสพลัส

ษาซีพลัสพลัส (C++) เป็นภาษาโปรแกรมคอมพิวเตอร์อเนกประสงค์ มีโครงสร้างภาษาที่มีการจัดชนิดข้อมูลแบบสแตติก (statically typed) และสนับสนุนรูปแบบการเขียนโปรแกรมที่หลากหลาย (multi-paradigm language) ได้แก่ การโปรแกรมเชิงกระบวนคำสั่ง, การนิยามข้อมูล, การโปรแกรมเชิงวัตถุ, และการโปรแกรมแบบเจเนริก (generic programming) ภาษาซีพลัสพลัสเป็นภาษาโปรแกรมเชิงพาณิชย์ที่นิยมมากภาษาหนึ่งนับตั้งแต่ช่วงทศวรรษ 1990 เบียเนอ สเดราสดร็อบ (Bjarne Stroustrup) จากเบลล์แล็บส์ (Bell Labs) เป็นผู้พัฒนาภาษาซีพลัสพลัส (เดิมใช้ชื่อ "C with classes") ในปี ค.ศ. 1983 เพื่อพัฒนาภาษาซีดั้งเดิม สิ่งที่พัฒนาขึ้นเพิ่มเติมนั้นเริ่มจากการเพิ่มเติมการสร้างคลาสจากนั้นก็เพิ่มคุณสมบัติต่างๆ ตามมา ได้แก่ เวอร์ชวลฟังก์ชัน การโอเวอร์โหลดโอเปอเรเตอร์ การสืบทอดหลายสาย เทมเพลต และการจัดการเอกเซพชัน มาตรฐานของภาษาซีพลัสพลัสได้รับการรับรองในปี ค.ศ. 1998 เป็นมาตรฐาน ISO/IEC 14882:1998 เวอร์ชันล่าสุดคือเวอร์ชันในปี ค.ศ. 2014 ซึ่งเป็นมาตรฐาน ISO/IEC 14882:2014 (รู้จักกันในชื่อ C++14).

กำหนดการพลวัตและภาษาซีพลัสพลัส · ขั้นตอนวิธีของฟลอยด์-วอร์แชลและภาษาซีพลัสพลัส · ดูเพิ่มเติม »

ภาษาเพิร์ล

right ภาษาเพิร์ล (Perl) (ย่อมาจาก Practical Extraction and Report Language) เป็นภาษาโปรแกรมแบบไดนามิก พัฒนาโดยนายแลร์รี วอลล์ (Larry Wall) ในปี ค.ศ. 1987 เพื่อใช้งานกับระบบปฏิบัติการยูนิกซ์ ภาษาเพิร์ล นั้นถูกออกแบบมาให้ใช้งานได้ง่าย โครงสร้างของภาษาจึงไม่ซับซ้อน มีลักษณะคล้ายกับภาษาซี นอกจากนี้เพิร์ลยังได้แนวคิดบางอย่างมาจากเชลล์สคริปต์, ภาษา AWK, sed และ Lisp ปัจจุบันเวอร์ชันล่าสุดคือ 5.18.0.

กำหนดการพลวัตและภาษาเพิร์ล · ขั้นตอนวิธีของฟลอยด์-วอร์แชลและภาษาเพิร์ล · ดูเพิ่มเติม »