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.
