Dinamik Programlamaya Giriş: Örtüşen Alt Problemler ve Optimal Altyapı

Yayınlanan: 2021-02-08

İçindekiler

Tanıtım

Diyelim ki 25'in karesini çözecek bir sorumuz var. Bu soruyla ilk defa karşılaşıyorsak elde veya hesap makinesi ile çözebiliriz. Ama bu soruyu daha önce gördüysek veya daha önce çözdüysek, ezberleyerek hızlı bir şekilde cevaplama ihtimalimiz var.

Bu bizi, eğer hatırlayabilirsek bir dahaki sefere atlayabileceğimiz sonucuna götürür. Dinamik programlama benzer bir konsept üzerinde çalışır, fikir bir hesaplamanın sonucunu hatırlamak ve gerekirse gelecekte kullanmaktır.

Bu basit dinamik programlama prosedürü, bir programcının verimli kod savaşını fethetmesi için onu güçlü bir silah haline getirir.

Örneğin, karmaşık bir sorumuz olduğunu varsayalım ve her zaman soruyu alt problemlere bölen bir çözüm düşünelim. Ancak bir alt problemi birden çok kez hesaplayacağımız bir durumda takılıp kalabiliriz. Burada optimal bir çözüm için dinamik programlama kullanıyoruz.

Dinamik programlamanın iki kavramı vardır:

Çakışan alt problemler
Optimum altyapı

Örtüşen Alt Problemler

Örtüşen alt problem kavramını anlamanın klasik bir örneği, Fibonacci serisini yazdıran bir programdır.

Fibonacci dizisinin mantığı “fibonacci(n) = fibonacci(n-1) + fibonacci(n-2)” şeklinde verilmektedir. Ve bu işlevi sorunsuz bir şekilde yürütmek, temel bir fibonacci(0)=0 ve fibonacci(1)=1 durumuyla özyinelemeli bir çözüm kullanılarak yapılabilir.

genel statik int fibonacci(int n){
if (n== 0 || n== 1 )
dönüş n;
dönüş fibonacci(n -1 )+fibonacci(n -2 );
}
public static void main(String[] args){
System.out.print( “4. fibonacci sayısı “ +fibonacci( 4 ));
}

4. fibonacci basamağını yazdırmamız gerektiğini söyleyin, ardından özyineleme ağacı şu şekilde gider:

fibonacci(4)

/ \

fibonacci(3) + fibonacci(2)

/ \ / \

fibonacci(2) + fibonacci(1) fibonacci(1) + fibonacci(0)

/ \

fibonacci(1) + fibonacci(0)

Fibonacci(0)'dan başladığımız için fibonacci(4)'nin fibonacci serisindeki 5. basamak olduğuna dikkat edin. Yukarıdaki özyineleme ağacında fibonacci(2)'nin iki kez tekrarlandığını görebiliriz. 4 yüksekliğinde bir özyineleme ağacında yineleme gözlemledik, şimdi çok sayıda özyinelemeli bir çağrımız olduğunu ve ardından büyük bir yüksekliğe sahip bir özyineleme ağacı olacağını hayal edin. Ve örtüşen alt problemler olarak bilinen bu tür birçok yinelenen hesaplama olacaktır.

Bununla başa çıkmak için iki yöntemimiz var (i)tablolama, (ii)memoization

Uygulamalarından geçerek onları anlayalım.

not alma

Fibonacci problemini memoization yöntemini kullanarak çözmek, aşağıda gösterildiği gibi yapılabilir.

statik int[] not;
genel statik int fibonacci(int n){
if(not[n]!=-1)
dönüş notu[n];
if(n==0 || n==1){
not[n]=n;
dönüş n;
}
not[n] = fibonacci(n-1)+fibonacci(n-2);
dönüş notu[n];
}
public static void main(String[] args){
not=yeni int[5];
for(int i=0;i<=4;i++)
not[i]=-1;
System.out.println(“4. fibonacci sayısı “+fibonacci(4));
}

