กำหนดการพลวัต

บทความนี้เกี่ยวกับกระบวนการแก้ไขปัญหา สำหรับประเภทภาษาโปรแกรมขั้นสูง ดูที่ ภาษาเชิงพลวัต

ในคณิตศาสตร์ วิทยาการคอมพิวเตอร์ และเศรษฐศาสตร์ กำหนดการพลวัต หรือ การเขียนโปรแกรมแบบไดนามิก (อังกฤษ: dynamic programming; ย่อว่า DP) เป็นระเบียบวิธีในการออกแบบขั้นตอนวิธีสำหรับแก้ปัญหาที่สามารถแบ่งออกเป็นปัญหาย่อยได้ โดยจัดเก็บคำตอบของปัญหาย่อยที่เคยคำนวณไว้เพื่อนำกลับมาใช้ใหม่ แทนการคำนวณปัญหาย่อยเดิมซ้ำหลายครั้ง

ปัญหาที่เหมาะกับการใช้DPมักมีปัญหาย่อยที่ทับซ้อนกัน (overlapping subproblems) และมีโครงสร้างย่อยที่เหมาะสมที่สุด (optimal substructure) กล่าวคือ คำตอบของปัญหาใหญ่สามารถสร้างขึ้นจากคำตอบของปัญหาย่อยได้ วิธีนี้ใช้ได้ทั้งการแก้ปัญหาแบบบนลงล่าง (top-down) ซึ่งมักใช้ร่วมกับการจำ (memoization) และการแก้ปัญหาแบบล่างขึ้นบน (bottom-up) ซึ่งคำนวณคำตอบของปัญหาย่อยตามลำดับจากขนาดเล็กไปใหญ่

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

ประวัติ

จุดกำเนิดในทฤษฎีการตัดสินใจ

ก่อนคริสต์ทศวรรษ 1950 นักคณิตศาสตร์ใช้ความสัมพันธ์เวียนเกิด (recurrence relation) การคำนวณย้อนหลัง และแคลคูลัสของการแปรผัน (calculus of variations) แก้ปัญหาที่ประกอบด้วยการตัดสินใจหลายขั้นอยู่แล้ว อย่างไรก็ตาม วิธีเหล่านี้ยังไม่ได้รวมกันเป็นทฤษฎีทั่วไปสำหรับปัญหาที่การตัดสินใจในขั้นหนึ่งเปลี่ยนแปลงทางเลือกที่มีอยู่ในขั้นถัดไป ผลงานสำคัญของริชาร์ด เบลล์แมน (Richard Bellman) จึงไม่ใช่เพียงการเสนอสูตรเวียนเกิดสูตรใดสูตรหนึ่ง แต่เป็นการวางกรอบทั่วไปสำหรับอธิบายและแก้ กระบวนการตัดสินใจหลายขั้น (multistage decision process)

เบลล์แมนเล่าย้อนหลังว่าเขาเริ่มศึกษาปัญหาการตัดสินใจหลายขั้นระหว่างทำงานที่แรนด์คอร์ปอเรชัน (RAND Corporation) ในฤดูร้อน ค.ศ. 1949 ตามคำแนะนำของเอ็ด แพกซ์สัน (Ed Paxson) ต่อมาในฤดูใบไม้ร่วง ค.ศ. 1950 เขาเริ่มใช้ชื่อ ไดนามิกโปรแกรมมิง (dynamic programming) สำหรับแนวคิดดังกล่าว คำว่า โปรแกรมมิง ในที่นี้มิได้หมายถึงการเขียนโปรแกรมคอมพิวเตอร์ แต่ใช้ในความหมายของการจัดทำแผนหรือการกำหนดชุดการตัดสินใจ เช่นเดียวกับคำว่ากำหนดการเชิงเส้น (linear programming) ส่วนคำว่า ไดนามิก สื่อว่าปัญหามีหลายขั้นและเปลี่ยนแปลงไปตามเวลา

