สารานุกรมออนไลน์ | Siam Wiki
ไม่เจอคำค้นที่ต้องการ
หน้าแรก
การคูณลูกโซ่ของเมทริกซ์
หน้าแรก
การคูณลูกโซ่ของเมทริกซ์
Matrix-Chain Multiplication หรือ การคูณเมตริกซ์ ใช้สำหรับการแก้ปัญหาการคูณ matrix ซึ่งการคูณปกติอาจจะมีจำนวนครั้งมากเกินไปหรือมีประสิทธิภาพที่ไม่ดีพอซึ่งการใช้ algorithm นี้เป็นการคูณ matrix อย่างต่อเนื่องเพื่อหารูปแบบการคูณที่ดีที่สุดโดยใช้คุณสมบัติการเปลี่ยนหมวดหมู่การคูณของ matrixตัวอย่างmatrix X มีขนาด 10 x 3matrix Y มีขนาด 3 x 5matrix Z มีขนาด 5 x 6 จำนวนครั้งของการคูณแบบ (X * Y) * Z คือ(10*3*5 + 10*5*6) = 450 ครั้งส่วนจำนวนครั้งของการคูณแบบ X * (Y * Z) คือ (3*5*6 + 10*3*6) = 270 ครั้ง จะเห็นได้ว่าการเปลี่ยนหมวดหมู่การคูณช่วยเพิ่มประสิทธิภาพหรือลดจำนวนครั้งการคูณลงได้ เราจึงต้องหารูปแบบของหมวดหมู่ที่ดีที่สุดโดยใช้ Matrix-Chain-Multiplication ทำการคูณ ถ้าเราต้องการคูณแมทริกซ์จำนวน n ตัว A1A2…An ต้องการหาลำดับการคูณแมทริกซ์ ที่ใช้จำนวนครั้งของการคูณน้อยที่สุดเช่น n = 3 ต้องการคูณ A1A2A3 เมื่อ A1, A2, A3 มีขนาด10x100, 100x5, และ 5x50ตามลำดับ (A1A2)A3) ต้องใช้จำนวนครั้งของการคูณ = 10*100*5 เพื่อคำนวณ (A1A2)+ 10*5*50 เพื่อคำนวณ ((A1A2)A3)=7,500 ครั้ง(A1(A2A3)) ต้องใช้จำนวนครั้งของการคูณ = 100*5*50 เพื่อคำนวณ (A2A3)+ 10*100*50 เพื่อคำนวณ (A1(A2A3)) = 75,000 ครั้งจะเห็นได้ว่า ((A1A2)A3) ใช้จำนวนครั้งของการคูณน้อยกว่า (A1(A2A3))ถึงสิบเท่า
[https://www.youtube.com/watch?v=GMzVeWpyTN0 1]
[https://www.geeksforgeeks.org/dynamic-programming-set-8-matrix-chain-multiplication/ 1]
เมนูนำทาง
การคูณลูกโซ่ของเมทริกซ์
ใกล้เคียง
แหล่งที่มา
WikiPedia: การคูณลูกโซ่ของเมทริกซ์
×