• โฮมเพจ
  • บทความ
  • ทั่วไป
  • บทนำสู่การเขียนโปรแกรมแบบไดนามิก: ปัญหาย่อยที่ทับซ้อนกัน & โครงสร้างย่อยที่เหมาะสมที่สุด

บทนำสู่การเขียนโปรแกรมแบบไดนามิก: ปัญหาย่อยที่ทับซ้อนกัน & โครงสร้างย่อยที่เหมาะสมที่สุด

เผยแพร่แล้ว: 2021-02-08

สารบัญ

บทนำ

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

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

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

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

การเขียนโปรแกรมแบบไดนามิกมีสองแนวคิด:

  1. ปัญหาย่อยที่ทับซ้อนกัน
  2. โครงสร้างย่อยที่เหมาะสมที่สุด

ปัญหาย่อยที่ทับซ้อนกัน

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

ตรรกะของอนุกรมฟีโบนักชีถูกกำหนดโดย “ฟีโบนักชี(n) = ฟีโบนักชี(n-1) + ฟีโบนักชี(n-2)” และการเรียกใช้ฟังก์ชันนี้อย่างราบรื่นสามารถทำได้โดยใช้โซลูชันแบบเรียกซ้ำ โดยมีตัวพิมพ์พื้นฐานเป็น fibonacci(0)=0 และ fibonacci(1)=1

คงที่สาธารณะ int fibonacci (int n) {
 ถ้า (n== 0 || n== 1 )
 กลับ n;
 ส่งกลับ fibonacci(n -1 )+fibonacci(n -2 );
 }
 โมฆะคงที่สาธารณะหลัก (สตริง [] args){
 System.out.print( “เลขฟีโบนักชีลำดับที่ 4 คือ “ +fibonacci( 4 ));
 }

สมมติว่าเราต้องพิมพ์ตัวเลขฟีโบนักชีที่ 4 จากนั้นทรีเรียกซ้ำจะเป็น

ฟีโบนักชี(4)

/ \

ฟีโบนักชี(3) + ฟีโบนักชี(2)

/ \ / \

ฟีโบนักชี(2) + ฟีโบนักชี(1) ฟีโบนักชี(1) + ฟีโบนักชี(0)

/ \

ฟีโบนักชี(1) + ฟีโบนักชี(0)

โปรดทราบว่า fibonacci(4) เป็นตัวเลขที่ 5 ในอนุกรม fibonacci เพราะเราเริ่มจาก fibonacci(0) ในแผนผังการเรียกซ้ำด้านบน เราจะเห็นว่า fibonacci(2) ซ้ำสองครั้ง เราได้สังเกตการทำซ้ำในทรีการเรียกซ้ำที่มีความสูง 4 ตอนนี้ลองนึกดูว่าเรามีการเรียกซ้ำเป็นจำนวนมหาศาล และต่อมาจะมีต้นไม้เรียกซ้ำที่มีความสูงมาก และจะมีการคำนวณซ้ำกันจำนวนมาก ซึ่งเรียกว่าปัญหาย่อยที่ทับซ้อนกัน

เรามีสองวิธีในการจัดการกับ (i) ตารางนี้ (ii) การท่องจำ

ให้เราเข้าใจพวกเขาโดยเดินผ่านการใช้งานของพวกเขา

ท่องจำ

การแก้ปัญหาฟีโบนักชีโดยใช้วิธีการบันทึกสามารถทำได้ตามที่แสดงด้านล่าง

บันทึก int[] คงที่;
คงที่สาธารณะ int fibonacci (int n) {
ถ้า(บันทึก[n]!=-1)
บันทึกคืน [n];
ถ้า(n==0 || n==1){
บันทึก[n]=n;
กลับ n;
}
บันทึก[n] = ฟีโบนักชี(n-1)+ฟีโบนักชี(n-2);
บันทึกคืน [n];
}
โมฆะคงที่สาธารณะหลัก (สตริง [] args){
บันทึก=ใหม่ int[5];
สำหรับ(int i=0;i<=4;i++)
บันทึก[i]=-1;
System.out.println(“เลขฟีโบนักชีที่ 4 คือ “+ฟีโบนักชี(4));
}

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

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

ตาราง

วิธีนี้ต่างจากวิธีข้างต้นเล็กน้อย การท่องจำเป็นไปตามวิธีแก้ปัญหาแบบเรียกซ้ำเดียวกัน แต่ในการจัดตาราง เราทำตามวิธีแก้ปัญหาแบบวนซ้ำ เรียกอีกอย่างว่าวิธีการจากล่างขึ้นบน ให้เราดูการดำเนินการตามแนวทางจากล่างขึ้นบน

