Dinamik Programlama: Nedir, Nasıl Çalışır ve Öğrenme Kaynakları

Dinamik programlama, bir matematikçi ve ekonomist olan Richard Bellman tarafından geliştirilen bir kavramdır.

O sırada Bellman karmaşık optimizasyon problemlerini çözmenin bir yolunu arıyordu. Optimizasyon problemleri, bir dizi seçenek arasından en iyi çözümü seçmenizi gerektirir.

Optimizasyon problemine bir örnek, Gezgin satıcı problemidir. Amaç, satıcının her şehri tam olarak bir kez ziyaret etmesini ve başlangıç ​​şehrine dönmesini sağlayacak en kısa rotayı bulmaktır.

Bellman'ın bu problemlere yaklaşımı, onları daha küçük alt problemlere bölmek ve alt problemleri en küçüğünden en büyüğüne doğru çözmekti. Daha sonra alt problemlerin sonuçlarını sakladı ve bunları daha büyük alt problemleri çözmek için yeniden kullandı. Dinamik programlamanın arkasındaki ana fikir budur.

Dinamik Programlama nedir?

Dinamik programlama, optimizasyon problemlerini daha küçük alt problemlere bölerek, her bir alt problemi bir kez çözerek ve çözümlerini daha büyük problemi çözmek için yeniden kullanılabilecek ve birleştirilebilecek şekilde saklayarak çözer. Problemler en küçüğünden en büyüğüne doğru çözülerek çözümlerin yeniden kullanılması sağlanır.

Dinamik Programlama Nasıl Çalışır?

Dinamik programlama kullanarak bir problem çözmek aşağıdaki adımları içerir:

1. Alt problemleri tanımlayın : Büyük bir problem küçük alt problemlere bölünür.
2. Alt Problemleri Çözün : Bu, özyineleme veya yineleme kullanılarak yapılabilen tanımlanmış alt problemin çözülmesini içerir.
3. Çözümleri Saklayın : Alt problemlere yönelik çözümler, tekrar kullanılabilecek şekilde saklanır.
4. Orijinal Problemin Çözümünü Oluşturun : Büyük problemin çözümü, halihazırda hesaplanmış olan alt problemlerden inşa edilir.

Bunu uygulamalı olarak görmek için, bu işlemi kullanarak 6. Fibonacci sayısını, F(6) hesaplıyoruz.

İlk olarak, çözülmesi gereken alt problemleri tanımlayın.

n > 1 için F(n) = F(n-1) + F(n-2)

Bu nedenle: F(6) = F(5) + F(4)

F(5) = F(4) + F(3)

F(4) = F(3) + F(2)

F(3) = F(2) + F(1)

F(2) = F(1) + F(0)

F(1) = 1

F(0) = 0

İkinci adım, özyinelemeli bir işlev veya yinelemeli bir süreç kullanarak her bir alt problemi çözmeyi içerir. Daha küçük alt problemlerin sonuçlarını yeniden kullanarak alt problemleri en küçüğünden en büyüğüne çözeriz. Bu bize aşağıdakileri verir:

F(0) = 0

F(1) = 1

F(2) = F(1) + F(0) = 1 + 0 = 1

F(3) = F(2) + F(1) = 1 + 1 = 2

F(4) = F(3) + F(2) = 2 + 1 = 3

F(5) = F(4) + F(3) = 3 + 2 = 5

F(6) = F(5) + F(4) = 5 + 3 = 8

Alt problemlerin her birini çözerken, çözümleri aşağıdaki gibi daha büyük alt problemlerin çözümünde tekrar kullanılabilmeleri için bir dizide veya tabloda saklarız:

Tüm alt problemler çözüldükten sonra, orijinal problemin çözümünü oluşturmak için çözümleri kullanırız.

Bu durumda asıl problemin çözümü, en büyük problemden belirlenen alt problemler olan F(5) ve F(4)'ün sonuçlarının toplanmasıyla bulunan 6. Fibonacci sayısıdır. Sonuç bize 8 verir.

Dinamik Programlama Nerede ve Neden Kullanılır?

Dinamik programlama, daha küçük alt problemlere bölünebilen problemlerimizin olduğu alanlarda kullanılır ve bunların çözümleri daha büyük problemleri çözmek için kullanılır.

