การคูณเมทริกซ์แบบลูกโซ่ (หรือปัญหาการเรียงลำดับเมทริกซ์แบบลูกโซ่^{[ 1 ]} ) เป็นปัญหาการหาค่าเหมาะสมที่สุดที่เกี่ยวข้องกับวิธีที่มีประสิทธิภาพที่สุดในการคูณลำดับของเมท ริกซ์ที่กำหนด ปัญหาไม่ได้อยู่ที่การดำเนินการคูณจริง ๆ แต่เป็นการตัดสินใจลำดับของการคูณเมทริกซ์ที่เกี่ยวข้องเท่านั้น ปัญหานี้อาจแก้ไขได้โดยใช้ การ เขียน โปรแกรมแบบไดนามิก

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

(( AB ) C ) D = ( A ( BC ) ) D = ( AB ) ( CD ) = A (( BC ) D ) = A ( B ( CD ) ).

แม้ว่าลำดับการใส่วงเล็บของพจน์ต่างๆ จะไม่ส่งผลต่อผลลัพธ์ แต่ก็ส่งผลต่อจำนวนการคำนวณทางคณิตศาสตร์อย่างง่ายที่จำเป็นในการคำนวณผลลัพธ์นั้น กล่าวคือ ส่งผล ต่อ ความซับซ้อนในการคำนวณ การคูณเมทริกซ์ขนาดX × Yกับเมทริกซ์ขนาดY × Z โดยตรงนั้น ต้องใช้ การคูณธรรมดา XYZครั้ง และ การบวกธรรมดา X ( Y − 1) Zครั้ง ในบริบทนี้ โดยทั่วไปแล้วจะใช้จำนวนการคูณธรรมดาเป็นตัววัดความซับซ้อนของเวลาในการทำงาน

ถ้าAเป็นเมทริกซ์ขนาด 10 × 30, Bเป็นเมทริกซ์ขนาด 30 × 5 และCเป็นเมทริกซ์ขนาด 5 × 60 แล้ว

การคำนวณ ( AB ) Cต้องการการดำเนินการ (10×30×5) + (10×5×60) = 1500 + 3000 = 4500 ครั้ง ในขณะที่

การคำนวณA ( BC )ต้องใช้การดำเนินการ (30×5×60) + (10×30×60) = 9000 + 18000 = 27000 ครั้ง

เห็นได้ชัดว่าวิธีแรกมีประสิทธิภาพมากกว่า ด้วยข้อมูลนี้ ปัญหาจึงสามารถปรับปรุงได้เป็น "จะกำหนดวงเล็บที่เหมาะสมที่สุดของผลคูณของเมท ริกซ์ n ตัวได้อย่างไร " จำนวนวงเล็บที่เป็นไปได้นั้นกำหนดโดยจำนวนคาตาลันลำดับที่⁽ n – 1) ซึ่งคือΘ (4n ^/ n³ / ^² )ดังนั้นการตรวจสอบวงเล็บที่เป็นไปได้ทั้งหมด ( วิธีลองทุกวิธี ) จะต้องใช้เวลาในการทำงานที่เป็นเลขชี้กำลังตามจำนวนเมทริกซ์ ซึ่งช้ามากและไม่เหมาะสมสำหรับn ขนาดใหญ่ วิธีแก้ปัญหาที่รวดเร็วกว่าสามารถทำได้โดยการแบ่งปัญหาออกเป็นชุดของปัญหาย่อยที่เกี่ยวข้องกัน

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

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

