Veri Yapıları - Böl ve Yönet
Böl ve yönet yaklaşımında, eldeki problem daha küçük alt problemlere bölünür ve ardından her problem bağımsız olarak çözülür. Alt problemleri daha da küçük alt problemlere ayırmaya devam ettiğimizde, sonunda daha fazla bölünmenin mümkün olmadığı bir aşamaya ulaşabiliriz. Bu "atomik" olası en küçük alt problem (fraksiyonlar) çözülür. Özgün bir problemin çözümünü elde etmek için tüm alt problemlerin çözümü nihayet birleştirilir.
Genel olarak anlayabiliriz divide-and-conquer üç aşamalı bir süreçte yaklaşım.
Böl / Böl
Bu adım, problemi daha küçük alt problemlere bölmeyi içerir. Alt problemler, asıl problemin bir parçasını temsil etmelidir. Bu adım genellikle, hiçbir alt problem daha fazla bölünemeyene kadar sorunu bölmek için özyinelemeli bir yaklaşım kullanır. Bu aşamada, alt problemler doğası gereği atomik hale gelir, ancak yine de asıl sorunun bir kısmını temsil eder.
Fethet / Çöz
Bu adım, çözülmesi gereken çok sayıda küçük alt problemi alır. Genel olarak, bu düzeyde sorunlar kendi başlarına 'çözülmüş' olarak kabul edilir.
Birleştir / Birleştir
Daha küçük alt problemler çözüldüğünde, bu aşama onları orijinal problemin bir çözümünü formüle edene kadar tekrar tekrar birleştirir. Bu algoritmik yaklaşım özyinelemeli olarak çalışır ve fethet ve birleştir adımları o kadar yakın çalışır ki tek gibi görünürler.
Örnekler
Aşağıdaki bilgisayar algoritmaları temel alır divide-and-conquer programlama yaklaşımı -
- Sıralamayı Birleştir
- Hızlı sıralama
- Ikili arama
- Strassen'ın Matrix Çarpımı
- En yakın çift (puan)
Herhangi bir bilgisayar problemini çözmenin çeşitli yolları vardır, ancak bahsedilenler böl ve yönet yaklaşımının iyi bir örneğidir.