เบลล์แมนตีพิมพ์บทความเรื่อง “On the Theory of Dynamic Programming” ใน ค.ศ. 1952 ซึ่งเป็นผลงานตีพิมพ์ระยะแรกที่วางแนวคิดของ DP ในรูปคณิตศาสตร์ ในปีถัดมา รายงานของแรนด์เรื่อง An Introduction to the Theory of Dynamic Programming อธิบายDP ว่าเป็นทฤษฎีคณิตศาสตร์สำหรับกระบวนการหลายขั้น ซึ่งผลของการดำเนินการก่อนหน้าสามารถนำมาใช้กำหนดการดำเนินการในอนาคตได้ รายงานดังกล่าวครอบคลุมทั้งกระบวนการแบบกำหนดแน่นอน (deterministic process) และกระบวนการเชิงเฟ้นสุ่ม (stochastic process)

ใน ค.ศ. 1954 เบลล์แมนเผยแพร่บทความสำรวจ “The Theory of Dynamic Programming” ซึ่งจัดระบบแนวคิดพื้นฐาน การสร้างสมการเชิงฟังก์ชัน (functional equation) และการประยุกต์กับปัญหาหลายขั้น ต่อมา หนังสือ Dynamic Programming ค.ศ. 1957 ได้รวบรวมทฤษฎีดังกล่าวอย่างเป็นระบบ ทั้งปัญหาการจัดสรรทรัพยากร การควบคุม สินค้าคงคลัง เกมหลายขั้น กระบวนการตัดสินใจมาร์คอฟ และความสัมพันธ์กับแคลคูลัสของการแปรผัน หนังสือเล่มนี้ทำให้ DP กลายเป็นสาขาสำคัญของการวิจัยดำเนินงาน (operations research) และทฤษฎีการควบคุม (control theory)

หลักภาวะเหมาะที่สุดและสมการเบลล์แมน

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

เบลล์แมนแทน “คำตอบที่ดีที่สุดนับจากสถานะปัจจุบันไปจนจบ” ด้วยฟังก์ชันค่า (value function) ให้ $V_{t}(s)$ เป็นต้นทุนต่ำที่สุดที่ยังเหลืออยู่ เมื่อระบบอยู่ในสถานะ $s$ ณ ขั้นที่ $t$ ถ้าเลือกการกระทำ $a$ แล้วเสียต้นทุนทันที $c_{t}(s,a)$ และเปลี่ยนไปเป็นสถานะ $T(s,a)$ จะเขียนความสัมพันธ์ได้ว่า

$V_{t}(s)=\min _{a\in A(s)}\left\{c_{t}(s,a)+V_{t+1}{\bigl (}T(s,a){\bigr )}\right\}$

โดย $A(s)$ คือชุดการกระทำที่เลือกได้จากสถานะ $s$ สูตรนี้เรียกโดยทั่วไปว่าสมการเบลล์แมน (Bellman equation) ความหมายอย่างไม่เป็นทางการคือ

ค่าที่ดีที่สุดจากจุดปัจจุบัน = ต้นทุนของการตัดสินใจครั้งนี้ + ค่าที่ดีที่สุดของปัญหาที่เหลือ

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

ตัวอย่างอย่างง่าย สมมุติว่าต้องเดินทางจาก ก ไป ง โดยมีเส้นทางและระยะทางดังนี้

• ก → ข มีระยะทาง 4
• ก → ค มีระยะทาง 2
• ข → ง มีระยะทาง 3
• ค → ง มีระยะทาง 6

เริ่มจากปลายทาง จะได้ $V({\text{ง}})=0$ เพราะเมื่อถึง ง แล้วไม่ต้องเดินทางต่อ จากนั้นคำนวณย้อนกลับเป็น

$V({\text{ข}})=3+V({\text{ง}})=3$

