Merhaba arkadaşlar, İlk algoritma olarak 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 :

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.

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.

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.