Bu alanlar bilgisayar bilimi, ekonomi, matematik ve mühendisliği içerir. Bilgisayar biliminde diziler, grafikler ve tamsayı değerleri içeren problemleri çözmek için ve rekabetçi programlamada kullanılır.

Ekonomide, finans, üretim ve kaynak tahsisindeki optimizasyon problemlerini çözmek için kullanılır. Matematikte dinamik programlama, optimizasyon problemlerini çözmek için kullanıldığı oyun teorisi, istatistik ve olasılıkta kullanılır.

Mühendislikte kaynak tahsisi, çizelgeleme, üretim, iletişim ve kontrol sistemlerindeki sorunları çözmek için kullanılır.

Optimizasyon problemlerini çözmek için dinamik programlama kullanmanın çeşitli avantajları vardır:

1. Verimlilik : Dinamik programlama, benzer problemlerin birden çok kez yeniden hesaplanmasını engellediği için diğer optimizasyon algoritmalarından daha verimli olabilir.
2. Büyük Problemleri Çözme : Dinamik programlama, diğer yöntemlerle çözülmesi mümkün olmayan büyük optimizasyon problemleri için idealdir. Bunun nedeni, problemi daha küçük problemlere bölerek karmaşıklıklarını azaltmasıdır.
3. Optimal Çözümler : Dinamik programlama algoritmaları, alt problemler ve hedefler doğru bir şekilde tanımlanırsa, bir problemin optimal çözümünü bulabilir.
4. Basitlik: Dinamik programlama algoritmalarının uygulanması ve anlaşılması kolaydır, özellikle de problem belirli bir sırada tanımlanabiliyorsa.
5. Genişletilebilirlik: Dinamik programlama algoritmaları, ek alt problemler ekleyerek ve problemin hedeflerini değiştirerek daha karmaşık problemleri çözmek için kolayca genişletilebilir.

Optimizasyon problemlerinin çözümü söz konusu olduğunda dinamik programlama, çözümlerde verimliliği sağlamak için çok kullanışlı bir araçtır.

Dinamik Programlamada Kullanılan Yaklaşımlar

Dinamik programlamada, optimizasyon problemlerini çözmek için iki yaklaşım kullanılır. Bunlar yukarıdan aşağıya yaklaşım ve aşağıdan yukarıya yaklaşımdır.

Yukarıdan Aşağıya Yaklaşım

Bu yaklaşım aynı zamanda memoizasyon olarak da bilinir. Notlandırma, öncelikle işlev çağrılarının sonuçlarını önbellekte depolayarak ve önbelleğe alınan sonuçları yeniden hesaplamak yerine bir sonraki ihtiyaç duyulduğunda geri döndürerek bilgisayar programlarını daha hızlı hale getirmek için kullanılan bir optimizasyon tekniğidir.

Yukarıdan aşağıya yaklaşım, özyineleme ve önbelleğe almayı içerir. Özyineleme, bağımsız değişken olarak sorunun daha basit sürümleriyle kendisini çağıran bir işlevi içerir. Özyineleme, problemi daha küçük alt problemlere bölmek ve alt problemleri çözmek için kullanılır.

Bir alt sorun çözüldüğünde, sonucu önbelleğe alınır ve benzer bir sorun oluştuğunda yeniden kullanılır. Yukarıdan aşağıya yaklaşımın anlaşılması ve uygulanması kolaydır ve bir alt sorunu yalnızca bir kez çözer. Bununla birlikte, bir dezavantajı, özyineleme nedeniyle çok fazla bellek kaplamasıdır. Bu, yığın taşması hatasına yol açabilir.

Aşağıdan Yukarıya Yaklaşım

Tablolama olarak da bilinen aşağıdan yukarıya yaklaşım, özyinelemeyi ortadan kaldırır, onun yerine yinelemeyi koyar, böylece yığın taşma hatalarını önler.

Bu yaklaşımda, büyük bir problem daha küçük alt problemlere bölünür ve alt problemlerin çözümleri daha büyük problemi çözmek için kullanılır.

Daha küçük alt problemler önce büyükten küçüğe doğru çözülür ve sonuçları bir matriste, dizide veya tabloda saklanır, dolayısıyla tablo adı verilir.

Saklanan sonuçlar, alt problemlere bağlı olan daha büyük problemleri çözer. Orijinal problemin sonucu daha sonra önceden hesaplanan değerler kullanılarak en büyük alt problem çözülerek bulunur.

