dinamik programlama - en uygun kırılma noktası

Question

Dinamik programlamayı kullanarak, matris zinciri çarpma probleminin n^3 zamanında çözülebildiğini, en uygun ikili ağaç problemi için de n^3 zaman aldığımızı, ancak n^2'ye kadar optimize et. Bu neden? Bunun matris çarpma probleminde, M (i, n) zincirinin en uygun kırılma noktasının M (i + 1, n) zincirinin optimal kırılma noktasından daha büyük olabileceğini söyleyen bir deyim var. Birisi bunu anlamama yardımcı olabilir mi? Matris çarpma probleminde bu neden doğrudur, ama en uygun ikili ağaç probleminde değil? I2 bir alt aralığıdır tuşları I1 bir aralık dikkate alındığında

Teşekkür

Answer 1

, I1 üzerinde optimum ikili ağacın sorgu maliyet (bu I2 optimum ikili ağacın sorgu maliyeti daha büyüktür Oldukça sezgisel olmalı, ancak resmi olarak, I2 için en uygun ağacı al ve tekrar tekrar standart algoritma yoluyla anahtarları sil.). Bu, en uygun kırılma noktasını iki yarım arasındaki dengeleme sürecinin bir türü olarak bulma sürecini düşünebileceğiniz anlamına gelir.

Bu, matris zinciri için geçerli değildir: çarpma maliyeti (100, 100), (100, 100), (100, 100), (100, 100), (100, 1) 'den çok daha büyüktür, çünkü iki matris-vektör çarpımı, bir matris matrisinden daha ucuz olan çok'dur.