Algoritmalar: Backtrack

[t-hex]

Merhaba arkadaşlar,
Forumdaki makelelerde yaptığım ufak bir araştırmadan sonra algoritmalarla
ilgili hiç makele bulunmadığını farkettim ve ben de anlatımı bir makeleye sığabilecek belli başlı algoritmalardan söz etmek için bu makeleyi yazmaya karar verdim. İlk algoritma olarakta kodlaması kolay ama kolay olduğu kadarda masraflı çok olan “Aynı yere geri dönme” (Backtrack) algoritmasını seçtim. Makelenin geri kalanında backtrack olarak söz edeceğim.

Backtrack algoritması özyineleme (recursion) desteklenen her dilde kodlanabilir ve basit bir algoritma olmasına rağmen de bir çok ufak iş için kullanılabilir. Bu algoritmanın dezavantajı maximum adım sayısı bilinmeyen durumlarda stackoverflow hatasına neden olabilmesidir.

Algoritmanın pseudo-code’u aşağıdaki gibi :

Kod: Tümünü seç

  procedure backtrack(i:integer;deger: integer);
  basla
    Eger sonuclardan-biriyse
      << sonucla ilgili islemleri yap >>
    degilse
       her adaydeger icin backtrack(i+1,adaydeger);
    bitir;
  bitir;

Tabi ilk bakışta bu pseudo-code’dan her şeyi anlamak kolay değil, o yüzden hemen bir örnek verelim. Bu algoritmayı kullanarak bir kümenin bütün alt kümelerini oluştururalım. Kümemiz 1’den 5’e kadar olan sayılardan oluşsun. Algoritmada bahsi geçen her adım için adaylar true ve false değerlerini alacak. Yani herhangi bir indexdeki eleman o altkümenin içindeyse true değilse false olarak işaretlenecek. Eger adım sayısı kümenin eleman sayısına eşit olduysa tüm kombinasyonlar üretildi demektir, sonucu ekrana yazıyoruz. Eger adım sayısı kümenin eleman sayısından küçükse daha üretilmesi gerek kombinasyonlar var demektir, bizde bir sonraki adım için tüm olası değerleri veriyoruz.

Kod: Tümünü seç

var
  arr : array[1..5] of boolean;
 procedure Recurse(i : integer;val:boolean);
 var j : integer;
 begin
    arr[i]:= val;
    if (i=Length(arr)) then begin
      Write('{ ');
      for j := 0 to Length(Arr) do  if(arr[j]) then Write(j,' ');
      WriteLN(' }');
    end else begin
      recurse(i+1,true);
      recurse(i+1,false);
    end;
 end;
begin
  recurse(1,true);
  recurse(1,false);
  readln;
end.

n elemanlı bir kümenin 2^n tane altkümesi vardır, dolayısıyla örneği çalıştırdığımızda 32 tane sonuç göreceğiz.

İkinci örnek olarak da bir string içindeki karakterlerin bütün permütasyonlarını oluşturalım. Yine aynı mantığı kullanıcaz ama bu sefer biraz daha fazla çalışmamız lazım.

Kod: Tümünü seç

var
  str : string = 'ABC';

 procedure backtrack(str:string;i:integer);
 var
  j: integer;
  ch : char;
 begin
   if i = length(str) then begin
     WriteLn(str);
   end else begin
     for j := i to length(str) do begin
        ch := str[i];
        str[i] := str[j];
        str[j] := ch;
        backtrack(str,i+1);
     end;
   end;
 end;

begin
  backtrack(str,1);
  Readln;
end.

Örnekteki i değeri str değişkeninin uzunluğuna denk olduğunda bunu ekrana yazıyoruz, eğer değilse i ve length(Str) arasındaki karakterleri str değişkeninin i. karakteri ile değiştirip prosedürü tekrar çağırıyoruz.
Üç karakterden oluşan stringin toplam 3! = 6 tane permütasyonu olması lazım, yalnız biz bunu yaparken bütün karakterlerin birbirinden farklı olduğunu farzediyoruz. ‘AAA’ şeklinde tanımlanmış bir değişkende birbirinin aynısı olmasına rağmen 6 tane satır göreceğiz.

Şimdilik aklıma gelen bunlardı, yorum ve önerilerinizi bekliyorum.

İbrahim DURSUN, Mart 2005

[fduman]

Güzel bir recursion örneği. Devamını bekliyorum.

[fduman]

Örneği console application olarak çalıştırdım ancak eksik sonuç veriyor. Geriye sadece 2 değer dönüyor.

Kod: Tümünü seç

if str[i]=str[j] then continue;

bu satırı kaldırınca düzgün bir şekilde çalışıyor. zannedersem debug amacıyla ekledin ve sonra kaldırmayı unuttun.

Kolay gelsin.

[t-hex]

ah evet, o satır olmayacaktı, deneme amaçlı eklemiştim sonra silmeyi unutmuşum. sağol