Dinamik Grafik Programlama

Error

Dinamik programlama kullanan çözümlerde dinamiklerin hesaplanma sırası önemlidir (önceden mevcut olanın bağlı olduğu değerlerin hesaplanması gerekir).
Bu nedenle, yönlendirilmiş asiklik grafiklerde dinamik programlama kullanmak gerekiyorsa, başlangıçta grafiğin topolojik bir sıralamasını oluşturmak gerekir. Ardından, oluşturulan topolojik sıralama sırasına göre köşeleri sıralayarak dinamikleri hesaplayın (soruna bağlı olarak, geçiş sırası kaynaklardan alıcılara veya tersi olabilir).
 
 

Grafik döngüler içeriyorsa (topolojik sıralama yoktur), iki püf noktası yardımcı olabilir:

1) Dinamikleri n kez hesaplayın, burada n, grafikteki köşe sayısıdır (Ford-Bellman algoritmasına benzeterek). Ancak bu, asimptotikleri artırır ve genel olarak nadiren verimlidir.

2) Grafik yoğunlaşmasını oluşturun. Orijinal grafiğin güçlü bir şekilde bağlantılı her bileşeni için sorunu ayrı ayrı çözün. Yoğunlaştırılmış grafik döngüsel değildir ve bunun için, güçlü bir şekilde bağlı bileşenler için hesaplanan değerleri köşe değerleri olarak kullanırken, topolojik sıralama ile standart yaklaşımı kullanabilirsiniz. Bu yöntem esas olarak kullanılır.