Yukarıdaki kodda, bir bakım günlüğü dosyası oluşturuyoruz veya bir arama tablosunu koruyoruz ve hesaplanan sonuçların değerlerini saklıyoruz. Hesaplanan tüm değerleri ezberlediğimiz için, gerektiğinde bunları gelecekte kullanabiliriz, böylece mükerrer hesaplamalardan ve çakışan alt problemlerden kaçınırız.

Tüm mantık özyinelemeli çözüme benzer, ancak yaptığımız tek fark, değeri ana yönteme döndürmeden önce bunları not dizisinde not etmemizdir. Bu algoritmanın tek kısıtlaması, O(n) boyutunda fazladan bir alana ihtiyacımız olmasıdır, ancak önceki özyinelemeli çözümü optimize ediyoruz.

tablolama

Bu yöntem, yukarıdaki çözümden biraz farklıdır. Notlandırma aynı özyinelemeli çözümü izler. Ancak tablolamada yinelemeli bir çözüm izliyoruz. Aşağıdan yukarıya yaklaşım olarak da adlandırılır. Aşağıdan yukarıya yaklaşımın uygulanmasına bakalım.

genel statik int fibonacci(int n){
int tablo[]=yeni int[n+ 1 ];
for (int i= 0 ;i<=n;i++){
if (i== 0 || i== 1 )
tablo[i]=i;
başka {
tablo[i]=tablo[i -1 ]+tablo[i -2 ];
}
}
dönüş tablosu[n];
}
public static void main(String[] args){
System.out.println( “4. fibonacci sayısı “ +fibonacci( 4 ));
}

fibonacci(n)=fibonacci(n-1)+fibonacci(n-2) olduğunu bildiğimize göre, notlandırmada fibonacci(4) fonksiyon çağrısı ile başladık ve sonra değerini hesaplamadığımızı fark ettik, bu yüzden biz değerlerini hesapladım ve sonra sakladım.

Benzer bir durum, fibonacci(3), fibonacci(2) gibi daha fazla özyinelemeli çağrılarla karşı karşıya kalacaktır. Şimdi bu, özyineleme yığınında çok sayıda özyinelemeli çağrının beklemesine neden olur, ancak yine de örtüşen alt problemlerin tekrarını atlıyoruz.

Ayrıca 0'dan n'inci öğeye kadar fibonacci'yi yinelemeli olarak hesaplamanın ve ardından n'inci fibonacci öğesini döndürmenin bir yolu var. Yukarıdaki kodda uyguladığımız şey budur. Bu kod da aynı alan gereksinimine sahiptir O(n).

Ödeme: Tam yığın geliştirici olma becerileri

Optimum Altyapı

Bu kavramda, bir probleme ancak ilgili alt problemlerini optimal olarak çözdüğümüzde optimal bir çözüm elde edebiliriz.

Ve bu kavramın klasik bir örneği, bir grafikteki düğümler arasında bir geçişi düşünmektir.

Telangana'dan Delhi'ye birden fazla kökümüz olduğunu varsayalım. Ve Nagpur ve Gwalior'dan geçen en kısa rotamız varsa. O halde Nagpur'dan Delhi Delhi'ye en kısa yol Gwalior'dan geçmelidir. Şimdi problemimizi Telangana'dan Nagpur'a, Nagpur'dan Gwalior'a, Gwalior'dan Delhi'ye alt problemlere ayırabiliriz.

Ve bu özellik için klasik bir örnek, her iki dizideki en uzun ortak dizidir. Bir alt dizi, bir alt diziden farklıdır. Bir sonraki dizide, karakterlerin orijinal dizide birbirini takip etmesi gerekmez.

Yani fikir, alt problemlerini en uygun şekilde çözerek çözmektir. En uzun ortak dizinin uzunluğu n olsun.