$V({\text{ค}})=6+V({\text{ง}})=6$

$V({\text{ก}})=\min\{4+V({\text{ข}}),\,2+V({\text{ค}})\}=\min\{7,8\}=7$

ดังนั้นเส้นทางที่สั้นที่สุดคือ ก → ข → ง มีระยะทางรวม 7 จุดสำคัญคือ เมื่อคำนวณ $V({\text{ข}})$ หรือ $V({\text{ค}})$ แล้ว สามารถเก็บค่านั้นไว้และนำกลับมาใช้ โดยไม่ต้องแก้ปัญหาเดิมซ้ำอีก

การแพร่เข้าสู่วิทยาการคอมพิวเตอร์

ในบริบทดั้งเดิม DP เป็นวิธีทางคณิตศาสตร์สำหรับการตัดสินใจและการหาค่าเหมาะที่สุด ต่อมานักวิทยาการคอมพิวเตอร์นำแนวคิดเดียวกันมาใช้ออกแบบขั้นตอนวิธี โดยเรียกปัญหาที่คำตอบเหมาะที่สุดสามารถประกอบขึ้นจากคำตอบเหมาะที่สุดของปัญหาย่อยว่า มี โครงสร้างย่อยเหมาะที่สุด (optimal substructure) และเรียกกรณีที่ปัญหาย่อยเดิมปรากฏซ้ำหลายครั้งว่า มี ปัญหาย่อยทับซ้อน (overlapping subproblems)

หากใช้การเรียกซ้ำธรรมดา ปัญหาย่อยเดียวกันอาจถูกคำนวณซ้ำเป็นจำนวนมาก DP จึงเก็บคำตอบของแต่ละปัญหาย่อยไว้ การดำเนินการแบบบนลงล่าง (top-down) ที่เก็บผลของการเรียกซ้ำเรียกว่า การจำ (memoization) ส่วนการดำเนินการแบบล่างขึ้นบน (bottom-up) ที่คำนวณจากปัญหาเล็กไปหาปัญหาใหญ่เรียกว่า การจัดตาราง (tabulation) ทั้งสองแบบอาศัยความสัมพันธ์เวียนเกิดเดียวกัน ต่างกันที่ลำดับการคำนวณและการจัดเก็บผลลัพธ์

ใน ค.ศ. 1957 เบลล์แมนเชื่อมDP กับกระบวนการตัดสินใจมาร์คอฟ (Markov decision process) ซึ่งอธิบายการตัดสินใจภายใต้ความไม่แน่นอนโดยใช้สถานะ การกระทำ ความน่าจะเป็นของการเปลี่ยนสถานะ และผลตอบแทน กรอบนี้ต่อมากลายเป็นพื้นฐานของการควบคุมเชิงเฟ้นสุ่ม (stochastic control) การวางแผนทางเศรษฐศาสตร์ และการเรียนรู้แบบเสริมกำลัง (reinforcement learning)

ใน ค.ศ. 1962 เบลล์แมนเสนอวิธีDP สำหรับปัญหาพนักงานขายเดินทาง (travelling salesman problem) ในปีเดียวกัน ไมเคิล เฮลด์ (Michael Held) และริชาร์ด คาร์ป (Richard Karp) เผยแพร่วิธีที่ได้ผลอย่างเป็นอิสระ โดยกำหนดสถานะจากเซตของเมืองที่เยี่ยมชมแล้วและเมืองปลายทางปัจจุบัน วิธีดังกล่าวยังใช้เวลาแบบเลขชี้กำลัง แต่ลดจำนวนกรณีจากการไล่เรียงเส้นทางทุกแบบประมาณ $n!$ เหลือประมาณ $O(n^{2}2^{n})$ แสดงให้เห็นว่าDP อาจช่วยลดขนาดการค้นหาได้อย่างมาก แม้ไม่ทำให้ทุกปัญหากลายเป็นปัญหาที่แก้ได้ในเวลาพหุนามก็ตาม

