Dinamik Programlamayı Anlamak Böylece Etkin Bir Şekilde Kullanabilirsiniz

Bu makale üretim geliştirmeyle ilgili değildir ancak programlamayla ilgilidir. Dinamik Programlamayı (DP) ve önceki hesaplama deneyiminin etkili bir şekilde nasıl kullanılacağını tartışacağım. Umarım bunu ilginç bulacaksınız.

Dinamik Programlamaya Giriş

Dinamik Programlama terimi ilk olarak 1950'li yıllarda bilgisayar teknolojisinin önde gelen uzmanlarından biri olan ünlü Amerikalı matematikçi Richard Bellman tarafından kullanıldı . Dinamik Programlama (DP), karmaşık görevleri daha küçük alt problemlere bölerek çözme yöntemidir.

DP'nin çözebileceği türden problemlerin iki kriteri karşılaması gerekir:

1. Optimum altyapı . Dinamik programlama, daha küçük alt problemlerin çözümünün ilk problemi çözmek için kullanılabileceği anlamına gelir. Optimum altyapı “Böl ve Fethet” paradigmasının temel özelliğidir.

Klasik bir uygulama örneği, problemi yinelemeli olarak en basit alt problemlere (boyut 1 diziler) böldüğümüz ve ardından her birini temel alarak hesaplamalar yaptığımız birleştirme sıralama algoritmasıdır. Sonuçlar, ilk katman elde edilene kadar bir sonraki katmanı (daha büyük alt problemleri) çözmek için kullanılır.

2. Örtüşen alt problemler . Bilgisayar bilimlerinde, eğer problem birkaç kez yeniden kullanılan alt problemlere bölünebiliyorsa, problemin örtüşen alt problemlere sahip olduğu söylenir. Başka bir deyişle, aynı kodu aynı giriş verileriyle ve aynı sonuçlarla çalıştırmak. Bu problemin klasik bir örneği, aşağıda inceleyeceğimiz Fibonacci dizisindeki N'inci elemanın hesaplanmasıdır.

DP'nin Böl ve Fethet paradigmasının kullanımının özel bir durumu veya onun daha karmaşık bir versiyonu olduğunu söyleyebilirsiniz. Desen, çok sayıda farklı kombinasyonun hesaplandığı kombinatorik içeren görevleri çözmek için çok uygundur, ancak öğelerin N miktarı sıklıkla monoton ve aynıdır.

Optimal altyapıya sahip problemlerde ve örtüşen alt problemlerde, eğer kaba kuvvet yaklaşımını uygularsak, çok sayıda tekrarlanan hesaplamalar ve işlemlerle karşılaşırız. DP, iki ana yaklaşımı kullanarak çözümü optimize etmemize ve hesaplamanın iki katına çıkmasını önlememize yardımcı olur: not alma ve tablolama:

1. Notlandırma (yukarıdan aşağıya yaklaşım) yineleme yoluyla uygulanır. Bir görev daha küçük alt problemlere bölünür, sonuçları bir belleğe aktarılır ve tekrar tekrar kullanılarak orijinal problemi çözmek için birleştirilir.

• Eksileri: Bu yaklaşım, özyinelemeli yöntem çağrıları aracılığıyla yığın belleğini kullanır
• Artıları: DP görevlerine yönelik esneklik.

2. Tablolama (aşağıdan yukarıya yaklaşım), yinelemeli bir yöntem kullanılarak uygulanır. En küçüğünden başlangıcına kadar alt problemler ardı ardına iteratif olarak hesaplanır.

• Eksileri: sınırlı uygulama aralığı. Bu yaklaşım, başlangıçta alt problemler dizisinin tamamının anlaşılmasını gerektirir. Ancak bazı problemlerde bu mümkün olmuyor.
• Artıları: Her şey tek bir işlev içinde çalıştırıldığı için verimli bellek kullanımı.

Teori kulağa sıkıcı ve anlaşılmaz gelebilir; gelin bazı örneklere bakalım.

Problem: Fibonacci Dizisi

DP'nin klasik bir örneği, her bir öğenin önceki iki öğenin toplamı olduğu ve birinci ve ikinci öğelerin 0 ve 1'e eşit olduğu Fibonacci dizisindeki N'inci öğenin hesaplanmasıdır.

Hipotez yoluyla, bir değeri hesaplamak için bir öncekini bulmamız gerektiğinden, başlangıçta optimal altyapının doğasına odaklanıyoruz. Önceki değeri hesaplamak için ondan önce gelen değeri bulmamız gerekir, vb. Çakışan alt görevlerin doğası aşağıdaki şemada gösterilmektedir.