Bu yaklaşım, özyinelemeyi ortadan kaldırarak bellek ve zaman açısından verimli olma avantajına sahiptir.

Dinamik Programlama ile Çözülebilecek Problemlere Örnekler

Dinamik programlama kullanılarak çözülebilecek bazı programlama problemleri aşağıdadır:

1 numara. sırt çantası sorunu

Bir sırt çantası, tipik olarak arkaya bağlanan ve askerler ve yürüyüşçüler tarafından malzeme taşımak için kullanılan, kanvas, naylon veya deriden yapılmış bir çantadır.

Sırt çantası probleminde size bir sırt çantası sunulur ve taşıma kapasitesi göz önüne alındığında, her birinin değeri olan öğeleri seçmeniz istenir. Seçiminiz, toplanan öğelerin maksimum toplam değerini alacak ve öğelerin ağırlığı, sırt çantası kapasitesine eşit veya daha az olacak şekilde olmalıdır.

Sırt çantası problemine bir örnek aşağıda verilmiştir:

Bir yürüyüşe çıktığınızı ve 15 kilo kapasiteli bir sırt çantanız olduğunu hayal edin. Aşağıdaki tabloda gösterildiği gibi, yanınızda getirebileceğiniz öğelerin değerleri ve ağırlıkları ile birlikte bir listeniz var:

Eşyaların toplam değeri maksimize edilecek ve toplam ağırlık sırt çantası kapasitesi olan 15 kilogramdan az veya ona eşit olacak şekilde getirilecek eşyaların bir alt kümesini seçin.

Sırt çantası probleminin gerçek dünyadaki uygulamaları, riski en aza indirmek ve karı en üst düzeye çıkarmak için bir portföye eklenecek menkul kıymetlerin seçilmesini ve hammaddeleri kesmenin en az israflı yollarını bulmayı içerir.

2 numara. Zamanlama Problemi

Çizelgeleme problemi, amacın bir dizi kaynağa en iyi şekilde görev atamak olduğu bir optimizasyon problemidir. Kaynaklar, görevleri tamamlamak için kullanılan makineler, personel veya diğer kaynaklar olabilir.

Bir çizelgeleme problemi örneği aşağıda verilmiştir:

Bir çalışan ekibi tarafından tamamlanması gereken bir dizi görevi planlamaktan sorumlu bir proje yöneticisi olduğunuzu hayal edin. Her görevin bir başlangıç ​​zamanı, bir bitiş zamanı ve onu tamamlamaya yetkili çalışanların bir listesi vardır.

İşte görevleri ve özelliklerini açıklayan bir tablo:

Toplam tamamlanma süresini en aza indirmek için her görevi bir çalışana atayın.

Çizelgeleme problemi, üretim endüstrisinde makineler, malzemeler, aletler ve işçilik gibi kaynakların tahsisini optimize etmeye çalışırken karşılaşılabilir.

Sağlık hizmetlerinde yatak, personel ve tıbbi malzeme kullanımını optimize ederken de karşılaşılabilir. Bu sorunun oluşabileceği diğer sektörler proje yönetimi, tedarik zinciri yönetimi ve eğitimdir.

#3. Gezgin Satıcı Problemi

Bu, dinamik programlama kullanılarak çözülebilen en çok çalışılan optimizasyon problemlerinden biridir.

Gezgin satıcı problemi, şehirlerin bir listesini ve her bir şehir çifti arasındaki mesafeleri sağlar. Her şehri tam olarak bir kez ziyaret eden ve çıkış şehrine geri dönen mümkün olan en kısa rotayı bulmanız isteniyor.

Gezici satıcı problemine bir örnek aşağıda verilmiştir:

Mümkün olan en kısa sürede bir dizi şehri ziyaret etmesi gereken bir satış görevlisi olduğunuzu hayal edin. Aşağıdaki tabloda gösterildiği gibi, ziyaret etmeniz gereken şehirlerin ve her bir şehir çifti arasındaki mesafelerin bir listesine sahipsiniz:

Gezici satıcı problemi, eğlence endüstrisinde turistler için rota planlamaya çalışırken, lojistikte malların nakliyesini planlarken, ulaşımda otobüs güzergahlarını planlarken ve satış endüstrisinde karşılaşılabilir.

