Dinamik programlama, herhangi bir süredir sahadaysanız muhtemelen şimdiye kadar ortaya çıkmış bir terimdir. Konu, tasarım gözden geçirme toplantılarında ve mühendislerin günlük etkileşimlerinde sıklıkla gündeme gelir ve aynı zamanda teknik görüşmelerde de odak noktasıdır. Böl ve fethet stratejisi, herhangi bir hedefe ulaşmak için kusursuz bir yöntemdir. Bilgisayar programcılığında da aynı fikir doğrudur. Çok sayıda zorluğun, izole edilebilen ve ayrı ayrı ele alınabilen alt türleri vardır, bu da birincil sorunun nihai çözümüne olanak tanır. Bu yazımızda dinamik programlama algoritmasını ve Python'u ele alacağız.
Dinamik Programlama Nedir?
Dinamik programlama, karmaşık sorunları önce daha basit sorunlara indirgeyerek, ardından bu basit sorunların çözümlerini orijinal sorunu çözmek için yapı taşları olarak kullanarak çözme yöntemidir.
Eldeki sorunu yönetilebilir parçalara böleriz. Çoğu durumda, ebeveynin sorunu ile çocuğunun sorunları arasındaki tek gerçek ayrım, bunların göreli boyutlarıdır. Böylece, bu mini problemler daha da fazla mini problemlere bölünebilir ve bu sonsuza kadar böyle devam eder. Bir konu ve çeşitli alt problemlerinin bir ağaç oluşturduğunu hayal edin. Önce "yaprak" problemleri ele alınır, ardından "ebeveyn" problemleri gelir ve bu şekilde problem ağacında devam edilir. Daha küçük zorluklarla mücadele ederken, ilerlememizi daha sonra kullanmak üzere kaydederiz. Bu, gelecekte sorunun o kısmını atlamamıza izin verir.
Bu yöntem, bir problemi bağımsız olarak çözülebilecek daha küçük problemlere ayırması ve daha sonra nihai çözümü elde etmek için birleştirmesi bakımından böl ve fethet tekniğine benzer.
Dinamik Programlama Nasıl Çalışır?
Dinamik programlama etkilidir, çünkü zor konuları bileşen parçalarına ayırarak basitleştirir. Bir sonraki adım, birbirini takip eden bu zorluklara en iyi cevapları belirlemektir. Bu prosedürlerin sonuçları ezberlenebilir, böylece ilgili çözümler depodan alınabilir ve daha fazla hesaplama yapılmadan kullanılabilir. Ayrıca, önceden çözülmüş alt problemlerin yeniden hesaplanmasını önlemek için çözüm kaydedilebilir.
Dinamik programlamayı gerçekleştirmek için iki yöntem vardır:
1 numara. Yukarıdan Aşağıya Yaklaşım
Bilgisayar biliminde, problemler genellikle özyinelemeli çözümler oluşturarak veya eldeki problemin üstesinden gelmek için önceki adımların sonuçlarını kullanarak çözülür. Eğer benzerlerse, alt problemlerin çözümlerini ezberlemek veya bir tablo tutmak mümkündür. Yukarıdan aşağıya yöntemi ezbere dayalı öğrenmeye dayanır. Notlandırma, yineleme gerçekleştirme ve iki kez önbelleğe alma ile aynıdır. Özyineleme, işleve dolaylı bir çağrı yapmayı içerirken önbelleğe alma, ara sonuçların izlenmesini içerir.
Yukarıdan aşağıya yaklaşımın birçok avantajı arasında şunlar yer alır:
- Yukarıdan aşağıya yöntemi kavramak ve uygulamak basittir. Ne yapılması gerektiğini daha iyi anlamak için, bu yöntem sorunları bileşenlerine ayırır. Her yeni gelişme, daha önce aşılmaz bir engeli ortadan kaldırır. Parçalardan bazıları başka sorunlara bile uygulanabilir.
- Alt problemlerin isteğe bağlı olarak çözülmesini sağlar. Yukarıdan aşağıya yöntemi, sorunların daha sonra kullanılmak üzere saklanan çözümlerle yönetilebilir parçalara ayrıştırılmasına izin verecektir. Ardından, müşteriler her bir bileşeni onarmak için yardım isteyebilir.
- Hata ayıklama da basitleştirilmiştir. Bir problemi daha küçük parçalara bölmek, cevabı takip etmeyi ve olası hataları görmeyi kolaylaştırır.
Yukarıdan aşağıya bir yaklaşım kullanmanın dezavantajlarından bazıları şunlardır:
- Yukarıdan aşağıya strateji, çağrı yığınında diğer yaklaşımlardan daha fazla bellek kaplayan özyineleme yöntemini kullanır. Bu sonuçta performansın düşmesine neden olur. Ek olarak, özyineleme çok geçmişe giderse bir yığın taşması meydana gelebilir.
2 numara. Aşağıdan Yukarıya Yaklaşım
Bir sorunun çözümü, alt problemler açısından kendi kendine geri dönecek şekilde ifade edildikten sonra, kullanıcılar, önce daha küçük alt problemleri çözdükleri ve sonra çözümlerini daha büyük olanlara uyguladıkları aşağıdan yukarıya yaklaşımını kullanarak sorunu yeniden yazabilirler. .
Yukarıdan aşağıya yöntemin aksine, aşağıdan yukarıya yöntemi kullanıldığında özyineleme ortadan kaldırılır. Bu nedenle, özyinelemeli işlevler gereksiz ek yük eklemez veya yığının taşmasına neden olmaz. Ayrıca, veri sıkıştırma sağlar. Özyinelemenin zamansal karmaşıklığı, aynı değerleri yeniden hesaplama ihtiyacını ortadan kaldırarak azaltılır.
Sıfırdan çalışmanın bazı faydaları şunlardır:
- İlk olarak, daha küçük, yeniden kullanılabilir alt problemlerden büyük bir problemin nasıl inşa edileceğini belirler.
- Özyinelemeyi ortadan kaldırarak, mevcut belleğin daha iyi kullanılmasına yardımcı olur. Zamanlama karmaşıklığı bir yan etki olarak azalır.
Dinamik Programlamanın Özellikleri
Dinamik programlamanın iki ayırt edici özelliği vardır:
1 numara. Alt problemler örtüşüyor
Daha yönetilebilir olan birincil problemin modifikasyonlarına "alt problemler" denir. Her sayının kendisinden önceki iki sayının (0, 1, 1, 2, 3, 5, 8,…) toplamına eşit olduğu Fibonacci dizisi. Fibonacci dizisindeki n'inci değeri bulma görevini daha yönetilebilir parçalara bölebilirsiniz. Aynı alt problemi tekrar tekrar ele alarak çözümler buldukça, bu üst üste binen zorlukların çözülmesi giderek zorlaşıyor.
Dinamik programlama, üst üste binen alt problemlerin evrensel oluşumu nedeniyle büyük programlama işlerini yönetilebilir parçalara bölmek için kullanılabilir.
2 numara. Altyapı Optimal Özelliğe Sahiptir
Optimum alt yapı özelliği, çözümlerden tüm alt problemlere en uygun çözümün oluşturulması mümkün olduğunda kendini gösterir. Özyinelemenin çalışması için, her çakışmadan elde ettiğiniz yanıtı tüm probleme uygulamanız gerekir. Optimum alt yapı özelliği, Fibonacci dizisinde olduğu gibi, her bir alt problemin değerini belirlemek için dizideki bir sonraki alt probleme uygulanabilecek bir çözümü olduğunda tüm problem tarafından görüntülenir.
Dinamik Programlamanın Gerçek Dünyada Kullanımı
İşte dinamik programlamanın kullanım alanları.
1 numara. sırt çantası sorunu
Sırt çantası problemini çözmek için dinamik programlama yaygın olarak kullanılmaktadır. Karşılaştığımız sorunlar bunlar:
Her alt konu için söz konusu öğe sayısı ve sırt çantasında kalan alan miktarı ile belirlenen ideal değer, iki boyutlu bir dizide saklanarak bu sorunun hızlı bir şekilde çözülmesi sağlanır. Mevcut öğeyi her aşamada dahil ederek veya hariç tutarak değeri maksimize edebiliriz. Cevap, dizinin sağ alt köşesinde bulunabilir.
Sırt çantası problemi, bagaj paketlemeden yatırım kararları almaya ve kaynak tahsis etmeye kadar çok çeşitli bağlamlarda kullanılabilir.
2 numara. Tüm Çiftler En Kısa Yol
Ağırlıklı bir grafikteki en kısa yol sorunu, dinamik programlamanın başka bir tipik kullanımıdır. Floyd-Warshall veya Bellman-Ford gibi teknikleri kullanarak, verilen herhangi iki düğüm çifti arasındaki en kısa yolu bulabiliriz.
Herhangi iki düğüm arasındaki en kısa yolu takip etmek için bu algoritmalar üç boyutlu bir dizi kullanır. Ayrıca başlangıç noktasından ne kadar uzakta olduklarını takip edebilmek için her aşamada sonucu başlangıç noktası ile ara düğüm arasındaki mesafe ile karşılaştırırlar. Sonuçta iterasyonlar tamamlandı, nihai çözüm uzaklık matrisi olacaktır.
Ağ analizi, yönlendirme, navigasyon, sosyal ağ analizi vb. gibi tüm çiftler en kısa yol sorununu çözmek için çeşitli kullanımlar vardır.
#3. Dikiş Oyması
Görüntü işleme alanında, dikiş oyma, dinamik programlamanın ilgi çekici bir uygulamasıdır. Eldeki görev, temel özelliklerinden herhangi birini değiştirmeden bir görüntünün boyutunu azaltmaktır. Bir görüntüdeki dikişler olarak bilinen düşük enerjili rotalar, bu efekti elde etmek için pikselleri çıkarmak veya eklemek için kullanılabilir.
Dinamik programlamayı kullanarak, görüntüdeki her pikselin gradyanına ve komşularına dayalı kümülatif enerjisini hesaplayabilir ve ardından bu bilgiyi hangi dikişlerin çıkarılması veya eklenmesi gerektiğini belirlemek için kullanabiliriz. Ardından, resmin alt kısmından yukarıya doğru ilerleyerek, en az potansiyel enerjiye sahip dikiş yerini bulabiliriz. Bu yöntem, gerekli boyut elde edilene kadar tekrar kullanılabilir.
Ek olarak, dikiş oymacılığının yardımıyla görüntüler yeniden boyutlandırılabilir, kırpılabilir, yeniden hedeflenebilir ve daha fazlası yapılabilir.
#4. Makine Öğrenimi ve Genomik
Dizi hizalaması, gizli Markov modelleri ve filogenetik ağaçlar gibi makine öğrenimi ve genomik zorlukların tümü, dinamik programlamanın problem çözme yeteneklerine uygundur.
Ortak noktaları ortaya çıkarmak için çoklu sembol dizilerini (genellikle DNA veya proteinler) hizalamaya dizi hizalaması denir. Bu, onların evrimsel bağlantılarına, toplumdaki işlevlerine veya yapısal özelliklerine ışık tutabilir. Diziler arasındaki eşleşmelere ve uyumsuzluklara puanlar atayarak dinamik programlama yoluyla optimum hizalamalar bulunabilir.
Gizli Markov modelleri olarak bilinen olasılıksal modeller, bilinmeyen durumlara bağlı olan zaman serisi verilerini tanımlamak için kullanılır. Konuşma tanıma, NLP, biyoinformatik vb. zor fenomenleri modellemek için kullanışlıdırlar. Bir dizi gözlem verildiğinde, Viterbi ve İleri-Geri gibi dinamik programlama teknikleri gizli durumların en olası sırasını belirleyebilir.
Filogenetik ağaçlar, zaman içinde türler veya genler arasındaki bağlantıları gösterir. Bu ortaklıklardan ortak atalar, ayrışma tarihleri ve evrimsel olaylar çıkarmak mümkündür. Ayrıca, sıralama verilerini kullanarak optimal filogenetik ağaçları oluşturmak için Fitch ve Sankoff gibi bir dinamik programlama algoritması kullanılabilir.
#5. kriptografi
Gizli iletişim çalışması olan kriptografi, dinamik programlamanın problem çözme yeteneklerinden de yararlanır. Şifreleme, şifre çözme, dijital imzalar, kimlik doğrulama ve diğer benzer süreçlerin tümü kriptografinin bir parçasıdır.
Şifreleme, bilgileri insanlar tarafından okunabilirden gizli anahtar tarafından okunabilir hale getirir. Şifre çözme, orijinal anahtarı veya yenisini kullanarak şifrelenmiş verileri tekrar düz metne dönüştürme işlemidir. Dijital imzalar, bir mesajın veya belgenin doğruluğunun ve bütünlüğünün doğrulanmasına izin verir. Gönderenin veya alıcının kimlik bilgilerinin kontrol edilmesi, gönderenin veya alıcının kimliğini doğrulayabilir.
Dinamik anahtar kriptografisi, kod tabanlı kriptografi ve dinamik programlama tabanlı kriptografi dahil olmak üzere farklı kriptografi türlerinin tümü dinamik programlama ile uygulanabilir.
Dinamik anahtar kriptografisi, sürekli değişen anahtarlarla mesajları şifrelemek ve şifrelerini çözmek için kullanılan bir mekanizmadır. "Dinamik" anahtarlar, zaman içinde veya diğer faktörlere yanıt olarak gelişen anahtarlardır. Bu, onları saldırılara karşı savunmasız olan statik anahtarlardan daha güvenli hale getirir. Dinamik anahtar kriptografisini uygularken anahtarları oluşturmak ve güncel tutmak için dinamik programlamayı kullanmak mümkündür.
Kod tabanlı kriptografi olarak bilinen bir teknik kullanarak, bunu yaparken hata düzeltme kodları kullanarak mesajları şifrelemek ve şifrelerini çözmek mümkündür. Hata düzeltme kodları ile iletim hatalarını düzeltmek mümkündür. Kod tabanlı kriptografinin kullanımı, kuantum bilgisayarlardan gelen saldırılara karşı güvenli olduğundan, yaygın olarak kuantuma dayanıklı olarak kabul edilir. Dinamik programlama, kod tabanlı bir şifreleme sistemi kullanarak iletişimleri şifrelemek ve deşifre etmek için kullanılabilir.
Verileri şifrelemek ve şifresini çözmek için bir yöntem olarak dinamik programlama tabanlı kriptografi, dinamik bir programlama algoritmasına dayanır. Optimizasyon zorluklarının üstesinden gelmek için, dinamik programlama teknikleri tipik olarak problemi bir dizi daha basit alt probleme böler. Dinamik programlama kriptografisi sırt çantası, en kısa yol ve dikiş oymacılığı kullanır.
Dinamik Programlamanın Gerçek Dünya Örneği Nedir?
Çok sayıda gerçek dünya yazılım uygulaması örneği, ana bilgisayar sistemindeki kaynak ayak izlerini azaltırken çevikliği ve verimliliği korumak için dinamik programlamayı kullanır. Bazı örnekler aşağıdaki gibidir:
- Google Haritalar. Google Haritalar, belirli bir başlangıç noktasından birkaç farklı varış noktasına en hızlı rotayı bulmak için dinamik programlamayı kullanır.
- Ağ oluşturma. Tek bir göndericiden birden çok alıcıya sıralı veri aktarımı.
- Yazım denetleyicileri. Düzenleme mesafesi algoritması, bir kelimeyi diğerine dönüştürmek için gereken adım sayısını belirler ve iki kelime arasındaki benzemezlik derecesinin niceliksel bir ölçüsünü sağlar.
- İntihal yazılımı. Belge mesafesi yöntemleri, metin belgesi benzerliğini belirlemeye yardımcı olur.
- Arama motorları. İki internet içeriğinin gerçekte ne kadar benzer olduğunu belirlemek.
Dinamik Programlama Problemleri Nasıl Çözülür?
Dinamik programlama problemlerini çözme formülünü öğrenmek, dinamik programlama kavramını anladıktan sonraki adımdır. Eldeki soruna dinamik programlamanın nasıl uygulanacağına ve uygulanabilir bir çözüme nasıl ulaşılacağına ilişkin birkaç öneri:
1 numara. Dinamik Programlama Sorununu Kabul Edin
En önemli kısım, dinamik bir programlama algoritmasının belirtilen problem bildirimini çözebileceğini fark etmektir. Bu problemi çözmek, öncelikle problem ifadelerinin her birinin bir fonksiyon olarak daha küçük parçalara bölünüp bölünemeyeceğini belirlemeyi gerektirir.
2 numara. Sorunun Nedenlerini Belirleyin
Dinamik programlamanın iş için doğru araç olduğu sonucuna vardıysanız, bir sonraki adım, onu oluşturan alt problemler arasında problemin özyinelemeli yapısını belirlemektir. Bu durumda, sorunun koşullarının değişken doğasını hesaba katmalısınız. Bu değişken bir dizi konumu veya problem çözme hızı olabilir.
Ek olarak, sorunun bileşenlerini saymak çok önemlidir.
#3. Yinelemeli ve Özyinelemeli Yöntem Arasında Seçim Yapın
Dinamik programlama problemlerini çözmek için yinelemeli veya özyinelemeli yaklaşımlardan yararlanabilirsiniz. Şimdiye kadar söylenenlerden, özyinelemeli yöntemin tercih edildiğini söylemek güvenlidir. Bununla birlikte, yukarıda belirtilen tüm hususlar, sorunu çözmek için seçilen yöntemden bağımsız olarak kendi başlarına durur.
Hem özyinelemeli hem de yinelemeli yaklaşımlar, yineleme ilişkisini ve sorunun temel durumunu belirlemenizi gerektirir.
#4. Bir Ezberleme Sistemi Dahil Edin
Benzer yapıya sahip bir konuyu ele alırken, karşılaştırılabilir alt problemlerle ilgili geçmiş deneyimleri hatırlamak faydalı olabilir. Bunun sonucunda problemin zaman karmaşıklığı azalacaktır. Aynı alt problemleri ezberlemeden tekrar tekrar çözmeye devam edersek, bir görevin zaman karmaşıklığı katlanarak artabilir.
# 5. Tekrarlama İlişkisini Sözcüklere Aktarın
Bir problemi çözerken, birçok programcı yineleme ilişkisini tanımlamayı atlar ve doğrudan kodlamaya atlar. Başlamadan önce yineleme ilişkisini açıkça ifade edebilirseniz, sorunu daha iyi kavrayacak ve daha hızlı kodlayabileceksiniz.
Algoritma Dinamik Programlama
Dinamik programlamanın çoğu uygulaması özyinelemeli algoritmayı içerir. Optimizasyon için dinamik programlamanın kullanılması, özyinelemenin optimizasyon sorunlarının çoğuna içkin olduğunu ima eder.
Ancak dinamik programlama ile tamamen özyinelemeli problemleri çözmek mümkün değildir. Bir özyineleme, Fibonacci dizisi probleminde olduğu gibi, örtüşen alt problemlerin varlığı olmadıkça, çözümü yalnızca bir böl ve fethet stratejisiyle bulabilir.
Bunun nedeni, Birleştirerek Sıralama gibi özyinelemeli bir algoritmadaki temel alt problemlerin üst üste gelmemesi ve Dinamik Programlama kullanımını ortadan kaldırmasıdır.
Farklı Türlerde Dinamik Programlama Algoritmaları
İşte dinamik programlama algoritmalarının farklı türleri.
1 numara. En Uzun Ortak Alt Dizi
En uzun ortak alt dizinin (LCS) öğelerinin orijinal diziler içinde herhangi bir sırada görünmesi mümkündür; LCS, belirtilen tüm diziler için ortak olan en uzun alt dizi olarak tanımlanır.
İki dizi S1 ve S2 sağlanırsa, o zaman hem S1 hem de S2'nin bir alt dizisi olan bir Z dizisine bunların ortak alt dizisi denir. Ek bir gereklilik olarak, Z, S1 ve S2 kümelerinin endekslerinin kesinlikle artan bir dizisinden oluşmalıdır.
Seçilen elemanların Z'deki endeksleri, yükselen bir dizi oluşturmak için kesinlikle artmalıdır.
2 numara. Floyd-Warshall Algoritması
Ağırlıklı bir grafikteki her köşe çifti arasındaki en kısa yolu bulmak, Floyd-Warshall Algoritmasının amacıdır. Bu yöntem, grafikleri her iki yönde de ağırlıklarla işler. Öte yandan, kenarlarının toplamı negatif olan çevrimler için başarısız olur.
Floyd'un algoritması, Roy-Floyd algoritması, Roy-Warhshall algoritması ve WFI algoritmasının tümü, Floyd-Warhshall algoritmasının adlarıdır.
Bu algoritma, optimum kısayolları bulmak için dinamik bir programlama tekniği kullanır.
Dinamik Programlama Algoritması Lcs Problemlerini Özyinelemeli Tekniğe Göre Nasıl Daha Hızlı Çözer?
Dinamik programlama, işlev çağırma yükünü azaltır. Her işlev çağrısının sonucunu hatırlar, böylece sonraki çağrılar aynı işi tekrarlamadan saklanan verileri kullanabilir.
X'in bir öğesi Y'nin bir öğesiyle her karşılaştırıldığında, sonuçlar yukarıda belirtilen dinamik süreçte sonraki hesaplamalarda kullanılabilmesi için bir tabloya yazılır.
Bu nedenle, dinamik bir yöntemin çalışma zamanı, tabloyu doldurmak için gereken süre ile aynıdır (O(mn)). Buna karşılık, özyinelemeli algoritmanın karmaşıklığı 2max(m, n)'dir. ayrıca oku İş İhtiyaçlarınız İçin Doğru Şifreleme Algoritması Türünü Nasıl Seçersiniz?
Python'da Dinamik Programlama Problemleri Nelerdir?
Dinamik programlama kullanılarak, herhangi bir sayıdaki farklı problem ifadelerine en uygun çözüm belirlenebilir. Aşağıda, en sık talep edilen ünlü problem ifadelerinden bazılarını gözden geçireceğiz ve uygun Python koduyla birlikte kısa bir açıklama sağlayacağız.
1 numara. Sırt Çantası (0-1) Bağlı
Bu durumda, size N malın fiyatları ve ağırlıkları verilir ve bunları W kapasiteli bir sırt çantasına sığdırmakla görevlendirilir; amaç, her şeyi sırt çantasına sığdırırken seçilen öğe sayısını en aza indirmektir.
Mal organizasyonları için çoğu teknik mülakat, adayların dinamik programlama tekniğinin klasik bir örneği olan sırt çantası problemini çözmelerini gerektirecektir.
Problemin Tanımı W kapasiteli bir çantanız ve her birinin bir ağırlığı ve buna karşılık gelen karı olan bir listeniz olduğunu varsayalım. Amaç, etkili kötü doldurma ile kazancı en üst düzeye çıkarmaktır.
Cevap, 1 ile W arasındaki akla gelebilecek her ağırlık için sütunlar ve gerçekten seçtiğiniz ağırlıklar için satırlar içeren bir tablo yapmaktır. Bu tablo dp[][] olarak bilinecek. Sırt çantasının kapasitesi 'j' ise ve ağırlık/ürün dizisindeki ilk 'i' öğeleri dahil edilmişse, tablodaki /hücre dp[i][j] durumu mümkün olan en yüksek karı gösterir.
Sonuç olarak, son hücredeki değer çözümü ifade edecektir. Yalnızca sırt çantasının ağırlık sınırlamasını aşmayacak şeyleri paketlemek önemlidir. “ağırlık>ağırlık[i-1]” kriterinin tüm sütunların doldurulabileceği iki alternatifi vardır.
2 numara. 0/1 Sırt Çantasına Bağlı Notlandırma
Bir çantayı ağırlığı ve kârı bilinen, K boyutundaki öğelerle doldurun. Amacınız kazancınızı en üst düzeye çıkarmaktır. Burada, sorunu çözüp çözemeyeceğimizi görmek için tablolama yerine notlandırmayı kullanacağız.
Yukarıdaki 0/1 sırt çantası problemi, bir çözüm bulmak için aşağıdan yukarıya bir strateji kullanırken, bu problem bir çözüm elde etmek için ezberlemeye dayalı yukarıdan aşağıya bir yaklaşım kullanır.
Dinamik programlama, sorunun aynı kısımlarını birkaç kez çözme ihtiyacını azaltmak için ezberlemeyi kullanır. Bu, sürekli olarak alt sorunu çözme ihtiyacını ortadan kaldırır ve çıktı üretme sürecini kolaylaştırır.
Problemin Tanımı W kapasiteli bir çantanız ve her birinin bir ağırlığı ve buna karşılık gelen karı olan bir listeniz olduğunu varsayalım. Çanta mümkün olduğu kadar verimli bir şekilde doldurulursa, potansiyel olarak en yüksek kar düzeyi elde edilebilir.
Çözüm, önce bireysel alt problemlere verilen nihai cevapları tutmak için iki boyutlu bir dizi oluşturmaktır. Tablonun sütunları, 1 ile W arasındaki tüm potansiyel ağırlıkları listeleyecek, onu o kadar çok bölüme ayıracak ve satırlar, her verilen zamanda seçtiğiniz ağırlıkları gösterecektir.
Çözülen her alt problemi takip etmek için bir dp dizisi kullanıyoruz. Önceden çözülmüş bir alt problemi çözmek yerine, sadece onun cevabını döndürürüz.
#3. Eşit Alt Küme Problemi
Eşit alt küme sorununu çözmek için dinamik programlamayı kullanarak her iki alt kümedeki öğelerin toplamı aynı olacak şekilde verilen kümenin bir bölümünü bulun. Diğer adlarına ek olarak, eşit altküme sorunu (veya bölümleme sorunu), dinamik programlamanın gücünün en iyi örneğidir.
Eldeki görev, arr dizisini ikiye bölmemizi gerektiriyor, böylece sonraki alt kümelerin her biri aynı genel boyuta sahip oluyor.
Çözüm olarak boyutları (toplam/2+1)*(hedef+1) olan iki boyutlu bir dizi oluşturmamız gerekiyor. Burada, orijinal diziyi bölmenin sonuçları her alt küme ve her toplam için saklanabilir ve daha sonra alınabilir. Dizinin birinci boyutu, oluşturulabilecek çeşitli alt kümeleri temsil ederken, dizinin ikinci boyutu, alt kümelerin birleştirilmesiyle hesaplanabilecek çeşitli toplamları temsil edecektir.
Dinamik Programlamanın Avantajları
İşte dinamik programlamanın avantajlarından bazıları.
1 numara. Etkili Çözüm
Dinamik programlama, optimal alt yapıya ve örtüşen alt problemlere sahip sorunlara optimal çözümler bulmak için güçlü bir araçtır. Bunları yönetilebilir parçalara ayırarak, yöntemle bu zorlukların üstesinden gelmek daha kolaydır. Dinamik Programlama, tekrarlayan hesaplamalardan kaçınarak ve cevapları alt problemlere yeniden kullanarak en uygun çözümü oluşturabilir.
2 numara. Kolay Problem Bulmayı Kolaylaştırır
Zor bir problemi çözmek, önce onu daha basit parçalara ayırarak daha kolay olabilir. Karmaşık sorunları daha yönetilebilir parçalara ayırarak çözmeyi kolaylaştırır. Bu yöntem çözümü basitleştirir ve sorunu daha erişilebilir hale getirir.
#3. Verimli
Dinamik Programlama, gereksiz hesaplamaları ortadan kaldırarak ve önceden çözülmüş alt sorunları geri dönüştürerek, bir sorunu çözmek için gereken süreyi önemli ölçüde azaltabilir. Alt problemler örtüştüğünde, yöntem sorunu çözmek için gereken toplam önlem sayısını azaltarak yardımcı olabilir.
#4. Bir Sorunun Birden Çok Çözümü Olduğunda Etkilidir
Dinamik Programlama, çeşitli olası açıklamalardan hangisinin daha muhtemel olduğunu belirlemeye yardımcı olabilir. Bir sorunu çözmek için birkaç geçerli seçenek olduğunda, bu yöntem en iyisine odaklanmamıza yardımcı olabilir.
Dinamik Programlamanın Dezavantajları Nelerdir?
İşte dinamik programlamanın dezavantajlarından bazıları.
1 numara. Sürekli Tekrarlayan Alt Sorunlar
Dinamik programlama en iyi şekilde problemin birbiriyle örtüşen alt problemleri olduğunda işe yarar ki bu her zaman böyle olmayabilir. İşe yaramayacak ve bireysel problemler kesişmiyorsa muhtemelen size en iyi çözümü sağlamayacaktır.
2 numara. Zaman ve Mekanda Karmaşıklık
Sorun büyükse, Dinamik Programlama çok fazla bellek ve depolama alanı gerektirebilir, bu da çözümün zaman ve alan karmaşıklığını artırır. Hafızayı kullanan yaklaşım, ara sonuçları bir tabloda veya not tablosunda saklar.
#3. Sorunun Çerçevesi
Belirli problem yapıları için etkili olmasına rağmen, Dinamik Programlama her zaman en iyi seçim değildir. Bu yöntem, problemin birbiriyle örtüşen alt problemleri olduğunda en iyi sonucu verir, bu nedenle diğer durumlara uygulanamayabilir.
#4. Pratiğe dökmek zor
Dinamik programlama, algoritmalar ve veri yapıları hakkında derinlemesine bilgi gerektirir, bu da yeni başlayanlar için uygulamayı zorlaştırır. Yöntem, önceden düşünmeyi ve eldeki konuya derinlemesine aşina olmayı gerektirir.
Bottom Line
Sonuç olarak, diğer yaklaşımlar tercih edilse de, Dinamik Programlama cevapları bulmak için etkili bir yöntemdir. Artıları ve eksileri bilmek ve eldeki konuya göre doğru yöntemi seçmek çok önemlidir. Optimum alt yapıya ve örtüşen alt problemlere sahip problemler için, Dinamik Programlama optimal bir çözüm sağlayabilir; ancak bu yöntem her zaman geçerli olmayabilir.
Geliştirmesi zor olmasına ve çok fazla bellek kullanmasına rağmen, problem çözme sürecini düzene koyma ve hesaplama sürelerini kısaltma yeteneği onu bilgisayar bilimciler ve matematikçiler için önemli bir kaynak haline getiriyor.
Dinamik Programlama SSS
Doğrusal Programlama ile Dinamik Programlama Arasındaki Fark Nedir?
Doğrusal optimizasyon problemleri için doğrusal programlama (LP) algoritmasına sahibiz ve dışbükey olmayan kısıtlamalara sahip genel doğrusal olmayan optimizasyon sorunları için bir çözümün genel optimalliğini garanti eden dinamik programlamaya (DP) sahibiz.
Dinamik Programlamayı Öğrenmek Ne Kadar Zor?
Dinamik programlamanın, özellikle bilgisayar bilimi alanına yeni başlayanlar için karmaşık bir konu olduğu yaygın bir bilgidir. Bununla birlikte, temel ilkelerin sağlam bir şekilde kavranması ve geniş uygulama ile dinamik programlama kolaylıkla öğrenilebilir.
Dinamik Programlama Çok Zor mu?
Zorlar! Başlamak için, dinamik programlama yöntemleri fikrini kavramak zor olabilir. Herhangi bir uzman programcı, DP'de ustalaşmanın önemli bir zaman taahhüdü gerektirdiğini onaylayacaktır. Bir problemi bileşenlerine ayırma ve onu uygulanabilir bir bütün halinde yeniden bir araya getirme becerisi de gereklidir.
Benzer makaleler
- PROJE ZAMAN YÖNETİMİ: Etkili Yönetim için Süreçler, Araçlar ve Yazılım
- AMAZON SEO: Ürünlerinizi Daha İyi Sıralamak İçin Nasıl Optimize Edebilirsiniz?
- EN POPÜLER PROGRAMLAMA DİLLERİ: 2023 Rehberi
- BİLGİSAYAR PROGRAMLAMA NEDİR: Örnekler, Türler, Kurslar ve Yazılım
- Çevrimiçi İrade: En İyi Çevrimiçi İrade Üreticileri.
Referans