Bu görev için üç duruma bakacağız:

1. Basit yaklaşım: dezavantajları nelerdir?
2. Notlandırmayı kullanan optimize edilmiş bir çözüm
3. Tablolamayı kullanan optimize edilmiş bir çözüm

Basit/Kaba Kuvvet Yaklaşımı

Aklınıza gelebilecek ilk şey yinelemeyi girmek, önceki iki öğeyi özetlemek ve sonuçlarını vermektir.

 /** * Straightforward(Brute force) approach */ fun fibBruteForce(n: Int): Int { return when (n) { 1 -> 0 2 -> 1 else -> fibBruteForce(n - 1) + fibBruteForce(n - 2) } }

Aşağıdaki ekranda, dizideki beşinci öğeyi hesaplamak için bir yığın işlev çağrısı görebilirsiniz.

fib(1) fonksiyonunun beş kez, fib(2) ise üç kez çağrıldığına dikkat edin. Tek imzalı, aynı parametrelere sahip işlevler tekrar tekrar başlatılır ve aynı şeyi yapar. N sayısı artırıldığında ağaç doğrusal olarak değil üstel olarak artar, bu da hesaplamaların çok büyük bir şekilde tekrarlanmasına yol açar.

Matematik Analizi:

Zaman Karmaşıklığı: O(2^n),

Uzay Karmaşıklığı: O(n) -> özyinelemeli ağacın maksimum derinliğiyle orantılıdır, çünkü bu, örtülü işlev çağrıları yığınında bulunabilecek maksimum öğe sayısıdır.

Sonuç: Bu yaklaşım son derece verimsizdir. Örneğin 30. elementin hesaplanması için 1.073.741.824 işlem yapılması gerekmektedir.

Not Alma (Yukarıdan Aşağıya Yaklaşım)

Bu yaklaşımda uygulama, bellek tahsisi dışında yukarıda belirtilen "kaba kuvvet" çözümünden çok da farklı değildir. Yığımızda tamamlanan herhangi bir fib() fonksiyonunun hesaplamalarının sonuçlarını topladığımız değişken not olsun.

Bir tamsayı dizisine sahip olmanın ve buna indeksle atıfta bulunmanın yeterli olacağı unutulmamalıdır, ancak kavramsal netlik adına bir karma haritası oluşturulmuştur.

 /** * Memoization(Top-down) approach */ val memo = HashMap<Int, Int>().apply { this[1] = 0 this[2] = 1 } fun fibMemo(n: Int): Int { if (!memo.containsKey(n)) { val result = fibMemo(n - 1) + fibMemo(n - 2) memo[n] = result } return memo[n]!! }

Tekrar işlev çağrısı yığınına odaklanalım:

• Notta sonucu yazan ilk tamamlanan işlev, vurgulanan fib(2) dir. Kontrolü vurgulanan fib(3) e döndürür.
• Vurgulanan fib(3) fib(2) ve fib(1) çağrılarının sonuçlarını topladıktan sonra değerini bulur, çözümünü nota girer ve kontrolü fib(4) e döndürür.
• Daha önceki deneyimi yeniden kullanma aşamasına ulaştık; kontrol fib(4) 'e geri döndüğünde fib(2) çağrısı kendi sırasını bekler. fib(2) ise ( fib(1) + fib(0) çağırmak yerine, nottaki bitmiş çözümün tamamını kullanır ve onu hemen döndürür.
• fib(4) hesaplanır ve kontrolü yalnızca fib(3) başlatması gereken fib fib(5) öğesine döndürür. Son benzetmede, fib(3) hesaplama yapmadan anında nottan bir değer döndürür.

Fonksiyon çağrılarının ve hesaplamaların sayısında bir azalma gözlemleyebiliyoruz. Ayrıca N arttığında katlanarak daha az azalma olacaktır.

Matematik Analizi:

Zaman Karmaşıklığı: O(n)

Uzay Karmaşıklığı: O(n)

Sonuç: Asimptotik karmaşıklıkta açık bir fark var. Bu yaklaşım onu ilkel çözüme göre zaman açısından doğrusal hale getirmiş, bellekte ise arttırmamıştır.

Tablolama (aşağıdan yukarıya yaklaşım)

Yukarıda belirtildiği gibi, bu yaklaşım, daha küçük bir alt problemden daha büyük bir alt probleme doğru yinelemeli hesaplamayı içerir. Fibonacci örneğinde en küçük “alt problemler” dizideki sırasıyla 0 ve 1 numaralı birinci ve ikinci öğelerdir.

