Dijkstra’nın en kısa yol algoritması (DJK) ya da Dijkstra’nın deyişiyle “benim en kısa yol algoritmam” graf üzerinde bir noktadan diğer tüm noktalara en kısa yolu çıkarır ve bunu n noktalı bir grafta en kötü olarak O(n*n) zorlukta tamamlar. Daha önceden bahsettiğim Floyd-Warshall algoritması ise tüm noktalar arasındaki en kısa mesafeyi O(nnn) zorlukta çıkarıyordu. Dikkat ettiyseniz birisi yolu diğeri mesafeyi çıkarıyor. Algoritmanın aşamalarını ayrı ayrı değerlendirdiğimizde anlamamız daha kolay olacaktır. Örnek olarak 10×10′luk bir tahtanın üzerinde olduğumuzu düşünün. İlerlemeye (0,0) noktasından başlayıp, (9,9) noktasına ulaşmaya çalışacağız. Tahta üzerindeki her karede bir sayı olsun ve biz o kare üzerine geldiğimizde orada yazılı olan sayı kadar saniye beklemek zorunda kalalım. Bu durumda hedefimiz olan (9,9) noktasına en kısa zamanda nasıl ulaşırız? Devam…

Floyd-Warshall Algoritması, graf olarak ifade edilebilecek herhangi bir veri yapısında herhangi iki nokta arasındaki en kısa yolu bulmak için kullanılabilecek kodlaması oldukça basit bir algoritmadır. İnternette bu algoritmayı anlatan birçok kaynak bulabilirsiniz. Benim burada anlatacaklarım ise minimum teori ile maksimum pratik sunmak olacak. Pseudo kod yerine örnekler ve kod parçaları üzerinden açıklamaya çalışacağım. Floyd-Warshall algoritmasının özü çok basit bir formülden oluşuyor. A,B,C diye 3 tane noktamız olduğunu varsayalım. Bu durumda A ile C arasındaki en kısa mesafe min(mesafe(A,C), mesafe(A,B) + mesafe(B,C)) kadar olacaktır. Devam…

Recursion doğru kullanıldığı zaman çok işimize yarayabilir. Özellikle ağaç tipi data yapılarının tüm nodelarını dolaşmak istediğimizde recursiondan faydalanabiliriz. Fakat bu ağaç yapısının ne kadar derinliğe sahip olduğunu kestiremediğimiz durumlarda bu yönteme çok da bel bağlamamak lazım zira stack (yığın) taşabilir ve overflow hatasıyla karşılaşabiliriz.

Alternatif bir yöntem ise kendi yığınımızı kullanarak bu işi yapmaktır. Genel adı ile Breadth First Search (Yayılma Öncelikli Arama):

• Bir stack yaratılır ve root node’u bu yığına eklenir. (Queue ile de yapılabilir sadece işleme sıranız değişir)
• Herhangi bir node’un alt node’ları varsa bunlar da yığına eklenir
• Bulunduğumuz node işlenir ve yığından bir sonraki node çekilir.
• Yığın boşalana kadar bu işlem tekrarlanır.

Merhaba,

Recursion yöntemini kullanarak neler yapılabileceğini göstermek amacıyla

   12
-------- + 6
 13 + 1
 ------
   28

gibi ifadeleri (Expression) hesaplayan örnek bir program yazalım dedim.

Program bölme ve toplama işlemlerini tanıyabilecek. Bölme için gerekli çizgiler ‘-‘ karakteri kullanılarak çizilecek.

İfadeler ya bölme ya toplama işlemi olacak o yüzden şöyle bir class hiyerarşisi oluşturuyoruz.

İlk olarak bütün ifadelerin hesaplama yapan bir metodu olmalı ve bu metod Real bir değer döndürmeli. O yüzden TExpression diye abstract bir class tanımlıyoruz ve içine Evaluate metodunu yazıyoruz. Devam…

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.