แนวคิดนี้แพร่ไปยังสาขาอื่นอย่างรวดเร็ว ใน ค.ศ. 1967 แอนดรูว์ วิเทอร์บี (Andrew Viterbi) เสนอขั้นตอนวิธีวิเทอร์บี (Viterbi algorithm) สำหรับการถอดรหัสรหัสคอนโวลูชัน (convolutional code) โดยเก็บเส้นทางบางส่วนที่ดีที่สุดสำหรับแต่ละสถานะของระบบ ต่อมาขั้นตอนวิธีนี้ถูกใช้ในโทรคมนาคม การรู้จำเสียง และแบบจำลองมาร์คอฟซ่อนเร้น (hidden Markov model)

ใน ค.ศ. 1970 ซอล นีเดิลแมน (Saul Needleman) และคริสเตียน วุนช์ (Christian Wunsch) เผยแพร่ขั้นตอนวิธีนีเดิลแมน–วุนช์ (Needleman–Wunsch algorithm) สำหรับเปรียบเทียบลำดับกรดอะมิโนของโปรตีน โดยแทนปัญหาย่อยด้วยช่องต่าง ๆ ในตารางสองมิติและคำนวณค่าที่ดีที่สุดจากช่องข้างเคียง งานนี้ทำให้DP กลายเป็นเครื่องมือพื้นฐานของชีวสารสนเทศศาสตร์ (bioinformatics) โดยเฉพาะการจัดแนวลำดับดีเอ็นเอ อาร์เอ็นเอ และโปรตีน

ข้อจำกัดและพัฒนาการสมัยใหม่

ประสิทธิภาพของDP ขึ้นอยู่กับจำนวนสถานะที่ต้องคำนวณ หากระบบมีตัวแปรสถานะจำนวนมาก จำนวนสถานะอาจเพิ่มขึ้นอย่างรวดเร็ว เช่น ถ้ามีตัวแปร $d$ ตัว และแบ่งค่าของแต่ละตัวออกเป็น $m$ ระดับ ตารางอาจมีขนาดถึง $m^{d}$ เบลล์แมนเรียกปัญหานี้ว่า คำสาปของมิติ (curse of dimensionality) ข้อจำกัดดังกล่าวนำไปสู่การพัฒนาวิธีประมาณค่าฟังก์ชันค่า การรวมสถานะ และDP โดยประมาณ (approximate dynamic programming)

ตั้งแต่คริสต์ทศวรรษ 1980 เป็นต้นมา สมการเบลล์แมนกลายเป็นพื้นฐานส่วนหนึ่งของการเรียนรู้แบบเสริมกำลัง โดยระบบเรียนรู้ค่าของสถานะหรือการกระทำจากประสบการณ์ แทนที่จะคำนวณจากแบบจำลองที่ทราบล่วงหน้า ตัวอย่างสำคัญคือคิวเลิร์นนิง (Q-learning) ซึ่งคริสโตเฟอร์ วัตคินส์ (Christopher Watkins) และปีเตอร์ เดย์ยัน (Peter Dayan) อธิบายว่าเป็นวิธีเพิ่มค่าทีละขั้นสำหรับDP และพิสูจน์การลู่เข้าภายใต้เงื่อนไขที่กำหนดใน ค.ศ. 1992 DP จึงยังคงเป็นรากฐานร่วมของการหาค่าเหมาะที่สุด ทฤษฎีการควบคุม ปัญญาประดิษฐ์ เศรษฐศาสตร์ และขั้นตอนวิธีสมัยใหม่

ภาพรวม

การหาวิถีสั้นสุดภายในกราฟโดยใช้คุณสมบัติโครงสร้างย่อยที่เหมาะสมที่สุด เส้นตรงแสดงถึงเส้นเชื่อมของกราฟ เส้นโค้งแสดงถึงวิถีสั้นสุดระหว่างจุดยอด เส้นหนาแสดงถึงวิถีสั้นสุดจากจุดยอดเริ่มต้นถึงจุดยอดเป้าหมาย

