Bölme noktası

En iyi bölme noktasını bulmayı öğrenirsin.

Bölme noktası k

Her m[i][j] için bir bölme noktası k seçilir: i ≤ k < j. Maliyet m[i][k] + m[k+1][j] + dims[i-1]·dims[k]·dims[j] olur.

Tüm k değerleri denenir ve en küçük maliyet seçilir. Bu, optimal alt yapı özelliğidir.

Tekrarlama bağıntısı

Bağıntı: m[i][j] = min(m[i][k] + m[k+1][j] + dims[i-1]*dims[k]*dims[j]) tüm k için. Zincir uzunluğu küçükten büyüğe hesaplanır.

Bu formül çakışan alt problemleri bir kez çözerek karmaşıklığı O(n³)'e düşürür.

Uygulama matrix_chain fonksiyonu

matrix_chain(dims) yaz. İç içe döngü ile m tablosunu doldur, m[1][n-1]'i döndür. print(matrix_chain(init_dims())) ile 18000 yazdır.

Örnek çözümü göster

def init_dims():
    # Boyut dizisini döndür
    return [10, 20, 30, 40]
def matrix_chain(dims):
    # En düşük maliyeti bul
    n = len(dims)
    m = [[0] * n for _ in range(n)]
    for length in range(2, n):
        for i in range(1, n - length + 1):
            j = i + length - 1
            m[i][j] = float('inf')
            for k in range(i, j):
                cost = m[i][k] + m[k + 1][j] + dims[i - 1] * dims[k] * dims[j]
                if cost < m[i][j]:
                    m[i][j] = cost
    return m[1][n - 1]
print(matrix_chain(init_dims()))

Kendini test et

Bölme noktası: kavramları eşleştir

i≤k<j

Bölme aralığı
dims

Boyut dizisi
m[i][j]

En düşük maliyet
m[i][i]

0
Üç matris [10,20,30,40] için en düşük maliyet?
- 6000
- 24000
- 18000
- 32000
Cevabı göster

18000 — m[1][3] = 18000.

iç döngü değişkeni

for k in range(i, ____):

Cevabı göster

for k in range(i, j):

Sıradaki ders: Özet - Matrix chain

Deneyiminizi Geliştiriyoruz

Çerez Tercihleri

Kesinlikle Gerekli Çerezler

Analitik Çerezler