Matrix Chain Multiplication
Łańcuch macierzy jest opisany przez dims: macierz i ma dims[i] wierszy i dims[i+1] kolumn, więc każda macierz pasuje do następnej. Mnożenie macierzy p × q przez macierz q × r wymaga p × q × r mnożeń skalarnych i daje macierz p × r. Każdy sposób umieszczenia nawiasów daje ten sam wynik końcowy, ale nie przy takim samym koszcie. Zwróć najmniejszą liczbę mnożeń skalarnych potrzebną do pomnożenia całego łańcucha.
Funkcja
- dimsinteger-array
- rozmiary wzdłuż łańcucha: macierz i ma wymiary dims[i] × dims[i+1]
- Zwracainteger
- najmniejsza liczba mnożeń skalarnych potrzebnych do pomnożenia całego łańcucha
Ograniczenia
2 ≤ dims.length ≤ 100, więc łańcuch zawiera od 1 do 99 macierzy.1 ≤ dims[i] ≤ 100- Odpowiedź wynosi co najwyżej 98 × 106, znacznie poniżej zakresu 32-bitowej liczby całkowitej ze znakiem.
Przykłady
- Wejście
- dims = [4, 10, 3, 12]
- Wyjście
- 264
- Wyjaśnienie
- Pomnożenie pierwszych dwóch kosztuje 4 × 10 × 3 = 120 i daje macierz 4 × 3, której pomnożenie przez macierz 3 × 12 kosztuje dodatkowo 144: 264. Druga kolejność kosztuje 360 + 480 = 840.
- Wejście
- dims = [6, 2, 7, 3, 5]
- Wyjście
- 132
- Wyjaśnienie
- Pomnóż 2 × 7 przez 7 × 3 (42), wynik 2 × 3 przez 3 × 5 (30), a następnie 6 × 2 przez wynik 2 × 5 (60): łącznie 132.
- Wejście
- dims = [3, 7]
- Wyjście
- 0
- Wyjaśnienie
- Jest tylko jedna macierz 3 × 7, więc niczego się nie mnoży, a koszt wynosi 0.
Pytanie dodatkowe
Czy możesz również policzyć, ile różnych sposobów nawiasowania pozwala osiągnąć minimalny koszt?
Podpowiedzi
Otwieraj je po kolei. Każda zdradza trochę więcej.
Zapomnij o pierwszym mnożeniu i pomyśl o ostatnim. Niezależnie od wybranej kolejności, ostatni krok polega na pomnożeniu iloczynu pewnej lewej części łańcucha przez iloczyn pozostałej części.
Iloczyn macierzy między dwiema granicami
leftirightjest zawsze macierządims[left] × dims[right]. Jeśli więc ostatni krok dzieli ten fragment na granicysplit, jego koszt wynosidims[left] × dims[split] × dims[right], a obie części są mniejszymi przypadkami tego samego problemu.Zapisz w
best[left][right]najtańszy sposób mnożenia macierzy między granicamileftiright(0 dla pojedynczej macierzy). To minimum spośród wszystkich wartościbest[left][split] + best[split][right] + dims[left] × dims[split] × dims[right], gdziesplitznajduje się ściśle między nimi. Oblicz najpierw wąskie zakresy, a potem szerokie.
Rozwiązanie
Kolejność zmienia koszt: 264 w porównaniu z 840 w pierwszym przykładzie. Przyjrzyj się ostatniemu mnożeniu. Łączy ono iloczyny lewej i prawej części łańcucha, a każda z tych części jest tym samym problemem dla krótszego łańcucha. Tabela obejmująca fragmenty łańcucha rozwiązuje każdy z nich raz, w czasie O(n³).
Wypróbuj każdy podział za pomocą zwykłej rekurencji
Poprawne, ale nie kończy się na największych testach
Intuicja
Ponumeruj granice łańcucha od 0 do m-1, gdzie m = dims.length: granica k ma rozmiar dims[k]. Macierze między granicami left i right po pomnożeniu w dowolnej kolejności dają macierz o wymiarach dims[left] × dims[right]. Jeśli więc ostatni krok dzieli ten fragment w miejscu split, jego koszt wynosi dims[left] × dims[split] × dims[right], niezależnie od tego, co działo się wewnątrz obu bloków. Każdy blok powinien być zbudowany jak najtaniej, więc cheapest(left, right) to najmniejsza suma kosztów obu bloków i tego ostatniego kroku, obliczona dla każdego split. Sprawdzenie wszystkich możliwych ostatnich kroków gwarantuje poprawność.
Wielokrotnie rozwiązuje te same fragmenty: dla n macierzy wykonuje 3^(n-1) wywołań, czyli około 1.2 × 10^9 dla 20 macierzy, mimo że istnieje tylko około m²/2 różnych fragmentów.
Algorytm
- Napisz
cheapest(left, right)dla macierzy między granicamileftiright. - Jeśli
right - left < 2, jest jedna macierz: zwróć 0. - Dla każdego
splitleżącego ściśle między nimi dodajcheapest(left, split),cheapest(split, right)orazdims[left] × dims[split] × dims[right]. - Zwróć najmniejszą sumę.
- Odpowiedzią jest
cheapest(0, m-1).
def matrixChainOrder(dims):
def cheapest(left, right):
# The fewest multiplications for the matrices between boundaries left and right
if right - left < 2:
return 0 # a single matrix costs nothing
best = None
for split in range(left + 1, right):
cost = (cheapest(left, split) + cheapest(split, right)
+ dims[left] * dims[split] * dims[right])
if best is None or cost < best:
best = cost
return best
return cheapest(0, len(dims) - 1)Rekurencja z memoizacją
Intuicja
Wywołanie zależy wyłącznie od left i right. Zapisz jego wynik w memo[left][right], przy czym każda komórka początkowo ma wartość -1, której nie może przyjąć żaden rzeczywisty koszt, a późniejsze wywołania odczytują wartość z komórki zamiast ponownie wywoływać rekurencję. Każda z około m²/2 par jest rozwiązywana raz, przy mniej niż m podziałach: O(n³), czyli 161,700 sprawdzeń podziałów dla 99 macierzy. Rekurencja nigdy nie jest głębsza niż długość łańcucha, więc 100 granic zmieści się na każdym stosie wywołań.
Algorytm
- Zainicjuj
memozmwierszami imkolumnami, każda komórka ma mieć wartość -1. - W funkcji
cheapest(left, right)zwróć 0 dla fragmentu obejmującego jedną macierz, a jeśli komórka ma wartość inną niż -1, zwróć zapisany w niej koszt. - W przeciwnym razie oblicz koszt każdego
splitdokładnie tak jak w zwykłej rekurencji i wybierz minimum. - Zapisz to minimum w
memo[left][right]przed jego zwróceniem. - Odpowiedzią jest
cheapest(0, m-1).
def matrixChainOrder(dims):
m = len(dims)
# memo[left][right]: the answer for boundaries left and right, -1 while unknown
memo = [[-1] * m for _ in range(m)]
def cheapest(left, right):
if right - left < 2:
return 0 # a single matrix costs nothing
if memo[left][right] != -1:
return memo[left][right]
best = None
for split in range(left + 1, right):
cost = (cheapest(left, split) + cheapest(split, right)
+ dims[left] * dims[split] * dims[right])
if best is None or cost < best:
best = cost
memo[left][right] = best
return best
return cheapest(0, m - 1)Wypełnij tabelę, rozciągając ją na całą szerokość
Intuicja
Każda komórka zależy tylko od węższych przedziałów, więc pętle mogą wypełniać best[left][right] od wąskich do szerokich. Szerokość 1 oznacza pojedynczą macierz, więc wartość pozostaje równa 0; gdy przechodzisz do szerszego przedziału, obie części każdego podziału są już obliczone. Dla dims = [6, 2, 7, 3, 5]:
- Szerokość 2:
best[0][2] = 84,best[1][3] = 42,best[2][4] = 105. - Szerokość 3:
best[0][3]wynosi 78 (podział 1: 0 + 42 + 36),best[1][4]wynosi 72 (podział 3: 42 + 0 + 30). - Szerokość 4: podziały 1, 2 i 3 dają odpowiednio 0 + 72 + 60 = 132, 84 + 105 + 210 = 399 oraz 78 + 0 + 90 = 168, więc
best[0][4] = 132.
Podział na granicy 1 oznacza, że macierz 6 × 2 jest dołączana na końcu, tak jak w drugim przykładzie. Czas działania i zużycie pamięci są takie same jak w wersji z memoizacją, ale bez rekurencji.
Algorytm
- Niech
m = dims.length, a następnie przydziel tablicęm × mwypełnioną zerami jakobest. - Przechodź pętlą po
widthod 2 dom-1. W jej wnętrzu zwiększajleftod 0, dopókiright = left + widthpozostaje granicą. - Dla tego przedziału oblicz
best[left][split] + best[split][right] + dims[left] × dims[split] × dims[right]dla każdegosplitodleft+1doright-1, a następnie zapisz minimum wbest[left][right]. - Odpowiedź znajduje się w
best[0][m-1].
def matrixChainOrder(dims):
m = len(dims)
# best[left][right]: the fewest multiplications for the matrices
# between boundary left and boundary right (0 for a single matrix)
best = [[0] * m for _ in range(m)]
for width in range(2, m):
for left in range(m - width):
right = left + width
low = None
for split in range(left + 1, right):
# the last product joins a dims[left] x dims[split] block
# with a dims[split] x dims[right] block
cost = best[left][split] + best[split][right] + dims[left] * dims[split] * dims[right]
if low is None or cost < low:
low = cost
best[left][right] = low
return best[0][m - 1]
Pułapki i przypadki brzegowe
- Mnożenie najpierw najtańszej pary. Dla
[10, 10, 1, 9]ostatnia para jest najtańsza (90), ale kolejny krok kosztuje 900, co daje 990. Najpierw wykonanie mnożenia pierwszej pary kosztuje 190. - Odczytanie odpowiedzi z niewłaściwej komórki.
dimsma o jeden element więcej niż jest macierzy, więc odpowiedzią jestbest[0][m-1], a niebest[0][m]. - Iterowanie po
leftw górę w zewnętrznej pętli. Wierszleftodczytuje wtedybest[split][right]z późniejszego wiersza, który wciąż ma wartość 0. Umieść szerokość w zewnętrznej pętli albo odliczajleftw dół. - Pominięcie pojedynczej macierzy.
[3, 7]musi zwracać 0, a w R pętla2:(m-1)staje się2:1i wykonuje się wstecz, więc dodaj warunek ochronny.
Najczęstsze pytania3
Jaka jest złożoność czasowa mnożenia łańcucha macierzy?
Tabela zawiera około n²/2 odcinków, a każdy z nich sprawdza do n podziałów, więc programowanie dynamiczne działa w czasie O(n³) i zużywa O(n²) pamięci. Zwykła rekurencja bez zapamiętywania wyników wykonuje 3^(n-1) wywołań dla n macierzy.
Dlaczego kolejność mnożenia macierzy ma znaczenie?
Mnożenie macierzy jest łączne, więc (AB)C i A(BC) dają tę samą macierz, ale macierze pośrednie różnią się rozmiarem. W pierwszym przykładzie (AB)C tworzy macierz 4 × 3 i kosztuje 264, podczas gdy A(BC) tworzy macierz 10 × 12 i kosztuje 840.
Jak znaleźć optymalny sposób nawiasowania?
Zapisz zwycięski podział w choice[left][right] obok best[left][right]. Aby wypisać wynik, w przypadku pojedynczej macierzy wypisz jej nazwę; w przypadku dłuższego fragmentu wypisz nawias otwierający, część do choice[left][right], część po nim i nawias zamykający. Zwiększa to zużycie pamięci o O(n²).
Podobne zadania
Zadania oparte na tych samych pomysłach. Rozwiązanie dwóch lub trzech utrwala schemat.
def matrixChainOrder(dims):
# Napisz kod tutajTest #1
Test #2
Test #3
Argument
dims = [4, 10, 3, 12]
Oczekiwany wynik
264