DP ในการเขียนโปรแกรมคอมพิวเตอร์

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

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

ตัวอย่างเช่น กำหนดกราฟ $G=(V,E)$ และให้ $p$ เป็นเส้นทางสั้นที่สุด (shortest path) จากจุดยอด $u$ ไปยังจุดยอด $v$ ถ้าจุดยอด $w$ อยู่บนเส้นทาง $p$ แล้ว ส่วนของเส้นทางจาก $u$ ไปยัง $w$ และส่วนจาก $w$ ไปยัง $v$ จะต้องเป็นเส้นทางสั้นที่สุดระหว่างจุดยอดคู่ดังกล่าวด้วย มิฉะนั้นย่อมสามารถแทนส่วนใดส่วนหนึ่งด้วยเส้นทางที่สั้นกว่า และทำให้เส้นทางจาก $u$ ไปยัง $v$ สั้นลงได้ ดังนั้นจึงมีความสัมพันธ์ว่า

$\delta (u,v)=\delta (u,w)+\delta (w,v)$

เมื่อ $w$ อยู่บนเส้นทางสั้นที่สุดจาก $u$ ไปยัง $v$ แนวคิดเรื่องโครงสร้างย่อยนี้เป็นพื้นฐานของขั้นตอนวิธีหาเส้นทางสั้นที่สุดหลายขั้นตอนวิธี เช่น ขั้นตอนวิธีเบลล์แมน–ฟอร์ดและขั้นตอนวิธีฟลอยด์–วอร์แชลล์ แม้ขั้นตอนวิธีทั้งสองจะกำหนดปัญหาย่อยและความสัมพันธ์เวียนเกิดแตกต่างกันก็ตาม

DP แตกต่างจากการแบ่งแยกและเอาชนะ (divide and conquer) ตรงที่ปัญหาย่อยของDP มักทับซ้อนกัน กล่าวคือ ปัญหาย่อยเดียวกันปรากฏซ้ำในหลายส่วนของการคำนวณ ส่วนขั้นตอนวิธีแบบแบ่งแยกและเอาชนะ เช่น ควิกซอร์ต (quicksort) และการเรียงลำดับแบบผสาน (merge sort) มักแบ่งข้อมูลออกเป็นปัญหาย่อยที่แยกจากกัน จึงไม่จำเป็นต้องบันทึกคำตอบเพื่อหลีกเลี่ยงการแก้ปัญหาย่อยเดิมซ้ำ

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

ตัวอย่างทั่วไปของปัญหาย่อยที่ทับซ้อนกันคือการคำนวณจำนวนฟีโบนัชชี ซึ่งกำหนดด้วยความสัมพันธ์เวียนเกิด

$F_{n}=F_{n-1}+F_{n-2}$

โดยมีกรณีฐาน $F_{0}=0$ และ $F_{1}=1$ ในการคำนวณ $F_{5}$ จะต้องคำนวณทั้ง $F_{4}$ และ $F_{3}$ แต่การคำนวณ $F_{4}$ ก็ต้องคำนวณ $F_{3}$ อีกครั้งหนึ่ง ดังนั้น $F_{3}$ จึงเป็นปัญหาย่อยที่ทับซ้อนกัน

หากเขียนฟังก์ชันเวียนเกิดโดยตรง ปัญหาย่อยเดียวกันจะถูกคำนวณซ้ำจำนวนมาก และจำนวนการเรียกฟังก์ชันจะเติบโตแบบเลขชี้กำลังตามค่า $n$ แต่ถ้าบันทึกค่าของ $F_{0},F_{1},\ldots ,F_{n}$ ไว้ แต่ละค่าจะต้องคำนวณเพียงครั้งเดียว ทำให้เวลาในการคำนวณลดลงเหลือ $O(n)$

