การคูณเมทริกซ์แบบลูกโซ่คืออะไร

การคูณลูกโซ่เป็นเพียงการคูณแบบอนุกรม เอบีซีดี . เดิมทีไม่มีอะไรเกี่ยวกับการเขียนโปรแกรมและการเขียนโปรแกรมแบบไดนามิก แต่มีกฎที่ดี (กฎสมาคม) A * (B * C) = (A * B) * C แต่ค่าใช้จ่ายในการคำนวณของนิพจน์เหล่านี้แตกต่างกัน ดังนั้นจึงมีงานกระจายวงเล็บให้เหมาะสมที่สุด มันเป็นบทนำ ตอนนี้อ่านวิกิแล้ว

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

M1 = 12 x 20
M2 = 20 x 15
M3 = 15 x 30

มีสองวิธีในการแก้ปัญหานี้ ขึ้นอยู่กับว่าคุณเริ่มคูณเมทริกซ์จากจุดใด

1). ((M1 x M2) x M3)
2). (M1 x (M2 x M3))

อันแรกต้องการการคูณเพียง 3,600 + 5,400 = 9,000
วิธีที่สองต้องใช้การคูณ 9,000 + 7,200 = 16,200 ครั้ง
ที่นี่เราจะเลือกอันแรกในช่วงวินาทีเพราะต้องการจำนวนการคูณน้อยกว่า
โปรแกรมของคุณต้องสามารถบอกผู้ใช้ถึงวิธีใส่วงเล็บเมทริกซ์เพื่อลดการคูณได้ (ปัญหาการเพิ่มประสิทธิภาพ)