ตัวอย่างเช่น ถ้าเรามีเมทริกซ์สี่เมทริกซ์ ABCDเราจะคำนวณต้นทุนที่จำเป็นในการหาแต่ละ ( A ) ( BCD ) , ( AB ) ( CD )และ ( ABC ) ( D )โดยเรียกซ้ำเพื่อหาต้นทุนต่ำสุดในการคำนวณABC , AB , CDและBCDจากนั้นเราจะเลือกวิธีที่ดีที่สุด ยิ่งไปกว่านั้น วิธีนี้ไม่เพียงแต่ให้ต้นทุนต่ำสุดเท่านั้น แต่ยังแสดงให้เห็นถึงวิธีที่ดีที่สุดในการคำนวณการคูณด้วย กล่าวคือ จัดกลุ่มในลักษณะที่ให้ต้นทุนรวมต่ำที่สุด และทำเช่นเดียวกันสำหรับแต่ละตัวประกอบ

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

วิธีแก้ปัญหาอย่างง่ายวิธีหนึ่งเรียกว่าการจดจำผลลัพธ์ (memoization ): ทุกครั้งที่เราคำนวณต้นทุนขั้นต่ำที่จำเป็นในการคูณลำดับย่อยเฉพาะ เราจะบันทึกผลลัพธ์นั้นไว้ หากเราถูกขอให้คำนวณอีกครั้ง เราก็เพียงแค่ให้คำตอบที่บันทึกไว้ และไม่ต้องคำนวณใหม่ เนื่องจากมีลำดับย่อยที่แตกต่างกันประมาณ^n² / 2 ลำดับ โดยที่nคือจำนวนเมทริกซ์ พื้นที่ที่จำเป็นในการทำเช่นนี้จึงสมเหตุสมผล สามารถแสดงให้เห็นได้ว่าเทคนิคอย่างง่ายนี้ช่วยลดเวลาการทำงานลงเหลือ O( n³ ) จากแบบเลขชี้กำลัง ซึ่งมีประสิทธิภาพมากพอสำหรับการใช้งานจริง นี่คือ การเขียนโปรแกรมแบบไดนามิกจากบนลงล่าง ⁽ top-down dynamic programming)

แนวทางจากล่างขึ้นบนต่อไปนี้^{[ 2 ]}คำนวณต้นทุนขั้นต่ำของลำดับย่อยทั้งหมดที่มีความยาวk สำหรับแต่ละ 2 ≤ k ≤ n โดยใช้ต้นทุนของลำดับย่อยที่เล็กกว่าที่คำนวณไว้แล้ว มีเวลารันไทม์เชิงอะซิมโทติกเท่ากันและไม่ต้องการการเรียกซ้ำ

รหัสเทียม :

// เมทริกซ์ A[i] มีมิติ dims[i-1] x dims[i] สำหรับ i = 1..n MatrixChainOrder ( int dims [] ) { // length[dims] = n + 1 n = dims . length - 1 ; // m[i,j] = จำนวนขั้นต่ำของการคูณสเกลาร์ (เช่น ต้นทุน) // ที่จำเป็นในการคำนวณเมทริกซ์ A[i]A[i+1]...A[j] = A[i..j] // ต้นทุนเป็นศูนย์เมื่อคูณเมทริกซ์หนึ่งตัวสำหรับ( i = 1 ; i <= n ; i ++ ) m [ i , i ] = 0 ;สำหรับ( len = 2 ; len <= n ; len ++ ) { // ความยาวของลำดับย่อยสำหรับ( i = 1 ; i <= n - len + 1 ; i ++ ) { j = i + len - 1 ; m [ i , j ] = MAXINT ; สำหรับ( k = i ; k <= j - 1 ; k ++ ) { cost = m [ i , k ] + m [ k + 1 , j ] + dims [ i - 1 ] * dims [ k ] * dims [ j ] ; ถ้าcost < m [ i , j ] { m [ i , j ] = cost ; s [ i , j ] = k ; // ดัชนีของการแบ่งลำดับย่อยที่ทำให้ได้ต้นทุนต่ำสุด} } } } }

• หมายเหตุ: ดัชนีแรกสำหรับ dims คือ 0 และดัชนีแรกสำหรับmและsคือ 1

ตัวอย่าง การใช้งาน Pythonโดยใช้ decorator memoization จากไลบรารีมาตรฐาน:

จากfunctools นำเข้าcachedef matrix_chain_order ( dims : list [ int ]) -> int : @cache def a ( i , j ): return min ( ( a ( i , k ) + dims [ i ] * dims [ k ] * dims [ j ] + a ( k , j ) for k in range ( i + 1 , j )), default = 0 , )ส่งคืนค่าa ( 0 , len ( dims ) - 1 )

มีอัลกอริธึมบางตัวที่มีประสิทธิภาพมากกว่า อัลกอริธึมการเขียนโปรแกรมเชิงพลวัต O ( n³ ⁾แม้ว่าจะมีความซับซ้อนกว่าก็ตาม

อัลกอริทึมที่เผยแพร่โดยTC Huและ M.-T. Shing บรรลุความซับซ้อนในการคำนวณ O ( n log  n  ) [ ^{3 ] [ 4 ] [ 5 ] พวก} เขาแสดงให้เห็นว่าปัญหาการคูณเมทริกซ์แบบลูกโซ่สามารถแปลง (หรือลดทอน ) เป็นปัญหาการสร้างรูปสามเหลี่ยมของรูปหลายเหลี่ยมปกติได้รูปหลายเหลี่ยมมีทิศทางโดยมีด้านล่างแนวนอนเรียกว่าฐาน ซึ่งแสดงถึงผลลัพธ์สุดท้าย ด้านอีกnด้านของรูปหลายเหลี่ยมในทิศทางตามเข็มนาฬิกาแสดงถึงเมทริกซ์ จุดยอดที่ปลายแต่ละด้านคือมิติของเมทริกซ์ที่แสดงโดยด้านนั้น ด้วย เมทริกซ์ nตัวในลูกโซ่การคูณ จะมีการดำเนินการไบนารีn −1 ครั้ง และC _{n −1}วิธีในการวางวงเล็บ โดยที่C _{n −1}คือจำนวนคาตาลัน ลำดับที่ ( n −1) อัลกอริทึมใช้ประโยชน์ จากความ เป็นไปได้ในการสร้างรูปสามเหลี่ยมของรูปหลายเหลี่ยมที่มีn +1 ด้าน ได้ C _{n −1 วิธี}

ภาพนี้แสดงการแบ่งรูปหกเหลี่ยม ด้านเท่าออกเป็นรูปสามเหลี่ยม ได้หลายแบบ ซึ่งสอดคล้องกับวิธีการจัดวางวงเล็บเพื่อเรียงลำดับการคูณสำหรับผลคูณของเมทริกซ์ 5 ตัว

สำหรับตัวอย่างด้านล่าง มีด้านสี่ด้าน ได้แก่ A, B, C และผลลัพธ์สุดท้าย ABC A เป็นเมทริกซ์ขนาด 10×30, B เป็นเมทริกซ์ขนาด 30×5, C เป็นเมทริกซ์ขนาด 5×60 และผลลัพธ์สุดท้ายเป็นเมทริกซ์ขนาด 10×60 รูปหลายเหลี่ยมปกติสำหรับตัวอย่างนี้คือรูป 4 ด้าน นั่นคือรูปสี่เหลี่ยมจัตุรัส:

ผลคูณเมทริกซ์ AB เป็นเมทริกซ์ขนาด 10x5 และ BC เป็นเมทริกซ์ขนาด 30x60 การแบ่งสามเหลี่ยมที่เป็นไปได้สองแบบในตัวอย่างนี้คือ:

• 
  การแสดงรูปหลายเหลี่ยมของ (AB)C
• 
  การแสดงรูปหลายเหลี่ยมของ A(BC)

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

( AB ) C : (10×30×5) + (10×5×60) = 1500 + 3000 = 4500 การคูณ

A ( BC ) : (30×5×60) + (10×30×60) = 9000 + 18000 = 27000 การคูณ

Hu และ Shing ได้พัฒนาอัลกอริทึมที่ค้นหาวิธีแก้ปัญหาที่เหมาะสมที่สุดสำหรับปัญหาการแบ่งพาร์ติ ชันต้นทุนต่ำสุด ใน เวลา O ( n  log  n )การพิสูจน์ความถูกต้องของอัลกอริทึมของพวกเขาอาศัย "Lemma 1" ที่พิสูจน์ในรายงานทางเทคนิคปี 1981 และถูกละเว้นจากเอกสารที่ตีพิมพ์^{[ 6 ] [ 4 ]}การพิสูจน์ Lemma ในรายงานทางเทคนิคไม่ถูกต้อง แต่ Shing ได้นำเสนอการพิสูจน์ที่แก้ไขแล้ว^{[ 1 ]}

Wang, Zhu และ Tian ได้เผยแพร่ อัลกอริทึม O ( n  log  m ) ที่เรียบง่าย โดยที่nคือจำนวนเมทริกซ์ในโซ่ และmคือจำนวนค่าต่ำสุดเฉพาะที่ในลำดับมิติของโซ่เมทริกซ์ที่กำหนด^{[ 7 ]}

อัลกอริทึมที่สร้างขึ้นโดยอิสระโดย Chin ^{[ 8 ]}และ Hu & Shing ^{[ 9 ]}ทำงานใน O( n )และสร้างวงเล็บซึ่งแย่กว่าตัวเลือกที่เหมาะสมที่สุดไม่เกิน 15.47% ในกรณีส่วนใหญ่ อัลกอริทึมจะให้ผลลัพธ์ที่ดีที่สุดหรือผลลัพธ์ที่แย่กว่าผลลัพธ์ที่ดีที่สุดเพียง 1-2 เปอร์เซ็นต์^{[ 5 ]}

อัลกอริทึมเริ่มต้นด้วยการแปลงปัญหาให้เป็นปัญหาการแบ่งรูปหลายเหลี่ยม โดยแต่ละจุดยอดVของรูปหลายเหลี่ยมจะมีน้ำหนักw กำกับอยู่ สมมติว่าเรามีจุดยอดสามจุดที่อยู่ติดกันและเป็นจุดยอดที่มีน้ำหนักน้อยที่สุดเราจะพิจารณารูปสี่เหลี่ยมที่มีจุดยอด(เรียงตามเข็มนาฬิกา) เราสามารถแบ่งเป็นรูปสามเหลี่ยมได้สองวิธี: ${\displaystyle V_{i-1},V_{i},V_{i+1}}$${\displaystyle V_{\min }}$${\displaystyle w_{\min }}$${\displaystyle V_{\min },V_{i-1},V_{i},V_{i+1}}$

• ${\displaystyle (V_{\min },V_{i-1},V_{i})}$และมีค่าใช้จ่าย${\displaystyle (V_{\min },V_{i+1},V_{i})}$${\displaystyle w_{\min }w_{i-1}w_{i}+w_{\min }w_{i+1}w_{i}}$
• ${\displaystyle (V_{\min },V_{i-1},V_{i+1})}$และมีค่าใช้จ่ายด้วย${\displaystyle (V_{i-1},V_{i},V_{i+1})}$${\displaystyle w_{\min }w_{i-1}w_{i+1}+w_{i-1}w_{i}w_{i+1}}$

ดังนั้น ถ้า

${\displaystyle w_{\min }w_{i-1}w_{i+1}+w_{i-1}w_{i}w_{i+1}<w_{\min }w_{i-1}w_{i}+w_{\min }w_{i+1}w_{i}}$

หรือเทียบเท่า

${\displaystyle {\frac {1}{w_{i}}}+{\frac {1}{w_{\min }}}<{\frac {1}{w_{i+1}}}+{\frac {1}{w_{i-1}}}}$

เราลบจุดยอดออกจากรูปหลายเหลี่ยมและเพิ่มด้านนั้นเข้าไปในการแบ่งรูปสามเหลี่ยม เราทำซ้ำกระบวนการนี้จนกว่าจะไม่มีจุดยอดใดตรงตามเงื่อนไขข้างต้น สำหรับจุดยอดที่เหลือทั้งหมดเราจะเพิ่มด้านนั้นเข้าไปในการแบ่งรูปสามเหลี่ยม ซึ่งจะทำให้เราได้การแบ่งรูปสามเหลี่ยมที่เกือบจะเหมาะสมที่สุด ${\displaystyle V_{i}}$${\displaystyle (V_{i-1},V_{i+1})}$${\displaystyle V_{i}}$${\displaystyle V_{n}}$${\displaystyle (V_{\min },V_{n})}$

ปัญหาการคูณโซ่เมทริกซ์สามารถขยายไปสู่การแก้ปัญหาที่เป็นนามธรรมมากขึ้นได้ กล่าวคือ เมื่อกำหนดลำดับเชิงเส้นของวัตถุ การดำเนินการไบนารีแบบเชื่อมโยงบนวัตถุเหล่านั้น และวิธีการคำนวณต้นทุนของการดำเนินการนั้นบนวัตถุสองชิ้นที่กำหนด (รวมถึงผลลัพธ์บางส่วนทั้งหมด) ให้คำนวณวิธีการจัดกลุ่มวัตถุด้วยต้นทุนต่ำสุดเพื่อใช้การดำเนินการกับลำดับ^{[ 10 ]}ตัวอย่างที่เป็นรูปธรรมของเรื่องนี้มาจากการเรียงลำดับ การดำเนินการ ร่วมในฐานข้อมูลดูการเพิ่มประสิทธิภาพการสืบค้น § การเรียงลำดับการร่วม

อีกกรณีพิเศษที่ค่อนข้างซับซ้อนคือการต่อสตริงของลิสต์ของสตริง ในภาษา Cตัวอย่างเช่น ต้นทุนของการต่อสตริงสองสตริงที่มีความยาวmและnโดยใช้strcatคือ O( m  +  n )เนื่องจากเราต้องใช้เวลา O( m )ในการค้นหาจุดสิ้นสุดของสตริงแรก และเวลา O( n )ในการคัดลอกสตริงที่สองไปไว้ที่ท้ายสตริงแรก โดยใช้ฟังก์ชันต้นทุนนี้ เราสามารถเขียนอัลกอริทึมการเขียนโปรแกรมแบบไดนามิกเพื่อหาวิธีที่เร็วที่สุดในการต่อลำดับของสตริง อย่างไรก็ตาม การเพิ่มประสิทธิภาพนี้ค่อนข้างไร้ประโยชน์ เพราะเราสามารถต่อสตริงได้โดยตรงในเวลาที่แปรผันตามผลรวมของความยาวของสตริง ปัญหาที่คล้ายกันนี้เกิดขึ้นกับลิสต์แบบเชื่อมโยง เดี่ยว ด้วย

การวางนัยทั่วไปอีกประการหนึ่งคือการแก้ปัญหาเมื่อมีโปรเซสเซอร์แบบขนาน ในกรณีนี้ แทนที่จะบวกต้นทุนของการคำนวณแต่ละปัจจัยของผลคูณเมทริกซ์ เราจะใช้ค่าสูงสุดเนื่องจากเราสามารถทำพร้อมกันได้ ซึ่งอาจส่งผลกระทบอย่างมากต่อทั้งต้นทุนขั้นต่ำและการจัดกลุ่มที่เหมาะสมที่สุดในท้ายที่สุด การจัดกลุ่มที่ "สมดุล" มากขึ้นซึ่งทำให้โปรเซสเซอร์ทั้งหมดทำงานได้อย่างต่อเนื่องจะได้รับความนิยมมากกว่า นอกจากนี้ยังมีวิธีการที่ซับซ้อนกว่านี้อีกด้วย^{[ 11 ]}

• แอสโซซิอาเฮดรอน
• ตะแกรงทามาริ