DINAMIK PROGRAMLAMA: ÖZELLIKLER, ÖRNEK, AVANTAJLAR, DEZAVANTAJLAR - TEKNOLOJI - 2025

Dinamik programlama , karmaşık bir sorunu çözer model algoritması ile bölünmesi olarak , alt problemler Sonuçları depolanması bunun sonucu yeniden hesaplamak zorunda kalmamak için.

Bu program, benzer alt problemlere bölünebilen problemleriniz olduğunda kullanılır, böylece sonuçları yeniden kullanılabilir. Çoğunlukla, bu program optimizasyon için kullanılır.

Dinamik program. Fibonacci dizisinde üst üste bindirilmiş alt problemler. Kaynak: Wikimedia commons, en: Kullanıcı: Dcoatzee, izlenen Kullanıcı: Stannered / Public domain

Mevcut alt problemi çözmeden önce, dinamik algoritma daha önce çözülmüş alt problemlerin sonuçlarını incelemeye çalışacaktır. En iyi çözümü elde etmek için alt problemlerin çözümleri birleştirilir.

Aynı alt problemi tekrar tekrar hesaplamak yerine, çözümünüzü bu alt problemle ilk karşılaştığınızda hafızada saklayabilirsiniz. Başka bir alt problemin çözümü sırasında tekrar göründüğünde, hafızada saklanan çözüm alınacaktır.

Bu, bellek süresini sabitlemek için harika bir fikirdir; burada ek alan kullanmak, bir çözüm bulmak için gereken süreyi iyileştirebilir.

Dinamik programlamanın özellikleri

Aşağıdaki temel özellikler, dinamik programlamanın uygulanabilmesi için sorun yaşamamanız gereken özelliklerdir:

Optimal alt yapı

Bu özellik, bir optimizasyon probleminin, onu oluşturan ikincil problemlerin optimal çözümlerinin birleştirilmesiyle çözülebileceğini ifade eder. Bu optimal alt yapılar özyineleme ile tanımlanır.

Örneğin, bir grafikte, bir tepe s'den bir tepe noktasına t giden en kısa r yolunda optimal bir alt yapı sunulacaktır:

Yani, bu en kısa yolda herhangi bir ara tepe noktası i alınabilir. Eğer r gerçekten en kısa rota ise, o zaman r1 (s'den i'ye) ve r2 (i'den t'ye) alt yollarına bölünebilir, böylece bunlar karşılık gelen köşeler arasındaki en kısa yollar olur.

Bu nedenle, en kısa yolları bulmak için çözüm, Floyd-Warshall algoritmasının yaptığı gibi, özyinelemeli olarak kolayca formüle edilebilir.

Çakışan alt problemler

Alt problem alanı küçük olmalıdır. Yani, bir problemi çözen herhangi bir özyinelemeli algoritma, yeni alt problemler oluşturmak yerine aynı alt problemleri defalarca çözmek zorunda kalacaktır.

Örneğin, Fibonacci serisini oluşturmak için bu yinelemeli formülasyonu düşünebiliriz: Fn = F (n - 1) + F (n - 2), F1 = F2 = 1'i temel alan olarak alırsak: F33 = F32 + F31 ve F32 = F31 + F30.

Gördüğünüz gibi, F31 hem F33 hem de F32'nin özyinelemeli alt ağaçlarına çözümleniyor. Toplam alt problem sayısı gerçekten az olsa da, bunun gibi özyinelemeli bir çözüm kullanırsanız, aynı problemleri defalarca çözersiniz.

Bu, dinamik programlama tarafından dikkate alınır, bu nedenle her bir alt sorunu yalnızca bir kez çözer. Bu, iki şekilde gerçekleştirilebilir:

Yukarıdan aşağıya yaklaşım

Herhangi bir sorunun çözümü, alt problemlerinin çözümü kullanılarak özyinelemeli olarak formüle edilebiliyorsa ve bu alt problemler örtüşüyorsa, alt problemlerin çözümleri kolaylıkla ezberlenebilir veya bir tabloda saklanabilir.

Yeni bir alt problem çözümü her arandığında, daha önce çözülüp çözülmediğini görmek için tablo kontrol edilecektir. Bir çözümün saklanması durumunda tekrar hesaplanmak yerine kullanılacaktır. Aksi takdirde, çözüm tabloda saklanarak alt problem çözülecektir.