การคำนวณจำนวนฟีโบนัชชีโดยรวมการปรากฏซ้ำของปัญหาย่อยเดียวกันไว้เป็นสถานะเดียว

การนำ DP ไปใช้ในโปรแกรมมีสองแนวทางหลัก ได้แก่

• แบบบนลงล่าง (top-down) เริ่มจากปัญหาเดิมแล้วใช้การเรียกซ้ำ (recursion) เพื่อแก้ปัญหาย่อย เมื่อคำนวณคำตอบของปัญหาย่อยครั้งแรกแล้ว จะบันทึกคำตอบไว้ในตารางหรือแคช หากพบปัญหาย่อยเดิมอีกครั้ง โปรแกรมจะอ่านคำตอบที่บันทึกไว้แทนการคำนวณใหม่ วิธีบันทึกผลของฟังก์ชันตามอาร์กิวเมนต์ที่ได้รับเรียกว่า เมโมอิเซชัน (memoization)

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

ตัวอย่างเช่น การคำนวณจำนวนฟีโบนัชชีแบบล่างขึ้นบนเริ่มจาก $F_{0}$ และ $F_{1}$ แล้วคำนวณ $F_{2},F_{3},\ldots ,F_{n}$ ตามลำดับ เนื่องจากการคำนวณค่าใหม่ต้องใช้เพียงสองค่าก่อนหน้า จึงสามารถลดหน่วยความจำเสริมจาก $O(n)$ เหลือ $O(1)$ ได้โดยเก็บไว้เฉพาะสองค่าล่าสุด

ภาษาโปรแกรมและไลบรารีบางชนิดมีเครื่องมือช่วยทำเมโมอิเซชันหรือการจัดตาราง เช่น มอดูล Memoize ของภาษาเพิร์ล เดคอเรเตอร์ functools.cache และ functools.lru_cache ของภาษาไพทอน และการจัดตาราง (tabling) ในระบบภาษาโปรล็อกบางระบบ อย่างไรก็ตาม เครื่องมือเหล่านี้โดยทั่วไปต้องได้รับการประกาศหรือเรียกใช้โดยผู้เขียนโปรแกรม มิได้ทำเมโมอิเซชันให้กับฟังก์ชันทุกฟังก์ชันโดยอัตโนมัติ

ในการเขียนโปรแกรม ภาษาโปรแกรมและระบบบางชนิดมีเครื่องมือช่วยทำเมโมอิเซชัน (memoization) โดยผู้เขียนโปรแกรมต้องประกาศหรือเรียกใช้เครื่องมือนั้นกับฟังก์ชันที่ต้องการ ตัวอย่างเช่น ระบบภาษาโปรล็อกบางระบบอย่างเอสดับเบิลยูไอ-โปรล็อก (SWI-Prolog) รองรับการจัดตาราง (tabling) ซึ่งบันทึกคำตอบของภาคแสดง (predicate) และนำกลับมาใช้เพื่อหลีกเลี่ยงการคำนวณซ้ำ ส่วนภาษาเจมีตัวดำเนินการ M. ซึ่งเก็บอาร์กิวเมนต์และผลลัพธ์ของฟังก์ชันไว้เพื่อนำกลับมาใช้ นอกจากนี้ ไลบรารีมาตรฐานของบางภาษายังมีเครื่องมือสำหรับเมโมอิเซชัน เช่น มอดูล Memoize ของภาษาเพิร์ล และเดคอเรเตอร์ (decorator) functools.cache กับ functools.lru_cache ของภาษาไพทอน เครื่องมือเหล่านี้ไม่ได้ทำเมโมอิเซชันให้แก่ฟังก์ชันทั้งหมดโดยอัตโนมัติ แต่ต้องได้รับการระบุหรือเรียกใช้อย่างชัดเจนในโปรแกรม