Matrix Chain Multiplication
Bir matris zinciri dims ile tanımlanır: i matrisi dims[i] satıra ve dims[i+1] sütuna sahiptir; dolayısıyla her matris bir sonrakine uyar. p × q boyutundaki bir matrisi q × r boyutundaki bir matrisle çarpmak p × q × r skaler çarpma işlemi gerektirir ve p × r boyutunda bir matris verir. Parantezleri yerleştirmenin her yolu aynı sonucu verir, ancak maliyetleri aynı değildir. Tüm zinciri çarpmak için gereken en az skaler çarpma sayısını döndürün.
Fonksiyon
- dimsinteger-array
- zincir boyunca boyutlar: i matrisi dims[i] × dims[i+1] boyutlarındadır
- Döndürürinteger
- tüm zinciri çarpmak için gereken en az sayıda skaler çarpım
Kısıtlar
2 ≤ dims.length ≤ 100, bu nedenle zincir 1 ile 99 matris içerir.1 ≤ dims[i] ≤ 100- Yanıt en fazla 98 × 106'dır; 32 bitlik işaretli bir tamsayının sınırlarının oldukça içindedir.
Örnekler
- Girdi
- dims = [4, 10, 3, 12]
- Çıktı
- 264
- Açıklama
- İlk ikisini çarpmak 4 × 10 × 3 = 120 maliyetlidir ve 4 × 3'lük bir matris bırakır; bunun 3 × 12'lik matrisle çarpılması 144 ekler: 264. Diğer sıralama 360 + 480 = 840 maliyetlidir.
- Girdi
- dims = [6, 2, 7, 3, 5]
- Çıktı
- 132
- Açıklama
- 2 × 7'yi 7 × 3 (42) ile, 2 × 3 sonucunu 3 × 5 (30) ile, ardından 6 × 2'yi 2 × 5 sonucuyla (60) çarp: toplam 132.
- Girdi
- dims = [3, 7]
- Çıktı
- 0
- Açıklama
- Yalnızca bir matris var, 3 × 7, bu yüzden hiçbir çarpma yapılmaz ve maliyet 0'dır.
Ek soru
En düşük maliyete ulaşan farklı parantezlemelerin sayısını da sayabilir misin?
İpuçları
Tek tek açın. Her biri biraz daha fazlasını gösterir.
İlk çarpımı unutun ve son çarpımı düşünün. Hangi sırayı seçerseniz seçin, son adım zincirin sol tarafındaki bir bölümün çarpımını geri kalan kısmın çarpımıyla çarpar.
leftverightsınırları arasındaki matrislerin çarpımı her zamandims[left] × dims[right]boyutlarında bir matristir. Dolayısıyla son adımda bu aralıksplitsınırında bölünürse maliyetidims[left] × dims[split] × dims[right]olur ve iki parça da aynı problemin daha küçük kopyalarıdır.Sınırlar
leftverightarasındaki matrisleri çarpmanın en düşük maliyetli yolunubest[left][right]içinde saklayın (tek bir matris için 0). Bu değer, sınırların kesinlikle arasında yer alan hersplitiçinbest[left][split] + best[split][right] + dims[left] × dims[split] × dims[right]ifadesinin minimumudur. Dar aralıkları geniş olanlardan önce hesaplayın.
Çözüm
Sıralama maliyeti değiştirir: ilk örnekte 840'a karşı 264. Son çarpıma bakın. Zincirin sol ve sağ kısımlarının çarpımlarını birleştirir ve her kısım, daha kısa bir zincirde aynı problemdir. Zincirin aralıklarını kapsayan bir tablo, her birini O(n³) zamanda bir kez çözer.
Basit özyineleme kullanarak her bölmeyi dene
Doğru, ama en büyük testlerde bitmiyor
Sezgi
Zincirin sınırlarını 0'dan m-1'e kadar numaralandır; burada m = dims.length: k sınırının boyutu dims[k]'dir. left ve right sınırları arasındaki matrisler, hangi sırayla çarpılırsa çarpılsın dims[left] × dims[right] boyutlarında bir matris verir. Dolayısıyla son adım bu aralığı split noktasında bölerse, iki bloğun içinde ne olduğundan bağımsız olarak maliyeti dims[left] × dims[split] × dims[right] olur. Her blok mümkün olan en düşük maliyetle oluşturulmalıdır; bu yüzden cheapest(left, right), tüm split noktaları için iki bloğun maliyetleri toplamı ile son adımın maliyetinin toplamları arasındaki en küçük değerdir. Her son adımı denemek, bunun doğruluğunu sağlar.
Aynı aralıkları tekrar tekrar çözer: n matris için 3^(n-1) çağrı gerekir; 20 matris için bu sayı yaklaşık 1.2 × 10^9 olurken, farklı aralıkların sayısı yalnızca yaklaşık m²/2'dir.
Algoritma
leftverightsınırları arasındaki matrisler içincheapest(left, right)yazın.right - left < 2ise tek bir matris vardır: 0 döndürün.- Aralarındaki her
splitdeğeri içincheapest(left, split),cheapest(split, right)vedims[left] × dims[split] × dims[right]değerlerini toplayın. - En küçük toplamı döndürün.
- Yanıt
cheapest(0, m-1)değeridir.
def matrixChainOrder(dims):
def cheapest(left, right):
# The fewest multiplications for the matrices between boundaries left and right
if right - left < 2:
return 0 # a single matrix costs nothing
best = None
for split in range(left + 1, right):
cost = (cheapest(left, split) + cheapest(split, right)
+ dims[left] * dims[split] * dims[right])
if best is None or cost < best:
best = cost
return best
return cheapest(0, len(dims) - 1)Memo ile özyineleme
Sezgi
Bir çağrı yalnızca left ve right değerlerine bağlıdır. Sonucunu memo[left][right] içinde sakla; her hücre başlangıçta, hiçbir gerçek maliyetin alamayacağı bir değer olan -1'i içersin ve sonraki çağrılar özyinelemeye başvurmak yerine hücreyi okusun. Yaklaşık m²/2 çiftin her biri, m'den az bölme denemesiyle bir kez çözülür: O(n³) ya da 99 matris için 161,700 bölme denetimi. Özyineleme, zincirin uzunluğundan daha derin olmaz; bu nedenle 100 sınır, herhangi bir çağrı yığınına sığar.
Algoritma
memo'yumsatır vemsütunla, her hücresi -1 olacak şekilde oluştur.cheapest(left, right)içinde, tek bir matrisi kapsayan aralık 0 döndürür; -1 dışında bir değer içeren hücre ise kayıtlı maliyetini döndürür.- Aksi takdirde her
splitnoktasının maliyetini, düz özyinelemede olduğu gibi hesapla ve en küçüğünü al. - Döndürmeden önce bu minimumu
memo[left][right]içine yaz. - Cevap
cheapest(0, m-1)olur.
def matrixChainOrder(dims):
m = len(dims)
# memo[left][right]: the answer for boundaries left and right, -1 while unknown
memo = [[-1] * m for _ in range(m)]
def cheapest(left, right):
if right - left < 2:
return 0 # a single matrix costs nothing
if memo[left][right] != -1:
return memo[left][right]
best = None
for split in range(left + 1, right):
cost = (cheapest(left, split) + cheapest(split, right)
+ dims[left] * dims[split] * dims[right])
if best is None or cost < best:
best = cost
memo[left][right] = best
return best
return cheapest(0, m - 1)Tabloyu genişliği uzatarak doldurun
Sezgi
Her hücre yalnızca daha dar aralıklara bağlıdır; bu nedenle döngüler best[left][right] değerlerini dar aralıklardan geniş aralıklara doğru doldurabilir. Genişlik 1 tek bir matrise karşılık gelir ve değeri 0 olarak kalır; daha geniş bir aralığa ulaştığınızda, her bölmenin iki parçası da önceden hesaplanmıştır. dims = [6, 2, 7, 3, 5] için:
- Genişlik 2:
best[0][2] = 84,best[1][3] = 42,best[2][4] = 105. - Genişlik 3:
best[0][3]değeri 78'dir (bölme 1: 0 + 42 + 36),best[1][4]değeri 72'dir (bölme 3: 42 + 0 + 30). - Genişlik 4: 1, 2 ve 3. bölmeler sırasıyla 0 + 72 + 60 = 132, 84 + 105 + 210 = 399 ve 78 + 0 + 90 = 168 verir; dolayısıyla
best[0][4] = 132.
1. sınırdaki en üst bölme, ikinci örnekte olduğu gibi 6 × 2 matrisinin en son çarpıldığı anlamına gelir. Zaman ve bellek kullanımı memo sürümüyle aynıdır ve özyineleme kullanılmaz.
Algoritma
m = dims.lengtholsun ve sıfırlardan oluşanm × mboyutunda birbesttablosu ayır.widthdeğerini 2'denm-1'e kadar döngüye sok. Bunun içinde,right = left + widthhâlâ bir sınır olduğu süreceleftdeğerini 0'dan başlayarak artır.- Bu aralık için,
left+1'denright-1'e kadar hersplitdeğeri içinbest[left][split] + best[split][right] + dims[left] × dims[split] × dims[right]değerini hesapla ve en küçüğünübest[left][right]içine kaydet. - Yanıt
best[0][m-1]içindedir.
def matrixChainOrder(dims):
m = len(dims)
# best[left][right]: the fewest multiplications for the matrices
# between boundary left and boundary right (0 for a single matrix)
best = [[0] * m for _ in range(m)]
for width in range(2, m):
for left in range(m - width):
right = left + width
low = None
for split in range(left + 1, right):
# the last product joins a dims[left] x dims[split] block
# with a dims[split] x dims[right] block
cost = best[left][split] + best[split][right] + dims[left] * dims[split] * dims[right]
if low is None or cost < low:
low = cost
best[left][right] = low
return best[0][m - 1]
Tuzaklar ve uç durumlar
- En ucuz çifti önce çarpmak.
[10, 10, 1, 9]dizisinde son çift en ucuzdur (90), ancak sonraki adım 900'e mal olur; toplam 990 eder. İlk çifti önce almak 190'a mal olur. - Yanıtı yanlış hücreden okumak.
dims, matris sayısından bir fazla öğe içerir; bu nedenle yanıtbest[0][m-1]olmalıdır,best[0][m]değil. - Dış döngüde
leftdeğerini artan yönde ilerletmek. Bu durumdaleftsatırı, henüz 0 olan sonraki bir satırdakibest[split][right]değerini okur. Genişliği dış döngüye alın veyaleftdeğerini geriye doğru sayın. - Tek matrisi gözden kaçırmak.
[3, 7]0 döndürmelidir; R'de2:(m-1)döngüsü2:1olur ve geriye doğru çalışır, bu nedenle bunu korumalı bir koşulla engelleyin.
Sıkça sorulan sorular3
Matris zinciri çarpımının zaman karmaşıklığı nedir?
Tabloda yaklaşık n²/2 aralık vardır ve her biri en fazla n bölme dener; bu nedenle dinamik programlama O(n³) zamanda ve O(n²) bellekle çalışır. Önbellekleme olmadan yapılan basit özyineleme, n matris için 3^(n-1) çağrı yapar.
Matris çarpımının sırası neden önemlidir?
Matris çarpımı birleşme özelliğine sahiptir; bu nedenle (AB)C ve A(BC) aynı matrisi verir, ancak ara matrislerin boyutları farklıdır. İlk örnekte (AB)C 4 × 3 boyutlarında bir matris oluşturur ve maliyeti 264’tür; A(BC) ise 10 × 12 boyutlarında bir matris oluşturur ve maliyeti 840’tır.
En uygun parantezlemeyi nasıl bulursunuz?
Kazanan bölmeyi choice[left][right] içinde, best[left][right] yanına kaydedin. Yazdırmak için tek bir matrisin adı yazdırılır; daha uzun bir aralıkta açılış parantezi, choice[left][right] öncesindeki bölüm, sonrasındaki bölüm ve kapanış parantezi yazdırılır. Bu, O(n²) bellek ekler.
Benzer problemler
Aynı fikirleri kullanan problemler. İki üçünü çözmek bir kalıbı kalıcı hale getirir.
def matrixChainOrder(dims):
# Kodu buraya yazınTest #1
Test #2
Test #3
Argüman
dims = [4, 10, 3, 12]
Beklenen Çıktı
264