n=LCS(patates, dövme), o zaman n=LCS(patates,tatto)+1 (son karakterler aynıysa), aksi takdirde n=maksimum(LCS(patates,tatto), LCS(patates, dövme).

statik int lcs(Dize s1, Dize s2, int m, int n ){
int dp[][] = yeni int[m+ 1 ][n+ 1 ];
for (int i= 0 ; i<=m; i++){
for (int j= 0 ; j<=n; j++){
if (i == 0 || j == 0 )
dp[i][j] = 0 ;
else if (s1.charAt(i -1 ) == s2.charAt(j -1 ))
dp[i][j] = dp[i -1 ][j -1 ]+ 1 ;
Başka
dp[i][j] = Math.max(dp[i -1 ][j], dp[i][j -1 ]);
}
}
dp[m][n] döndür ;
}
public static void main(String[] args){
System.out.println( “en uzun ortak dizinin uzunluğu “ +lcs( “patates” , “dövme” , 6 , 6 ));
}

Yukarıdaki kodda, tablolama yöntemini kullanarak mantığımızı uyguladık ve her iki dizide de bulunan en uzun ortak alt dizinin uzunluğunu hesapladık.

Ayrıca Okuyun: Hindistan'da Tam Yığın Geliştirici Maaşı

Dünyanın En İyi Üniversitelerinden Online Yazılım Geliştirme Kursları öğrenin . Kariyerinizi hızlandırmak için Yönetici PG Programları, Gelişmiş Sertifika Programları veya Yüksek Lisans Programları kazanın.

Çözüm

Artık verimli kod savaşını yenmek için güçlü tekniklerden birini kullanmanın farkında olduğunuza göre, diğer problemler için dinamik programlamayı uygulamayı deneyin ve dinamik programlama kullanarak bir soruyu kodlama yeteneğinizi güçlendirmeye başlayın.

Sonuç olarak, Full Stack Developers Courses, web geliştirme ile ilgili her şeyi halledebilen çok yetenekli uzmanlardır. Bu Tam Yığın Geliştirici becerileri, onları Ön Uç ve Arka Uç Geliştiricilerinden ayıran şeydir.

Dinamik programlama nedir?

Bir bilgisayar programı çok sayıda tekrar eden kod içerir. Bu verimsizdir ve performansını etkileyebilir. Bu durumda dinamik programlama kullanılır. Dinamik programlama, karmaşık bir problemi daha basit alt problemlere bölerek, bu alt problemlerin her birini sadece bir kez çözerek ve daha sonra benzer bir alt problem ortaya çıktığında bakılan tablolar kullanarak çözümlerini depolamak için bir yöntemdir. karmaşık sorunun çözümü. Dinamik programlama algoritmaları, yöneylem araştırması, istatistiksel tahmin, örüntü tanıma, yapay zeka, makine öğrenimi, hesaplamalı biyoloji ve diğer alanlarda çeşitli optimizasyon problemlerini çözmek için kullanılır.

Dinamik programlamada örtüşen alt problem nedir?

Örtüşen alt problem, alt problemlerin diğer alt problemlerde de kullanılan çözümleri olduğunda kullanılan bir kavramdır. Bu örtüşme, aynı alt görevin birden fazla kez çözülmesine neden olur. Sorun, alt görevi yalnızca bir kez çözmenin bir yolunu bulmak ve bu çözümü diğer alt sorunların çözümlerini elde etmek için kullanmaktır. Dinamik programlama algoritmaları bu sorunu memoization kullanarak çözer. Notlandırma, tekrar çözmek zorunda kalmamak için alt problemlerin çözümlerini sakladığımız bir tekniktir.

Dinamik programlamada optimal altyapı nedir?

Optimal altyapı, bir problemin optimal çözümünün, aynı problem tanımı içinde daha küçük bir problemin optimal çözümü ile ilgili olduğunu ifade eder. Optimum altyapı, sorunları çözmek veya çözüm olmadığını kanıtlamak için ihtiyaç duyulan ek bir gereksinimdir. Optimal altyapı ile birçok problemi NP-zor olarak ispatlayabiliriz. DP problemlerini çözmek için genel bir yaklaşım, alt problemlerin optimal çözümünü depolamak için dinamik programlama matrisini kullanmaktır. Dinamik programlama matrisi, sıfır olmayan herhangi bir optimal altyapı DP problemini çözmek için kullanılabilir.