dynamic-programming
Mnożenie łańcucha macierzy
Szukaj…
Rozwiązanie rekurencyjne
Mnożenie łańcucha macierzy to problem optymalizacji, który można rozwiązać za pomocą programowania dynamicznego. Biorąc pod uwagę sekwencję macierzy, celem jest znalezienie najbardziej efektywnego sposobu pomnożenia tych macierzy. Problemem nie jest w rzeczywistości wykonanie mnożenia, ale jedynie ustalenie sekwencji mnożenia macierzy.
Załóżmy, że mamy dwie macierze A, 1 i 2 o wymiarze m * n i p * P. Z zasad mnożenia macierzy wiemy, że
- Możemy wielokrotnie A1 i A 2, wtedy i tylko wtedy, gdy n = p. Oznacza to, że liczba kolumn A 1 musi być równa liczbie rzędów A 2.
- Jeśli pierwszy warunek jest spełniony i robimy pomnożyć A 1 i A 2, dostaniemy nową matrycę, nazwijmy go A 3 o wymiarze m * q.
- Aby pomnożyć 1 i A 2, musimy zrobić kilka mnożenia skalowania. Całkowita liczba zwielokrotnień skalujących, które musimy wykonać, to ( m * n * q ) lub ( m * p * q ).
- A 1 * A 2 nie jest równe A 2 * A 1 .
Jeśli mamy trzy macierze A 1, A2 i A3 o wymiar m * n * n p i P * P, odpowiednio, to jest 4 = A 1 * 2 * 3 stworzą wymiar m * q. Teraz możemy wykonać to mnożenie macierzy na dwa sposoby:
- Najpierw wielokrotnie A1 i A 2, a następnie w efekcie wielokrotnie A3. To znaczy: ( A 1 * A 2 ) * A 3 .
- Najpierw wielokrotnie A2 i A3, po czym w wyniku pomnożyć A1. To znaczy: A 1 * ( A 2 * A 3 ).
Możesz zauważyć, że kolejność mnożenia pozostaje taka sama, tzn. Nie mnożymy ( A 1 * A 3 ) * A 2, ponieważ może nie być poprawna. Zmieniamy tylko nawias, aby pomnożyć zestaw przed pomnożeniem go przez pozostałe. Ważne jest, w jaki sposób umieszczamy te nawiasy. Dlaczego? Powiedzmy zacznij wymiar 3 macierzy A 1, A2 i A3 są 10 * 100 * 100, 5, 5 * 50. Następnie,
- Dla ( A 1 * A 2 ) * A 3 całkowita liczba zwielokrotnień skalera wynosi: ( 10 * 100 * 5 ) + ( 10 * 5 * 50 ) = 7500 razy.
- Dla A 1 * ( A 2 * A 3 ) całkowita liczba zwielokrotnień skalera wynosi: ( 100 * 5 * 50 ) + ( 10 * 100 * 50 ) = 75000 razy.
W przypadku drugiego typu liczba zwielokrotnienia skalera jest 10 razy większa od liczby pierwszego typu! Jeśli więc możesz znaleźć sposób na znalezienie prawidłowej orientacji nawiasów potrzebnej do zminimalizowania całkowitego zwielokrotnienia skalera, skróciłoby to zarówno czas, jak i pamięć potrzebną do zwielokrotnienia macierzy. Tutaj przydaje się mnożenie łańcucha macierzy. W tym przypadku nie będziemy się zajmować faktycznym mnożeniem macierzy, dowiemy się tylko o prawidłowej kolejności nawiasów, aby zminimalizować liczbę mnożników skalera. Będziemy mieć macierze A 1 , A 2 , A 3 ........ A n i ustalimy minimalną liczbę mnożników skalujących potrzebnych do ich pomnożenia. Zakładamy, że podane wymiary są prawidłowe, tzn. Że spełniają nasz pierwszy wymóg mnożenia macierzy.
W celu rozwiązania tego problemu zastosujemy metodę „dziel i rządź”. Programowanie dynamiczne jest potrzebne ze względu na typowe podproblemy. Na przykład: dla n = 5, 5 mamy macierz A 1, A 2, A3, A4 i A5. Chcemy znaleźć minimalną liczbę mnożenia potrzebną do wykonania tego mnożenia macierzy A 1 * A 2 * A 3 * A 4 * A 5 . Spośród wielu sposobów skoncentrujmy się na jednym: ( A 1 * A 2 ) * ( A 3 * A 4 * A 5 ).
W tym przypadku dowiemy się A left = A 1 * A 2 . Prawo = A 3 * A 4 * A 5 . Następnie dowiemy się : odpowiedź = lewa * prawa . Całkowita liczba zwielokrotnień skalera potrzebnych do znalezienia odpowiedzi A : = Łączna liczba zwielokrotnień skalera potrzebnych do ustalenia A w lewo + Całkowita liczba zwielokrotnień skalera potrzebnych do ustalenia A w prawo + Całkowita liczba zwielokrotnień skalera potrzebnych do ustalenia A w lewo * Prawo
Ostatni termin, Łączna liczba zwielokrotnień skalujących potrzebnych do określenia A po lewej * Prawo może być zapisane jako: Liczba wierszy po lewej A * liczba kolumn po lewej A * liczba kolumn po prawej stronie . (Zgodnie z drugą zasadą mnożenia macierzy)
Ale moglibyśmy ustawić nawias także na inne sposoby. Na przykład:
- A 1 * ( A 2 * A 3 * A 4 * A 5 )
- ( A 1 * A 2 * A 3 ) * ( A 4 * A 5 )
- ( A 1 * A 2 * A 3 * A 4 ) * A 5 itp.
Dla każdego możliwego przypadku określimy liczbę pomnożenia skalera potrzebną do wykrycia A lewej i A prawej , a następnie A lewej * A prawej . Jeśli masz ogólne pojęcie o rekurencji, już wiesz, jak wykonać to zadanie. Nasz algorytm będzie:
- Set parenthesis in all possible ways.
- Recursively solve for the smaller parts.
- Find out the total number of scaler multiplication by merging left and right.
- Of all possible ways, choose the best one.
Dlaczego jest to problem z programowaniem dynamicznym? Aby ustalić ( A 1 * A 2 * A 3 ), jeśli już obliczyłeś ( A 1 * A 2 ), w tym przypadku pomocne będzie.
Aby określić stan tej rekurencji, widzimy, że aby rozwiązać każdy przypadek, musimy znać zakres macierzy, z którymi pracujemy. Potrzebujemy więc początku i końca . Ponieważ używamy dzielenia i podbijania, w naszym przypadku podstawowym będzie mniej niż 2 macierze ( początek > = koniec ), w których nie musimy w ogóle się pomnażać. Będziemy mieć 2 tablice: wiersz i kolumnę . wiersz [i] i kolumna [i] będą przechowywać liczbę wierszy i kolumn dla macierzy A i . Będziemy mieli tablicę dp [n] [n] do przechowywania już obliczonych wartości i zainicjowania jej -1 , gdzie -1 oznacza, że wartość nie została jeszcze obliczona. dp [i] [j] reprezentuje liczbę zwielokrotnień skalujących potrzebnych do pomnożenia A i , A i + 1 , ....., A j włącznie. Pseudo-kod będzie wyglądał następująco:
Procedure matrixChain(begin, end):
if begin >= end
Return 0
else if dp[begin][end] is not equal to -1
Return dp[begin][end]
end if
answer := infinity
for mid from begin to end
operation_for_left := matrixChain(begin, mid)
operation_for_right := matrixChain(mid+1, right)
operation_for_left_and_right := row[begin] * column[mid] * column[end]
total := operation_for_left + operation_for_right + operation_for_left_and_right
answer := min(total, answer)
end for
dp[begin][end] := answer
Return dp[begin][end]
Złożoność:
Wartość początku i końca może wynosić od 1 do n . Istnieją n 2 różne stany. Dla każdego stanu pętla wewnątrz będzie działać n razy. Złożoność czasu całkowitego: O(n³) i złożoność pamięci: O(n²) .