Özet - Matrix chain
- Algoritmalar kursu
- İleri seviye
- Ders 24/56
- 4 dk
En küçük çarpım maliyetini yazdıran mini görev yaparsın.
Özet - Matrix chain
Bu grupta matris zinciri çarpımının en düşük maliyetini dinamik programlama ile bulmayı öğrendin. Boyut dizisi, DP tablosu ve bölme noktası birleşince çözüm oluşur.
Şimdi tüm parçaları bir araya getiren bir fonksiyon yazacaksın. Bu özet, grubun kavramlarını tek bir kodda birleştirir.
Uygulama min_chain_cost fonksiyonu
min_chain_cost(dims) yaz. DP tablosunu kur, iç içe döngü ile doldur ve m[1][n-1]'i döndür. print(min_chain_cost([10, 20, 30, 40])) ile 18000 yazdır.
Başlangıç kodu
def min_chain_cost(dims):
# En düşük maliyeti DP ile bulÖrnek çözüm
def min_chain_cost(dims):
# En düşük maliyeti DP ile 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(min_chain_cost([10, 20, 30, 40]))Beklenen çıktı
18000
Soru ve cevaplar
Dersin sorularını cevaplarıyla birlikte inceleyebilirsin. Kendini denemek istersen dersi interaktif olarak çöz.
1 matrix_chain hangi tablo hücresini döndürür?
- m[0][0]
- m[0][n]
- m[n][n]
- m[1][n-1] Doğru cevap
Açıklama: m[1][n-1] tüm zincirin maliyetidir.
2 boyut dizisi
Soru
dims = init_____()
Cevap
dims = init_dims()Açıklama: dims doğru.
3 Özet - Matrix chain: kavramları eşleştir
| Kavram | Anlamı |
|---|---|
init_dims |
Boyut |
init_table |
Tablo |
matrix_chain |
Maliyet |
k |
Bölme |