Açıkçası, dinamik programlama, kendisi hakkında daha fazla bilgi edinmeye yardımcı olan birçok gerçek dünya uygulamasına sahiptir.

Dinamik programlama bilginizi açıklamak için aşağıdaki kaynakları göz önünde bulundurun.

Kaynaklar

Dinamik Programlama, Richard Bellman

Dinamik Programlama, dinamik programlamayı bulan ve onu ilk aşamalarında geliştiren Richard Bellman'ın yazdığı bir kitaptır.

Ön izleme	Ürün	Değerlendirme	Fiyat
	Dinamik Programlama (Dover Books on Computer Science)	Henüz derecelendirme yok	17,29 dolar	Amazon'da satın al

Kitap, metni anlamak için yalnızca temel matematik ve matematik bilgisi gerektiren, anlaşılması kolay bir şekilde yazılmıştır. Kitapta Bellman, dinamik programlamada anahtar olan çok aşamalı bir karar sürecinin matematiksel teorisini tanıtıyor.

Kitap daha sonra çok aşamalı üretim süreçlerindeki darboğaz problemlerini, varlık ve benzersizlik teoremlerini ve optimal envanter denklemini inceliyor.

Kitapla ilgili en iyi şey, Bellman'ın lojistik, çizelgeleme teorisi, iletişim teorisi, matematiksel ekonomi ve kontrol süreçleri gibi alanlardaki birçok karmaşık problemden örnekler sunması ve dinamik programlamanın problemleri nasıl çözebileceğini göstermesidir.

Kitap Kindle, ciltli ve karton kapaklı versiyonlarda mevcuttur.

Dinamik Programlama Algoritmaları Yüksek Lisans Kursu

Udemy tarafından hazırlanan bu Dinamik Programlama Algoritmaları Yüksek Lisans Kursu, Google'da bir yazılım mühendisi olan Apaar Kamal ve yine Google ile çalışan Prateek Narang tarafından sunulmaktadır.

Kurs, öğrencilerin dinamik programlama gerektiren birçok problem içeren programlama yarışmasında başarılı olmalarına yardımcı olmak için optimize edilmiştir.

Programlama rakiplerinin yanı sıra, kurs, algoritma anlayışlarını geliştirmek isteyen programcılar ve programlama görüşmeleri ve çevrimiçi kodlama turları için hazırlanan kişiler için idealdir.

40 saatten uzun olan kurs, dinamik programlamayı derinlemesine kapsar. Kurs öncelikle özyineleme ve geri izleme gibi kavramlar hakkında bir tazeleme sunar.

Daha sonra, diğer birçok kavramın yanı sıra oyun teorisi, diziler, ağaçlar ve grafikler, matris üste alma, bit maskeleri, kombinatorikler ve alt diziler, bölümleme problemleri ve çok boyutlu dinamik programlamadaki dinamik programlamayı kapsar.

Rekabetçi Programlama Temelleri, Ana Algoritmalar

Udemy, Prateek Narang ve Amal Kamaar tarafından hazırlanan ve rekabetçi programcılar için yararlı ve alakalı bir şekilde dinamik programlama, matematik, sayı teorisi ve gelişmiş veri yapıları ve algoritmaları kapsayan bir Rekabetçi Programlama Temelleri Kursu sunar.

Kurs, rekabetçi programlamada kullanışlı olan daha karmaşık algoritmalara ve tekniklere dalmadan önce veri yapıları ve algoritmalar hakkında bilgi tazeleme sunar.

Kurs, dinamik programlama, matematik, oyun teorisi, kalıp eşleştirme, Bit maskeleme ve programlama yarışmalarında kullanılan ve test edilen sayısız gelişmiş algoritmayı kapsar.

Udemy kursu 10 modüle ve 42 bölüme ayrılmıştır ve her bölümden sonra pek çok pratik soru sunar. Bu çok satan kurs, rekabetçi programlama ile ilgilenen herkesin sahip olması gereken bir kurstur.

Son sözler

Dinamik programlama, herhangi bir programcının gerçek dünya problemlerini çözmeyi geliştirmeyi öğrenmesi için faydalı bir beceridir. Bu nedenle programcılar, bu çok önemli aracı araç kutularına eklemek için önerilen kaynakları gözden geçirmeyi düşünmelidir.

Ardından, veri biliminde kullanılacak programlama dillerine göz atabilirsiniz.