© Jirsak/Shutterstock.com
เมื่อคุณจัดการกับชุดข้อมูล ชุดข้อมูลเหล่านั้นมักจะอยู่ในรูปของอาร์เรย์ และอาร์เรย์เหล่านี้มักจะอยู่ติดกัน ซึ่งหมายความว่าจะไม่มีการ “แบ่ง” ระหว่างค่าข้อมูล — ค่าเหล่านี้จะถูกจัดเก็บไว้ในหน่วยความจำบล็อกเดียว อาร์เรย์ประเภทนี้เป็นจุดศูนย์กลางเมื่อพูดถึงปัญหา Subarray สูงสุดแบบคลาสสิก แม้ว่าจะมีหลายวิธีในการแก้ไขปัญหานี้ แต่วิธีที่ดีที่สุดวิธีหนึ่งในการจัดการกับปัญหานี้คือการใช้อัลกอริทึมของ Kadane หากคุณสงสัยว่าจะใช้อัลกอริทึมนี้อย่างไร และเหมาะกับขอบเขตของการเขียนโปรแกรมแบบไดนามิกอย่างไร คุณมาถูกที่แล้ว มาร่วมสำรวจอัลกอริทึมของ Kadane และวิธีการใช้เพื่อแก้ปัญหา Subarray สูงสุด
ปัญหา Subarray สูงสุดคืออะไร
ปัญหา Subarray สูงสุดเรียกอีกอย่างว่า Maximum ปัญหา Subarray ที่ต่อเนื่องกัน พูดง่ายๆ งานที่โจทย์นำเสนอคือหาค่าสูงสุดของแถบย่อยที่อยู่ติดกันภายในอาร์เรย์ arr[] ที่มีขนาด N นั่นคือหาผลรวมสูงสุดที่เป็นไปได้ของการบวกจำนวนเต็มในอาร์เรย์โดยไม่มีการเว้นวรรค ตัวอย่างเช่น หากเราใช้อาร์เรย์ [4,-1, 2, 1] ผลรวมสูงสุดจะเป็นผลรวมของจำนวนเต็มทั้งหมด หรือ 6
สำหรับชุดข้อมูลขนาดเล็ก นี่อาจเป็นงานที่ค่อนข้างง่าย และสามารถแก้ไขได้โดยง่ายโดยใช้สิ่งที่เรียกว่า “วิธีเดรัจฉาน” โดยทั่วไปหมายถึงการใช้การคำนวณที่ง่ายที่สุดโดยคำนึงถึงประสิทธิภาพโดยรวม ด้วยวิธีนี้ เราสามารถเริ่มต้นจากดัชนีที่ 0 และคำนวณผลรวมของทุก subarray ที่เป็นไปได้ โดยเริ่มจากองค์ประกอบ A[0] เราสามารถคำนวณผลรวมของ subarray เหล่านี้โดยเริ่มจาก A[1] และต่อเนื่องไปจนถึง A[n-1] โดยที่ n คือขนาดอาร์เรย์ ถ้าเราเรียกผลรวมสูงสุดของ subarray ว่า local_maximum ที่ดัชนี i เราสามารถคำนวณค่าเหล่านี้ทั้งหมดแล้วจบด้วยการหาค่าสูงสุดของ local_maximums ซึ่งจะให้ผลรวมมากที่สุดเท่าที่จะเป็นไปได้ ซึ่งสามารถอธิบายได้ว่าเป็น global_maximum
อย่างที่คุณคาดไว้ วิธีนี้อาจใช้ได้ดีพอสมควรสำหรับอาร์เรย์ขนาดเล็กมาก แต่ค่อนข้างไม่มีประสิทธิภาพสำหรับชุดข้อมูลขนาดใหญ่ ความซับซ้อนของเวลาคือกำลังสองหรือ O(n2) หมายความว่าความซับซ้อนนั้นเพิ่มขึ้นอย่างรวดเร็วเมื่อขนาดอินพุตเพิ่มขึ้น ดังนั้นเราจึงต้องการกระบวนการที่มีประสิทธิภาพและสวยงามมากขึ้น นี่คือที่มาของการเขียนโปรแกรมแบบไดนามิก
การเขียนโปรแกรมแบบไดนามิกสามารถช่วยได้อย่างไร
การเขียนโปรแกรมแบบไดนามิกเป็นแนวทางในการแก้ปัญหาที่ซับซ้อนโดยการลดปัญหาเหล่านี้ลงในกลุ่มปัญหาที่ง่ายกว่า ปัญหาที่ง่ายขึ้นเหล่านี้ได้รับการแก้ไขแล้ว และวิธีแก้ไขจะถูกจัดเก็บไว้ในโครงสร้างข้อมูล เช่น อาร์เรย์ โซลูชันเหล่านี้สามารถเข้าถึงได้เมื่อเรากำลังแก้ปัญหาประเภทเดียวกัน หลีกเลี่ยงความจำเป็นในการแก้ปัญหาซ้ำและเร่งความเร็วการคำนวณโดยรวม
จะเป็นประโยชน์อย่างมากหากเราสามารถนำหลักการไปใช้ได้ ของการเขียนโปรแกรมแบบไดนามิกไปยังปัญหา Subarray สูงสุดของเรา โชคดีที่เราทำได้ และนั่นคือสิ่งที่อัลกอริทึมของ Kadane กำหนดให้ทำ มาเริ่มกันเลย
การเขียนโปรแกรมไดนามิกเป็นแนวทางในการแก้ปัญหาที่ซับซ้อนโดยการลดปัญหาเหล่านั้นให้เป็นปัญหาที่ง่ายกว่า
©hafakot/Shutterstock.com
อัลกอริทึมของ Kadane
ดังที่ได้กล่าวไว้สั้นๆ อัลกอริทึมของ Kadane ใช้การเขียนโปรแกรมแบบไดนามิกเพื่อคำนวณวิธีแก้ปัญหาที่มีประสิทธิภาพสูงสุดสำหรับปัญหา Subarray สูงสุด อัลกอริทึมทำงานโดยจัดเก็บผลรวมสูงสุดของแถบย่อยที่อยู่ติดกันที่ดัชนีปัจจุบัน จากนั้นจึงนำไปเปรียบเทียบกับผลรวมสูงสุดที่พบจนถึงตอนนี้ หากมีค่ามากกว่าผลรวมสูงสุดที่พบจนถึงตอนนี้ ค่านี้จะอัปเดตด้วยค่าใหม่
ข้อได้เปรียบที่สำคัญของอัลกอริทึมของ Kadane คือความเร็ว ซึ่งแสดงไว้ในความซับซ้อนของเวลาเป็น O(n) ซึ่งหมายความว่าความซับซ้อนของเวลาจะเพิ่มขึ้นเป็นเชิงเส้นตามขนาดอินพุตที่เพิ่มขึ้น ซึ่งดีกว่าความซับซ้อนของเวลากำลังสองของวิธีการเดรัจฉานมาก ความซับซ้อนของพื้นที่ก็ดีเช่นกัน เนื่องจากอัลกอริทึมมีความเสถียร ซึ่งหมายความว่าต้องใช้หน่วยความจำในจำนวนที่คงที่ในระหว่างกระบวนการ เนื่องจากจำเป็นต้องจัดเก็บตัวแปรเพียงสองตัว (เหล่านี้คือ global_maximum และ local_maximum)
อัลกอริทึมของ Kadane ในการดำเนินการ
ลองนำอาร์เรย์ [4,-1, 2, 1] อีกครั้ง หากเรากลับค่า brute force approac และเริ่มต้นด้วยองค์ประกอบ A[n] (ในกรณีนี้คือ 1) เราสามารถคำนวณผลรวมของทุก subarray ที่เป็นไปได้ จากนั้นดำเนินการต่อด้วย A[n-1], A[n-2] จนกว่าเราจะเสร็จสิ้นทั้งหมด
เมื่อพิจารณาจากสององค์ประกอบสุดท้าย A[3] และ A[4] เราจะเห็นว่า local_maximum คือ 5 และ 6 ตามลำดับ แต่ถ้าเราทราบ local_maximum[3] เราก็ไม่จำเป็นต้องคำนวณผลรวมของ subarray ทั้งหมดสำหรับ A[4] เนื่องจากเราทราบผลลัพธ์จาก A[3] และ local_maximum[3] แล้ว เราต้องการเพียงแค่ตรวจสอบ subarrays สองอัน อันที่มี A[4] เพียงอย่างเดียวและผลรวมของ A[4] และ local_maximum[3] ในกรณีนี้ ค่านี้จะเป็น A[4} + local_maximum[3] ซึ่งเท่ากับ 6 นี่เป็นคำตอบเดียวกับที่เราได้รับหากเราคำนวณผลรวมของ subarray ทั้งหมดสำหรับ A[4]
หลักการนี้ คือสิ่งที่สนับสนุนอัลกอริทึมของ Kadane และสามารถอธิบายได้ดังนี้:
local_maximum[i]=max(A[i], A[i] + local_maximum[i-1])
หรืออีกนัยหนึ่ง local_maximum ที่ดัชนี i คือค่าสูงสุดของ A[i] และผลรวมของ A[i] และ local_maximum ที่ดัชนี i-1
ดังนั้น เราต้องหาค่าสูงสุดของ A[i] เท่านั้น และ A[i] + local_maximum[i-1] เพื่อหาค่าสูงสุดในแต่ละดัชนี i ดังนั้นเราจึงจำเป็นต้องค้นหาแต่ละ local_maximum เพื่อค้นหา subarray สูงสุด นี่เป็นวิธีที่มีประสิทธิภาพมากกว่าในการจัดการกับปัญหา Subarray สูงสุด
การทำงานของอัลกอริทึมของ Kadane
มาดูขั้นตอนที่อัลกอริทึมของ Kadane ใช้ในการคำนวณ Subarray สูงสุด
อัลกอริทึมต้องการเพียงหนึ่งลูป วนซ้ำจาก i[0[ ถึง i[n-1] local_maximum[i] จะถูกคำนวณสำหรับแต่ละองค์ประกอบ ซึ่งขึ้นอยู่กับ local_maximum[i-1] การเปรียบเทียบ local_maxium ถึง global_maximum หากมีค่ามากกว่า global_maximum จะได้รับการอัปเดต สิ่งนี้จะเกิดขึ้นซ้ำสำหรับแต่ละดัชนีจนกว่าจะพบผลรวมที่ใหญ่ที่สุดของแถบย่อยที่อยู่ติดกัน
การนำอัลกอริทึมของ Kadane ไปใช้
เพื่อแสดงให้เห็นว่าสามารถนำอัลกอริทึมของ Kadane ไปใช้งานได้อย่างไร เราจะใช้ Python ในสภาพแวดล้อม Spyder มาดูกันว่าโค้ดทำงานอย่างไรในทางปฏิบัติ
จาก sys import maxsize def SolveMaxSubArrayProblem(input): n=len(input) globalMaxSum=-maxsize-1 localMaxSum=0 for i in range(0, n): localMaxSum=สูงสุด (อินพุต [i], อินพุต [i] + localMaxSum) if (localMaxSum>globalMaxSum): globalMaxSum=localMaxSum ส่งคืน globalMaxSum if_name_==”_main_”อินพุต=[1,-2, 5,-3, 4,-1, 6] result=SolveMaxSubArrayProblem(input) print(result) 11
ประการแรก การเยื้องที่เหมาะสมใน Python เป็นกุญแจสำคัญในการรันโค้ดอย่างถูกต้อง ในการเริ่มต้น เรากำลังนำเข้าฟังก์ชัน “maxsize” ซึ่งใช้เพื่อค้นหาค่าสูงสุด
ถัดไป เรากำลังกำหนด “solveMaxSubArrayProblem” เป็นฟังก์ชันของอาร์เรย์ “อินพุต” ที่มีความยาว n โดย globalMaxSum เริ่มต้นเป็นค่าจำนวนเต็มขั้นต่ำ สิ่งนี้ทำเพื่อให้แน่ใจว่าผลรวมของ subarray ที่คำนวณได้จะมากกว่าค่านี้
local_maximum จะแปรผันและถูกตั้งค่าเริ่มต้นเป็น 0
“for” หมายถึงลูป ซึ่งใช้ในการวนซ้ำผ่านองค์ประกอบอาร์เรย์แต่ละรายการ
สำหรับการวนซ้ำแต่ละครั้ง”localMaxSum”จะได้รับการอัปเดตเป็น localMaxSum ขององค์ประกอบปัจจุบันหรือองค์ประกอบบวกกับ localMaxSum ก่อนหน้า
หาก localMaxSum มีค่ามากกว่า globalMaxSum ปัจจุบัน ค่าหลังจะได้รับการอัปเดตเพื่อแสดงการเปลี่ยนแปลงนี้
เมื่อกระบวนการวนซ้ำเสร็จสิ้น globalMaxSum จะเท่ากับค่าสูงสุดของแถบย่อยที่อยู่ติดกัน และผลลัพธ์นี้จะถูกส่งกลับ
ประการสุดท้าย “if __name__==“”__main__”” ทดสอบฟังก์ชันโดยสร้างอาร์เรย์ที่ตามมาและใช้ฟังก์ชันที่กำหนดไว้ จากนั้นพิมพ์ผลลัพธ์
สำหรับอาร์เรย์ [1 ,-2, 5,-3, 4,-1, 6] แถบย่อยที่อยู่ติดกันสูงสุดมีผลรวมเป็น 11
©”TNGD”.com
สรุปผล
เราได้กล่าวถึงหลักการเบื้องหลังการเขียนโปรแกรมแบบไดนามิก เรายังแสดงให้เห็นว่าอัลกอริทึมของ Kadane ใช้สิ่งนี้เพื่อแก้ปัญหา Maximum Subarray อย่างไร ข้อดีของสิ่งนี้ถูกอธิบายไว้ อัลกอริทึมของ Kadane ค่อนข้างง่ายในการทำความเข้าใจและใช้งาน โดยมีความซับซ้อนของเวลาและพื้นที่ที่มีประสิทธิภาพ เมื่อพูดถึงการแก้ปัญหาค่า Subarray สูงสุด อัลกอริทึมของ Kadane เป็นวิธีที่เร็วที่สุดวิธีหนึ่ง
ถัดไป…
อัลกอริทึมของ Kadane: แนวทางที่มีประสิทธิภาพในการแก้ปัญหา Subarray สูงสุด , อธิบายด้วยรูปภาพ FAQs (คำถามที่พบบ่อย)
subarray คืออะไร
subarray เป็นส่วนหนึ่งของ array ที่ไม่มีการขัดจังหวะ กล่าวคือ ไม่มีการหยุดพัก ระหว่างจำนวนเต็ม สิ่งนี้อธิบายว่าอยู่ติดกัน subarray สามารถประกอบด้วยหนึ่งองค์ประกอบ ส่วนใหญ่จะใช้เมื่อทำงานกับชุดข้อมูล เพื่อทำสิ่งต่างๆ เช่น ค้นหา subarray สูงสุดที่อยู่ติดกัน
การเขียนโปรแกรมแบบไดนามิกคืออะไร
การเขียนโปรแกรมแบบไดนามิกหมายถึง ไปจนถึงเทคนิคการแก้ปัญหาที่ซับซ้อนด้วยการแตกย่อยให้เป็นเรื่องง่ายๆ โซลูชันย่อยแต่ละรายการจำเป็นต้องคำนวณเพียงครั้งเดียว และเก็บไว้ในแคชชั่วคราว ดังนั้นจึงหลีกเลี่ยงการคำนวณที่ซ้ำซ้อน ดังนั้นกระบวนการต่างๆ จึงเร่งความเร็วขึ้นอย่างมาก การเขียนโปรแกรมแบบไดนามิกมักใช้เพื่อเพิ่มประสิทธิภาพโซลูชันและอัลกอริธึมการออกแบบ เช่น อัลกอริทึม Bellman-Ford เพื่อค้นหาเส้นทางที่สั้นที่สุดในกราฟ โดยปกติแล้ว ปัญหาย่อยจะถูกแก้ไขจากล่างขึ้นบน หมายความว่าปัญหาที่ง่ายที่สุดจะถูกแก้ไขก่อน โซลูชันเหล่านี้จะถูกรวมเข้าด้วยกันเพื่อแก้ปัญหาเบื้องต้น
ปัญหา Subarray สูงสุดคืออะไร
นี่เป็นปัญหาการเขียนโปรแกรมแบบคลาสสิกที่เกี่ยวข้องกับการค้นหาผลรวมที่ใหญ่ที่สุด แถบย่อยที่อยู่ติดกันภายในอาร์เรย์ของจำนวนเต็ม วิธีแก้ปัญหานี้มีแอปพลิเคชันมากมายในสาขาต่างๆ เช่น การเงิน การวิเคราะห์ข้อมูล และการประมวลผลสัญญาณ อัลกอริทึมที่มีประสิทธิภาพมากที่สุดในการแก้ปัญหานี้คืออัลกอริทึมของ Kadane
อัลกอริทึมของ Kadane คืออะไร
อัลกอริทึมของ Kadane เป็นแนวทางที่มีประสิทธิภาพในการแก้ปัญหา subarray ที่ติดกันสูงสุด. อัลกอริทึมทำงานโดยการคำนวณ local_maximum และ global_maximum โดยการวนซ้ำบนอาร์เรย์ที่เริ่มต้นจากด้านซ้าย ตัวแปรเหล่านี้จะได้รับการอัปเดตในแต่ละขั้นตอน โดยค่าสูงสุดที่ local_maximum จนถึงตอนนี้จะแทนที่ global_maximum หากมีค่ามากกว่า เมื่อคำนวณ local_maximums ทั้งหมดแล้ว ก็จะทราบค่าสูงสุดของ subarray ที่ต่อเนื่องกันและมีค่าเท่ากับ global_maximum
วิธีการแบบ brute force ในการแก้ปัญหาค่า maximum Subarray คืออะไร
วิธีการเดรัจฉานเกี่ยวข้องกับการวนซ้ำของ subarrays ที่เป็นไปได้ทั้งหมดในอาร์เรย์และการคำนวณผลรวมของ subarray จากนั้นจะพบแถบย่อยที่อยู่ติดกันสูงสุด แต่กระบวนการนี้ไม่ได้มีประสิทธิภาพมากนักเนื่องจากต้องคำนวณทุกแถบย่อยเดียว
ข้อเสียของการใช้อัลกอริทึมของ Kadane คืออะไร
แม้ว่าอัลกอริทึมของ Kadane จะเรียบง่ายและมีประสิทธิภาพ แต่ก็สามารถนำมาใช้เพื่อแก้ปัญหา subarray สูงสุดได้เท่านั้น เอาต์พุตที่ผลิตออกมายังมีข้อจำกัด เนื่องจากมีผลรวมของ subarray สูงสุดเท่านั้น ไม่มีข้อมูลเกี่ยวกับอาร์เรย์เอง ซึ่งอาจจำเป็นสำหรับบางแอปพลิเคชัน ประการสุดท้าย แม้ว่าอัลกอริทึมจะรวดเร็ว การแก้ปัญหาก็ไม่ได้ดีที่สุดในทุกกรณี
อัลกอริทึมของ Kadane มีความซับซ้อนด้านเวลาเท่าใด
ความซับซ้อนของเวลาของ อัลกอริทึมของ Kadane คือ O(n)
อัลกอริทึมของ Kadane ใช้กับอาร์เรย์ที่ไม่ติดกันได้หรือไม่
ไม่ได้ อัลกอริทึมนี้ใช้กับ อาร์เรย์ที่ไม่ต่อเนื่องกัน
อัลกอริทึมของ Kadane สามารถแก้ไขเพื่อค้นหา subarray ที่มีผลรวมต่ำสุดได้อย่างไร
เราสามารถแทนที่ฟังก์ชัน maxsize ด้วย minsize และกำหนดค่าเริ่มต้นตัวแปรเป็นค่าอนันต์แทนศูนย์
อัลกอริทึมของ Kadane สามารถใช้กับอาร์เรย์ที่มีจำนวนเต็มลบทั้งหมดได้หรือไม่
ได้ อัลกอริทึมจะ ส่งคืน subarray ที่มีผลรวมเป็นลบน้อยที่สุดในกรณีนี้