Aşağıdan yukarıya yaklaşım

Bir problemin çözümü, alt problemlerine göre özyinelemeli olarak formüle edildikten sonra, problemi artan bir şekilde yeniden formüle etmek için bir girişimde bulunulabilir: önce, alt problemleri çözmeye çalışacağız ve daha büyük alt problemlerin çözümlerine ulaşmak için onların çözümlerini kullanacağız.

Bu aynı zamanda genellikle tablo biçiminde yapılır, daha küçük alt problemlere çözümler kullanarak daha büyük ve daha büyük alt problemlere yinelemeli çözümler üretir. Örneğin, F31 ve F30'un değerleri zaten biliniyorsa, F32'nin değeri doğrudan hesaplanabilir.

Diğer tekniklerle karşılaştırma

Dinamik programlama ile çözülebilecek bir problemin önemli bir özelliği, üst üste binen alt problemlere sahip olmasıdır. Dinamik programlamayı, en basit değerleri depolamanın gerekli olmadığı böl ve yönet tekniğinden ayıran şey budur.

Özyinelemeye benzer, çünkü temel durumlar hesaplanırken nihai değer tümevarımsal olarak belirlenebilir. Bu aşağıdan yukarıya yaklaşım, yeni bir değer yalnızca önceden hesaplanan değerlere bağlı olduğunda işe yarar.

Misal

1'e ulaşmak için minimum adımlar

Herhangi bir pozitif tamsayı "e" için aşağıdaki üç adımdan herhangi biri gerçekleştirilebilir.

- Sayıdan 1 çıkarın. (e = e-1).

- 2'ye bölünebiliyorsa, 2'ye bölünür (e% 2 == 0 ise e = e / 2).

- 3'e bölünebiliyorsa, 3'e bölünür (e% 3 == 0 ise e = e / 3).

Yukarıdaki adımlara dayanarak, e'yi 1'e getirmek için bu adımların minimum sayısı bulunmalıdır. Örneğin:

- e = 1 ise, sonuç: 0.

- e = 4 ise, sonuç: 2 (4/2 = 2/2 = 1).

- e = 7 olduğunda, sonuç: 3 (7-1 = 6/3 = 2/2 = 1).

Odaklanma

Her zaman n'yi olabildiğince düşük yapan adımı seçmek ve 1'e ulaşana kadar böyle devam etmek düşünülebilir. Ancak burada bu stratejinin işe yaramadığı görülebilir.

Örneğin, e = 10 ise adımlar şöyle olacaktır: 10/2 = 5-1 = 4/2 = 2/2 = 1 (4 adım). Bununla birlikte, en uygun form: 10-1 = 9/3 = 3/3 = 1 (3 adım). Bu nedenle, bulunan her n değeri için yapılabilecek tüm olası adımlar, bu olasılıkların minimum sayısı seçilerek denenmelidir.

Her şey özyineleme ile başlar: F (e) = 1 + min {F (e-1), F (e / 2), F (e / 3)} eğer e> 1 ise, temel durum olarak: F (1) = 0. Yineleme denklemine sahip olarak, yinelemeyi kodlamaya başlayabilirsiniz.

Ancak örtüşen alt problemleri olduğu görülebilir. Ayrıca, belirli bir girdi için en uygun çözüm, alt problemlerinin optimal çözümüne bağlıdır.

Ezberlemede olduğu gibi, çözülen alt problemlerin çözümlerinin daha sonra kullanılmak üzere saklandığı yer. Veya dinamik programlamada olduğu gibi, en alttan başlarsınız, verilen e kadar yolunuza devam edersiniz. Sonra her iki kod:

Ezberleme

Dinamik aşağıdan yukarıya programlama

avantaj

Dinamik programlamayı kullanmanın temel avantajlarından biri, önceden hesaplanan referanslar kullanıldığından işlemeyi hızlandırmasıdır. Özyinelemeli bir programlama tekniği olduğu için programdaki kod satırlarını azaltır.

Açgözlü algoritmalar ve dinamik programlama

Açgözlü algoritmalar, her ikisi de optimizasyon için araçlar oldukları için dinamik programlamaya benzer. Bununla birlikte, açgözlü algoritma her yerel adımda en uygun çözümü arar. Yani, küresel bir optimum bulma umuduyla açgözlü bir seçim arar.

