Bölme noktası
- Algoritmalar kursu
- İleri seviye
- Ders 23/56
- 4 dk
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.
Başlangıç kodu
def init_dims():
# Boyut dizisini döndür
return [10, 20, 30, 40]
def matrix_chain(dims):
# En düşük maliyeti bulÖrnek çözüm
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()))Beklenen çıktı
18000
Soru ve cevaplar
Dersin sorularını cevaplarıyla birlikte inceleyebilirsin. Kendini denemek istersen dersi interaktif olarak çöz.
1 Bölme noktası: kavramları eşleştir
| Kavram | Anlamı |
|---|---|
i≤k<j |
Bölme aralığı |
dims |
Boyut dizisi |
m[i][j] |
En düşük maliyet |
m[i][i] |
0 |
2 Üç matris [10,20,30,40] için en düşük maliyet?
- 6000
- 24000
- 18000 Doğru cevap
- 32000
Açıklama: m[1][3] = 18000.
3 iç döngü değişkeni
Soru
for k in range(i, ____):
Cevap
for k in range(i, j):Açıklama: j doğru.