Mátrix láncszorzás

1. Sablon:Label

Mátrixláncszorzás problémája

Definíció

A mátrixláncszorzás problémája a mátrixok egy adott sorrendjének összeszorzásával kapcsolatos. A cél az, hogy megtaláljuk a zárójelezés optimális módját, amely minimalizálja a szorzások számát. Fontos megjegyezni, hogy a mátrixok sorrendjét nem változtatjuk meg.

Ha három mátrixot szorzunk, például $A$, $B$, és $C$, akkor a szorzás kétféleképpen végezhető el: $(AB)C\text{vagy}A(BC)$ A különböző zárójelezések különböző számú elemi szorzást igényelhetnek.

Probléma megfogalmazása

Adott $n$ mátrix dimenziói:

• Mátrix $A_i$ mérete: $p_{i-1}\times p_i$.

A cél: minimalizálni a következő szorzások számát: $\text{szorzás száma}=p_{i-1}\cdot p_i\cdot p_j$

Dinamikus programozási megoldás

Az optimalizációs probléma megoldható dinamikus programozással az alábbi állapotfüggvénnyel:

$m[i,j]=\text{minimum szorzásszám az }{A}_i\text{ és }{A}_j\text{ közötti mátrixok összeszorzására.}$

Rekurzív reláció: $m[i,j]=\{\begin{array}{cc}0& \text{ha }i=j,\\ \underset{i\le k<j}{\min }\{m[i,k]+m[k+1,j]+p_{i-1}\cdot p_k\cdot p_j\}& \text{ha }i<j.\end{array}$

Python implementáció

Az alábbi Python kód implementálja a mátrixláncszorzás problémáját dinamikus programozással.

def matrix_chain_order(p):
    """
    Dinamikus programozási megoldás a mátrixláncszorzás problémára.
    
    Args:
        p: Mátrixok dimenzióit tartalmazó lista. Ha p = [10, 20, 30], akkor
           A1 dimenziója 10x20, A2 dimenziója 20x30.
    
    Returns:
        m: A minimális szorzásszám mátrix.
        s: A zárójelezés helyeit tartalmazó mátrix.
    """
    n = len(p) - 1  # Mátrixok száma
    m = [[0] * n for _ in range(n)]  # Szorzásszámokat tároló mátrix
    s = [[0] * n for _ in range(n)]  # Zárójelezési helyeket tároló mátrix

    for l in range(2, n + 1):  # Szorzandó mátrixok lánchosszát iteráljuk
        for i in range(n - l + 1):
            j = i + l - 1
            m[i][j] = float('inf')
            for k in range(i, j):
                q = m[i][k] + m[k + 1][j] + p[i] * p[k + 1] * p[j + 1]
                if q < m[i][j]:
                    m[i][j] = q
                    s[i][j] = k

    return m, s


def print_optimal_parens(s, i, j):
    """
    Rekurzív függvény a zárójelezés kiírására.
    
    Args:
        s: A zárójelezési helyeket tartalmazó mátrix.
        i: A kezdő mátrix indexe.
        j: A végső mátrix indexe.
    """
    if i == j:
        print(f"A{i+1}", end="")
    else:
        print("(", end="")
        print_optimal_parens(s, i, s[i][j])
        print_optimal_parens(s, s[i][j] + 1, j)
        print(")", end="")


# Példa bemenet
dimensions = [10, 20, 30, 40, 30]  # Mátrixok dimenziói: A1: 10x20, A2: 20x30, A3: 30x40, A4: 40x30

# Megoldás futtatása
m, s = matrix_chain_order(dimensions)

# Minimális szorzásszám
print("Minimális szorzásszám:", m[0][len(dimensions) - 2])

# Optimális zárójelezés
print("Optimális zárójelezés:", end=" ")
print_optimal_parens(s, 0, len(dimensions) - 2)

Példa bemenet és kimenet

Bemenet

Mátrixok dimenziói: $A_1:10\times 20$, $A_2:20\times 30$, $A_3:30\times 40$, $A_4:40\times 30$.

Kimenet

Minimális szorzásszám: 30000 Optimális zárójelezés: ((A1(A2A3))A4)

Magyarázat

A program kiszámolja az optimális zárójelezést úgy, hogy minimalizálja a szorzásszámot. A zárójelezési sorrend $((A_1(A_2{A}_3))A_4)$ minimalizálja az elemi szorzások számát, amely ebben az esetben 30 000.

Ez az algoritmus $O(n^3)$ időbonyolultságú, amely megfelelő nagyobb, de nem hatalmas mátrixláncok esetén.

• Sablon:En: Sablon:T+