Bu nedenle, açgözlü algoritmalar, o anda en uygun görünen ancak gelecekte pahalı hale gelen ve küresel bir optimalliği garanti etmeyen bir varsayımda bulunabilir.

Öte yandan, dinamik programlama alt problemler için en uygun çözümü bulur ve daha sonra en uygun çözümü bulmak için bu alt problemlerin sonuçlarını birleştirerek bilinçli bir seçim yapar.

Dezavantajları

- Her bir alt problemin hesaplanan sonucunu saklamak için, saklanan değerin kullanılıp kullanılmayacağını garanti etmeksizin çok fazla belleğe ihtiyaç vardır.

- Çoğu zaman, çıktı değeri yürütme sırasında aşağıdaki alt problemlerde hiç kullanılmadan saklanır. Bu, gereksiz bellek kullanımına yol açar.

- Dinamik programlamada, işlevler özyinelemeli olarak adlandırılır. Bu, yığın belleğinin sürekli artmasını sağlar.

Özyineleme ve dinamik programlama

Kodunuzu çalıştırmak için sınırlı belleğiniz varsa ve işlem hızı önemli değilse, özyinelemeyi kullanabilirsiniz. Örneğin, bir mobil uygulama geliştiriyorsanız, uygulamayı çalıştırmak için bellek çok sınırlıdır.

Programın daha hızlı çalışmasını ve hafıza kısıtlamasının olmamasını istiyorsanız, dinamik programlamanın kullanılması tercih edilir.

Uygulamalar

Dinamik programlama, aksi takdirde makul bir süre içinde çözülmesi son derece zor görünen problemleri çözmenin etkili bir yöntemidir.

Dinamik programlama paradigmasına dayalı algoritmalar, planlamadan problem çözmeden konuşma tanımaya kadar yapay zeka ile ilgili birçok örnek de dahil olmak üzere bilimin birçok alanında kullanılmaktadır.

Dinamik programlamaya dayalı algoritmalar

Dinamik programlama oldukça etkilidir ve çok çeşitli problemler için çok iyi çalışır. Birçok algoritma, açgözlü algoritma uygulamaları olarak görülebilir, örneğin:

- Fibonacci sayı serisi.

- Hanoi Kuleleri.

- Floyd-Warshall'dan geçen tüm kısa rota çiftleri.

- Sırt çantası sorunu.

- Proje planlaması.

- Dijkstra'da en kısa yol.

- Uçuş kontrolü ve robotik kontrol.

- Matematiksel optimizasyon problemleri.

- Devremülk: CPU kullanımını maksimuma çıkarmak için işi planlayın.

Fibonacci sayı serisi

Fibonacci sayıları şu sırayla bulunan sayılardır: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, vb.

Matematiksel terminolojide, Fibonacci sayılarının Fn dizisi, tekrarlama formülüyle tanımlanır: F (n) = F (n -1) + F (n -2), burada F (0) = 0 ve F ( 1) = 1.

Yukarıdan aşağıya yaklaşım

Bu örnekte, tüm başlangıç ​​değerlerine sahip bir arama dizisi -1 ile başlatılmıştır. Bir alt problemin çözümü gerektiğinde, ilk olarak bu arama matrisi aranacaktır.

Hesaplanan değer oradaysa, o değer döndürülür. Aksi takdirde, sonuç daha sonra tekrar kullanılabilmesi için arama dizisinde saklanacak şekilde hesaplanacaktır.

Aşağıdan yukarıya yaklaşım

Bu durumda, aynı Fibonacci serisi için önce f (0) hesaplanır, sonra f (1), f (2), f (3) vb. Böylece alt problemlerin çözümleri aşağıdan yukarıya doğru inşa ediliyor.

Referanslar

1. Vineet Choudhary (2020). Dinamik Programlamaya Giriş. Developer Insider. Alındığı kaynak: developerinsider.co.
2. Alex Allain (2020). C ++ 'da Dinamik Programlama. C Programlama. Alınan: cprogramming.com.
3. Akademi'den Sonra (2020). Dinamik Programlama Fikri. Alındığı: afteracademy.com.
4. Aniruddha Chaudhari (2019). Dinamik Programlama ve Özyineleme - Fark, Örneklerle Avantajlar. CSE Yığını. Alınan: csestack.org.
5. Kod Şefi (2020). Dinamik Programlama Eğitimi. Codechef.com'dan alınmıştır.
6. Programlama (2020). Dinamik program. Alındığı: programiz.com.