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   . Dinamik Programlama (DP), karmaşık görevleri daha küçük alt problemlere bölerek çözme yöntemidir.  kullanıldı  DP'nin çözebileceği türden problemlerin iki kriteri karşılaması gerekir:    . 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. 1. Optimum altyapı  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.    . 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. 2. Örtüşen alt problemler  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:    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. 1. Notlandırma (yukarıdan aşağıya yaklaşım)    Bu yaklaşım, özyinelemeli yöntem çağrıları aracılığıyla yığın belleğini kullanır Eksileri:    DP görevlerine yönelik esneklik. Artıları:    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. 2. Tablolama (aşağıdan yukarıya yaklaşım),    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. Eksileri:    Her şey tek bir işlev içinde çalıştırıldığı için verimli bellek kullanımı. Artıları:  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:  Basit yaklaşım: dezavantajları nelerdir?  Notlandırmayı kullanan optimize edilmiş bir çözüm  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.     fonksiyonunun beş kez,   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. fib(1) fib(2)   Matematik Analizi:    O(2^n), Zaman 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. Uzay Karmaşıklığı:    Bu yaklaşım son derece verimsizdir. Örneğin 30. elementin hesaplanması için 1.073.741.824 işlem yapılması gerekmektedir. Sonuç:  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   dir. Kontrolü vurgulanan   e döndürür. fib(2) fib(3)  Vurgulanan     ve   çağrılarının sonuçlarını topladıktan sonra değerini bulur, çözümünü nota girer ve kontrolü   e döndürür. fib(3) fib(2) fib(1) fib(4)  Daha önceki deneyimi yeniden kullanma aşamasına ulaştık; kontrol   'e geri döndüğünde   çağrısı kendi sırasını bekler.   ise (   çağırmak yerine, nottaki bitmiş çözümün tamamını kullanır ve onu hemen döndürür. fib(4) fib(2) fib(2) fib(1) + fib(0)    hesaplanır ve kontrolü yalnızca   başlatması gereken fib   öğesine döndürür. Son benzetmede,   hesaplama yapmadan anında nottan bir değer döndürür. fib(4) fib(3) fib(5) fib(3)  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)    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. Sonuç:  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:   . Önceki unsurları bildiğimiz için bir sonrakini, ondan sonrakini vb. kolaylıkla hesaplayabiliriz. fib(n) = fib(n-1) + fib(n-2)  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)    Bu yaklaşım, hız açısından not alma kadar etkilidir ancak sabit miktarda bellek tüketir. Sonuç:  Sorun: Benzersiz İkili Ağaçlar  Daha karmaşık bir   bakalım: N düğümden oluşturulabilecek yapısal olarak benzersiz tüm ikili ağaçların sayısını bulmamız gerekiyor. soruna    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. İkili ağaç,  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.  Her ağaç en üst düğümden (Ağacın Tepe Noktası) başlar. Ağaç daha sonra derinlemesine genişler.  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   olarak adlandıracağız. fonksiyonumuzu numOfUniqueTrees(n: Int)  Ö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.     sonucunu elde etmek için, düğümlerimizi dağıtmak için tüm değişkenleri dikkate almamız gerekir. Bunlar tabloda gösterilmektedir:  numOfUniqueTrees(6)  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ğ)    , çünkü sağda düğümümüz yok. Sonuç   olur - soldaki sabit sağdaki benzersiz alt ağaçların sayısı.  numOfUniqueTrees(5) * numOfUniqueTrees(0) numOfUniqueTrees(5)    hesaplanıyor. numOfUniqueTrees(5)  Ş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   eşittir.  numOfUniqueTrees(4) * numOfUniqueTrees(0) -> numOfUniqueTrees(4)    hesaplanıyor. Köşeye bir düğüm atarsak 3 tane kalır. numOfUniqueTrees(4)  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.   = 14. numOfUniqueTrees(4)  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,   = 42 elde ederiz. numOfUniqueTrees(5)  Dağılımların toplamına eşit olan   hesaplamasına dönelim. numOfUniqueTrees(6)  (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,   elde ederiz. numOfUniqueTrees(5) = 132  Görev çözüldü!  Sonuç: N = 6 olan çözümdeki örtüşen alt problemlere dikkat edelim. Basit çözümde   18 kez çağrılacaktır (aşağıdaki ekran). Artan N ile aynı hesaplamanın tekrarları çok daha fazla olacaktır.  numOfUniqueTrees(3)  (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

The code in this story is for educational purposes. The readers are solely responsible for whatever they build with it.

Walkthroughs, tutorials, guides, and tips. This story will teach you how to do something new or how to do something better.

inDrive.Tech

Bu ses hikayenin orijinal dilinde üretilmiştir!

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

About Author

YORUMLAR

ETİKETLERİ ASIN

BU YAZI

Related Stories

HackerNoon Yazma Yarışmasını mı Kazanmak İstiyorsunuz? İşte #crypto-api Yarışması Kazananlarının Önerileri

HackerNoon Kendi Ana Dilinizde 🆕 ‼️ Teknoloji Blog Yazıları için 77 Dil Ana Sayfası

Forumlardan Feed'lere: Sosyal Medya Algoritmaları Dijital Etkileşimi Nasıl Şekillendiriyor

AI/ML Datalake için Referans Mimarisi Oluşturmaya Yönelik Mimar Kılavuzu

HackerNoon Yazma Yarışmasını mı Kazanmak İstiyorsunuz? İşte #crypto-api Yarışması Kazananlarının Önerileri

HackerNoon Kendi Ana Dilinizde 🆕 ‼️ Teknoloji Blog Yazıları için 77 Dil Ana Sayfası

Forumlardan Feed'lere: Sosyal Medya Algoritmaları Dijital Etkileşimi Nasıl Şekillendiriyor

AI/ML Datalake için Referans Mimarisi Oluşturmaya Yönelik Mimar Kılavuzu

Light-Mode

Classic

Newspaper

Minty

Dark-Mode

Neon Noir

Minty

HN StartUps