คงที่สาธารณะ int fibonacci (int n) {
 int table[]=ใหม่ int[n+ 1 ];
 สำหรับ (int i= 0 ;i<=n;i++){
 ถ้า (i== 0 || i== 1 )
 ตาราง[ผม]=ผม;
 อื่นๆ {
 table[i]=table[i -1 ]+ตาราง[i --2 ];
 }
 }
 กลับ ตาราง[n];
 }
 โมฆะคงที่สาธารณะหลัก (สตริง [] args){
 System.out.println( “เลขฟีโบนักชีที่ 4 คือ “ + ฟีโบนักชี( 4 ));
 }

ดังที่เรารู้ว่า fibonacci(n)=fibonacci(n-1)+fibonacci(n-2) ในการท่องจำ เราเริ่มต้นด้วยการเรียกฟังก์ชัน fibonacci(4) แล้วเราก็พบว่าเราไม่ได้คำนวณค่าของมัน เราจึง ได้คำนวณค่าของมันแล้วเก็บไว้

สถานการณ์ที่คล้ายคลึงกันจะต้องเผชิญกับการเรียกซ้ำเพิ่มเติมเช่น fibonacci(3), fibonacci(2) ตอนนี้ทำให้การเรียกซ้ำจำนวนมากรออยู่ในกองการเรียกซ้ำ แต่อย่างไรก็ตาม เรากำลังข้ามการทำซ้ำของปัญหาย่อยที่ทับซ้อนกัน

นอกจากนี้เรายังมีวิธีคำนวณ fibonacci จาก 0 ถึง n องค์ประกอบแบบวนซ้ำแล้วส่งคืนองค์ประกอบ fibonacci ที่ n นี่คือสิ่งที่เราได้ดำเนินการในโค้ดด้านบน รหัสนี้มีข้อกำหนดพื้นที่เหมือนกัน O(n)

ชำระเงิน: ทักษะในการเป็นนักพัฒนาเต็มรูปแบบ

โครงสร้างย่อยที่เหมาะสมที่สุด

ในแนวคิดนี้ เราสามารถหาแนวทางแก้ไขปัญหาที่เหมาะสมที่สุดได้ก็ต่อเมื่อเราได้แก้ไขปัญหาย่อยที่เกี่ยวข้องกันอย่างเหมาะสมแล้วเท่านั้น

และตัวอย่างคลาสสิกของแนวคิดนี้คือการพิจารณาการข้ามผ่านระหว่างโหนดในกราฟ

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

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

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

ถ้า n=LCS(มันฝรั่ง รอยสัก) ดังนั้น n=LCS(potat,tatto)+1 (หากอักขระตัวสุดท้ายเหมือนกัน) อื่น n=maximum(LCS(potato,tatto), LCS(potat, tattoo)

คงที่ int lcs (สตริง s1, สตริง s2, int m, int n ){
 int dp[][] = ใหม่ int[m+ 1 ][n+ 1 ];
 สำหรับ (int i= 0 ; i<=m; i++){
 สำหรับ (int j= 0 ; j<=n; j++){
 ถ้า (i == 0 || j == 0 )
 dp[i][j] = 0 ;
 อื่น if (s1.charAt(i -1 ) == s2.charAt(j -1 ))
 dp[i][j] = dp[i -1 ][j -1 ]+ 1 ;
 อื่น
 dp[i][j] = Math.max(dp[i -1 ][j], dp[i][j -1 ]);
 }
 }
 กลับ dp[m][n];
 }
 โมฆะคงที่สาธารณะหลัก (สตริง [] args){
 System.out.println( “ส่วนย่อยของลำดับที่ยาวที่สุดคือ “ +lcs( “มันฝรั่ง” , “รอยสัก” , 6 , 6 ));
 }

ในโค้ดด้านบนนี้ เราได้นำตรรกะของเราไปใช้โดยใช้วิธีการจัดตารางและคำนวณความยาวของลำดับย่อยร่วมที่ยาวที่สุดในทั้งสองสตริง

อ่านเพิ่มเติม: เงินเดือนนักพัฒนาเต็มกองในอินเดีย

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

บทสรุป

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

โดยสรุปแล้ว หลักสูตร Full Stack Developers เป็นผู้เชี่ยวชาญที่มีทักษะสูง ซึ่งสามารถจัดการทุกอย่างที่เกี่ยวข้องกับการพัฒนาเว็บได้ ทักษะ Full Stack Developer เหล่านี้คือสิ่งที่แตกต่างจาก Frontend และ Backend Developers

การเขียนโปรแกรมแบบไดนามิกคืออะไร?

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

ปัญหาย่อยที่ทับซ้อนกันในการเขียนโปรแกรมแบบไดนามิกคืออะไร?

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

โครงสร้างย่อยที่เหมาะสมที่สุดในการเขียนโปรแกรมแบบไดนามิกคืออะไร?

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