Böl ve İşgal Et (Divide & Conquer)

Başlık sizi şaşırtmasın. Siyasetten falan bahsetmeyeceğim. Bu yazıda bir başka algoritma tasarım tekniği olan böl ve işgal et tekniğinden bahsedeceğim.

Bilgisayar bilimlerinde böl ve işgal et (D&C) önemli bir algoritma tasarım tekniğidir. Bir problemin iki veya daha fazla benzer alt probleme parçalanarak özyinelemeli olarak çözülmesine dayanmaktadır. Daha sonra bu alt problemlerin çözümleri arasından çözüm seçilir. Arama (Mergesort, Quicksort), "Discrete Fourier Transforms" (FFTs) dahil olmak üzere bir çok algoritma bu yöntemi kullanmaktadır.

D&C algoritmaları özyinelemeli yordamlar şeklinde gerçekleştirilmektedir. Dilerseniz sonuçların bir veri tipinde saklandığı özyinelemeli olmayan şekilde de kullanabilirsiniz.

Örnek vererek ne olduğunu anlatmaya çalışayım.

Problemimiz bir dizi içerisindeki en büyük sayıyı bulmak. Bunu aşağıdaki çok kolay algoritma yardımıyla tek geçişte bulabilirsiniz, evet ama anlaşılması için basit bir örnek veriyorum.

private static void normalMAX(double[] dizi) {
double max = dizi[0];
for (int i = 0; i < dizi.length; i++) {
if (dizi[i] > max)
max = dizi[i];
}
System.out.println("MAX:" + max);
}

Aşağıdaki kod parçasında ise bu problemin D&C yöntemi kullanılarak hazırlanmış çözüm algoritmasını görmektesiniz:

private static void dcMAX(double[] dizi) {
System.out.println("MAX:"+max(dizi,0,dizi.length/2));
}

private static double max(double a[], int l, int r) {
if (l == r)
return a[l];
int m = (l + r) / 2;
double u = max(a, l, m);
double v = max(a, m + 1, r);
if (u > v)
return u;
else
return v;
}

Bu şekilde çözdüğünüz zaman mesela 100000 elemanlık bir dizi için 1 milisaniye kazancınız oluyor :)

Bir başka kullanıldığı alan Hanoi kulelerinin çözüm algoritmasıdır. Bunu nasıl yapıyor derseniz problemi alt problemlere bölerek çözerek yapıyor :)

D&C yöntemi zor problemlerin çözülmesinde verimli algoritmalar bulunmasında çok kullanılmaktadır. Problemi alt parçalara ayırarak paralelliği de desteklemektedir.

En önemli dezavantajı özyinelemeden kaynaklanan yavaşlıktır. Tekrar eden altyordam çağrıları yeterince büyük olmayan çağrı yığıtlarında problemler yaratabilmektedir. Bir başka dezavantajı parçalara bölerek çözmenin, işlemlerin karmaşıklaşmasına neden olmasıdır.

Bazı problemler için, çoğu alt problemin sonucu aynı olabilmektedir. Bu durumda çözümlerin tekrar tekrar kullanılması önem kazanmaktadır. Bu yönteme memoization adı verilmektedir. Dinamik programlamanın özyinelemeli türüdür.


Bağlantılar:

http://en.wikipedia.org/wiki/Divide_and_conquer_algorithm
http://www.csc.liv.ac.uk/~ped/teachadmin/algor/d_and_c.html
http://en.wikipedia.org/wiki/Memoization
http://members.comu.edu.tr/kadayif/algoritmaanalizi/algoritmaanalizi.htm