ADS úlohy E - Matsoucin

Vím-li, jak efektivně uzávorkovat

$n$ matic, pomůže mi to k tomu, abych věděl, jak uzávorkovat

$n+1$ matic?

Příklad: součin délky 4+1:

$ABCDE=(ABCD)(E)=(ABC)(DE)=(AB)(CDE)=(A)(BCDE)$

Z něj je vidět, že nemohu postupovat tak, že zjistím uzávorkování pro první matice, přidám k nim další a pak provedu triviální výpočet. Musím postupovat slučováním - nejprve zjistím složitost pro všechny součiny délky 2, pak délky 3… Dále je vidět, že pro hledání složitosti násobení

$n+1$ matic musím provést

$n+1$ porovnání pro danou posloupnost.

Vytvořím si tak následující tabulku:

$\left(\begin{array}{ccccc}A& B& C& D& E\\ AB& BC& CD& DE\\ ABC& BCD& CDE\\ ABCD& BCDE\\ ABCDE\end{array}\right)$

Každá z těchto položek obsahuje následující vlastnosti:

• jaké matice násobím (z názvu)
• optimální náročnost násobení (samostatné matice mají náročnost 0)
• rozměry součinu - levý a pravý, z hlediska algoritmu
• dělení - mezi kterými maticemi musím udělat závorky (nejprve uzavírací, pak otevírací)

Počítám-li od jedničky, pak pro výpočet složitosti násobení na pozici

$[i,j]$ musím porovnat násobení na pozicích

$[i-k,j]$ a

$[k,j-k+1]$pro

$1\le k<i$. Konkrétně - hledám-li vhodné uzávorkování pro pole

$BCD$, pak porovnávám ty součiny, které začínají

$B$ a končí

$D$ (bez vynechání).

Přidaná náročnost je rovna součinu pravého rozměru levé matice a levého rozměru pravé matice (k tomu je potřeba připočíst náročnost původních matic).
Rozměry součinu mohu určit okamžitě, bez počítání složitosti - levý rozměr první matice x pravý rozměr poslední matice.

Proč? Součin

$(AB)(CD)$ vyprodukuje matice o rozměrech

$a\times b,b\times c$, takže musím ještě připočst součin těchto matic, což je

$abc$.

Nakonec je otázka - jak se dobrat k výsledku? Vzdálenost znám, ale potřebuju i konstruktivní odpověď.

Pro každé pole si uložím číslo matice, na které druhý částečný součin začínal (nebo první končil - konzistentně!). Jakmile mám tabulku vyplněnou, jdu od spoda nahoru rekurzivně - výsledek rozdělím závorkami a poté opět hledám, jak rozdělit uzávorkované části.

Například:

$ABCDE$ říká

$B$ - výraz tak rozdělím na

$(AB)(CDE)$ a hledám pole označené

$CDE$ (

$AB$ už je triviální součin). U

$CDE$ najdu napsáno

$E$, takže celkové uzávorkování je

$(AB)(CD)(E)$.

Složitost:

Pro hledání nejlepšího uzávorkování délky

$x$ budu muset porovnat

$x$ čísel. Ke každému z těchto čísel také musím přičíst určitý součin. To, kolik polí budu muset vyplnit, záleží na řádku; mám-li

$10$ matic a porovnávám-li násobení

$5$ z nich, pak budu vyplňovat jenom

$6$ polí (

$1-5,2-6\dots 6-10$). Informaci o rozdělení držím společně s minimem, takže toto složitost neovlivní.

Pro

$n$ matic tak musím vyplnit

$n-1+n-2+\cdots +1$ polí, což je

$\frac{n(n-1)}{2}$. Při zpětném vyhledávání projdu nejhůře celou tabulku (ale nikdy se nebudu muset vracet, protože každé uzávorkování jednotlivé součiny pouze rozdělí). Složitost je tak

$O(n^2)$.