Elementlerin birbirleriyle nasıl ilişki kurduğunun çok iyi farkındayız ve bu şu formülle ifade edilir: fib(n) = fib(n-1) + fib(n-2) . Önceki unsurları bildiğimiz için bir sonrakini, ondan sonrakini vb. kolaylıkla hesaplayabiliriz.

Bildiğimiz değerleri toplayarak bir sonraki unsuru bulabiliriz. İstenilen değeri bulana kadar bu işlemi döngüsel olarak uyguluyoruz.

 /** * Tabulation(Bottom-up) approach fun fibTab(n: Int): Int { var element = 0 var nextElement = 1 for (i in 2 until n) { val newNext = element + nextElement element = nextElement nextElement = newNext } return nextElement }

Matematik Analizi:

Zaman Karmaşıklığı: O(n)

Uzay Karmaşıklığı: O(1)

Sonuç: Bu yaklaşım, hız açısından not alma kadar etkilidir ancak sabit miktarda bellek tüketir.

Sorun: Benzersiz İkili Ağaçlar

Daha karmaşık bir soruna bakalım: N düğümden oluşturulabilecek yapısal olarak benzersiz tüm ikili ağaçların sayısını bulmamız gerekiyor.

İkili ağaç, her düğümün ikiden fazla alt öğeye sahip olmadığı hiyerarşik bir veri yapısıdır. Genel bir kural olarak, ilkine ana düğüm adı verilir ve iki çocuğu vardır; sol çocuk ve sağ çocuk.

N = 3 için bir çözüm bulmamız gerektiğini varsayalım. Üç düğüm için yapısal olarak benzersiz 5 ağaç vardır. Bunları kafamızda sayabiliriz ama N artarsa varyasyonlar çok artar ve bunları kafamızda görselleştirmek imkansız hale gelir.

Bu görev kombinatoriklere atfedilebilir. Hangi kombinasyonların oluşturulabileceğini ve bunların oluşumu için nasıl bir model bulabileceğimizi bulalım.

1. Her ağaç en üst düğümden (Ağacın Tepe Noktası) başlar. Ağaç daha sonra derinlemesine genişler.
2. Her düğüm, ekranda gösterildiği gibi yeni bir alt ağacın (alt ağacın) başlangıcıdır. Sol alt ağaç yeşil, sağ alt ağaç ise kırmızı renktedir. Her birinin kendi tepe noktası vardır.

Kavramsal düzeyde N = 6 olan bir görev örneğine bakalım. Hesaplama fonksiyonumuzu numOfUniqueTrees(n: Int) olarak adlandıracağız.

Örneğimizde, biri daha önce bahsedilen prensibe göre ağacın tepe noktasını, diğer 5'i ise geri kalanını oluşturan 6 düğüm verilmiştir.

Artık geri kalan düğümlerle etkileşime giriyoruz. Bu çeşitli şekillerde yapılabilir. Örneğin, sol alt ağacı oluşturmak için beş düğümün tamamını kullanarak veya beş düğümün tamamını sağ alt ağaca göndererek. Veya düğümleri ikiye bölerek (solda 2 ve sağda 3) (aşağıdaki ekrana bakın), bu tür varyantlardan sınırlı sayıda elde ederiz.

numOfUniqueTrees(6) sonucunu elde etmek için, düğümlerimizi dağıtmak için tüm değişkenleri dikkate almamız gerekir. Bunlar tabloda gösterilmektedir:

Tabloda düğümlerin 6 farklı dağılımı gösterilmektedir. Her dağılım için kaç tane benzersiz ağaç üretilebileceğini bulup bunları toplarsak nihai sonuca ulaşmış oluruz.

Dağıtım için benzersiz ağaçların sayısı nasıl bulunur?

İki parametremiz var: Sol Düğümler ve Sağ Düğümler (tablonun sol ve sağ sütunları).

Sonuç şuna eşit olacaktır: numOfUniqueTrees(leftNodes) * numOfUniqueTrees(rightNodes) .

Neden? Solda, X benzersiz ağacımız olacak ve her biri için, Y benzersiz ağaç varyasyonunu sağ tarafa koyabileceğiz. Sonucu elde etmek için bunları çarpıyoruz.

Hadi İlk Dağılımın Varyasyonlarını Bulalım (5 Sol, 0 Sağ)

numOfUniqueTrees(5) * numOfUniqueTrees(0) , çünkü sağda düğümümüz yok. Sonuç numOfUniqueTrees(5) olur - soldaki sabit sağdaki benzersiz alt ağaçların sayısı.

numOfUniqueTrees(5) hesaplanıyor.

Şimdi en küçük alt problemimiz var. Daha büyüğüyle yaptığımız gibi onunla da çalışacağız. Bu aşamada DP görevlerinin özelliği açıktır: optimal altyapı, özyinelemeli davranış.

Tepe noktasına bir düğüm (yeşil düğüm) gönderilir. Geriye kalan (dört) düğümü önceki deneyime benzer şekilde dağıtıyoruz (4:0), (3:1), (2:2), (1:3), (0:4).

İlk dağılımı hesaplıyoruz (4:0). Daha önceki benzetmeyle numOfUniqueTrees(4) * numOfUniqueTrees(0) -> numOfUniqueTrees(4) eşittir.

numOfUniqueTrees(4) hesaplanıyor. Köşeye bir düğüm atarsak 3 tane kalır.

Dağılımlar (3:0), (2:1), (1:2), (0:3).

2 düğüm için yalnızca iki benzersiz ikili ağaç vardır; 1 - bir için. Daha önce üç düğüm için benzersiz ikili ağaçların 5 çeşidinin bulunduğunu belirtmiştik.

Sonuç olarak — dağılımlar(3:0), (0:3) 5'e eşittir, (2:1), (1:2) — 2. 5 + 2 + 2 + 5'i toplarsak 14 elde ederiz. numOfUniqueTrees(4) = 14.

Hesaplama sonucunu not alma deneyimine göre değişken nota girelim. Dört düğüm için varyasyon bulmamız gerektiğinde, bunları tekrar hesaplamayacağız, ancak daha önceki deneyimlerimizi yeniden kullanacağız.

(4:0), (3:1), (2:2), (1:3), (0:4) dağılımlarının toplamına eşit olan (5:0) hesaplamasına dönelim. (4:0) = 14 olduğunu biliyoruz. Haydi nota dönelim, (3:1) = 5, (2:2) = 4 (solda 2 varyasyon * sağda 2), (1:3) = 5, (0:4) = 14. Bunları toplarsak 42, numOfUniqueTrees(5) = 42 elde ederiz.

Dağılımların toplamına eşit olan numOfUniqueTrees(6) hesaplamasına dönelim.

(5:0) = 42, (4:1) = 14, (3:2) =10 (5 sol * 2 sağ), (2:3) = 10, (1:4) = 14, (0: 5) = 42. Bunları toplarsak 132, numOfUniqueTrees(5) = 132 elde ederiz.

Görev çözüldü!

Sonuç: N = 6 olan çözümdeki örtüşen alt problemlere dikkat edelim. Basit çözümde numOfUniqueTrees(3) 18 kez çağrılacaktır (aşağıdaki ekran). Artan N ile aynı hesaplamanın tekrarları çok daha fazla olacaktır.

(5 sol, 0 sağ) ve (0 sol, 5 sağ) için benzersiz ağaç sayısının aynı olacağını vurguluyorum. Yalnızca bir durumda solda, diğerinde sağda olacaklar. Bu aynı zamanda (4 sol, 1 sağ) ve (1 sol, 4 sağ) için de geçerlidir.

Dinamik programlamanın bir yaklaşımı olarak notlandırma, böylesine karmaşık bir görev için çözümü optimize etmemize olanak sağladı.

Uygulama

 class Solution { fun calculateTees(n: Int, memo:Array<Int?>): Int { var treesNum = 0 if(n < 1) return 0 if(n == 2) return 2 if(n == 1) return 1 if(memo[n]!=null) return memo[n]!! for (i in 1..n){ val leftSubTrees = calculateTees( i - 1, memo) val rightSubTrees = calculateTees(n - i, memo) treesNum += if(leftSubTrees>0 && rightSubTrees>0){ leftSubTrees*rightSubTrees } else leftSubTrees+leftSubTrees } memo[n] = treesNum return treesNum } } 

Çözüm

Bazı durumlarda görevleri Dinamik Programlama yoluyla çözmek, büyük miktarda zaman tasarrufu sağlayabilir ve algoritmanın maksimum verimlilikle çalışmasını sağlayabilir.

Bu makaleyi sonuna kadar okuduğunuz için teşekkür ederiz. Sorularınızı yanıtlamaktan memnuniyet duyarım.

kaydeden Ayat Rakhishev