Kategori Arşivi Veri Yapıları ve Algoritmalar

Fikstür Algoritması

Lisans döneminde algoritma ödevlerimizden bir tanesi girilen takım sayısına göre fikstür oluşturan bir programdı. Aklıma gelince paylaşayım istedim. Fikstür algoritmalarında mantık; n adet takım varsa, lig n-1 adet hafta müsabaka olmalıdır. (Rövanşlar hesaba katılırsa hafta sayısı 2 x (n-1) olacaktır.) İlk haftanın fikstürü çekilir, diğer haftalar ise ilk hafta referans alınarak belirlenir. Bizim kullandığımız algoritmayı örnekle açıklayayım. Örneğin 6 takımlı bir lig oluşturalım. Bu takımları 1,2,3,4,5,6 şeklinde ifade edelim. İlk hafta maçları şu şekilde olsun;

image2

Birinci haftayı oluşturduktan sonra ilk takımı sabit tutarak diğer takımları saat yönünün tersinde ilerletelim. Bu durumda ikinci hafta aşağıdaki şekilde olacaktır;

image3

Bu şekilde devam ettiğimiz taktirde 6 takımlı ligin 5 hafta sürecek müsabakalarının fikstürü aşağıdaki gibi olacaktır.

image

Fikstür bu şekilde belirlendikten sonra ev deplasman ayarları da yapılabilir. Farklı bir durum da tek sayıda takım olması durumudur. Bu durumda ilk hafta oluşturulurken bir takımın karşısına X yazılabilir. Böylelikle fikstür çekimi sonucunda karşısa X gelen takım o haftayı bay geçecektir. Fikstür ayarlaması yukarıdaki gibi yapıldıktan sonra random olarak her takım için bir sayı çekilir. Bu durumda her sayıya karşılık gelen takım belirlenmiş olur.

Johnson Algoritması–En Kısa Yol Problemi (The Shortest Path Problem)

En Kısa Yol Problemi’nden (The Shortest Path Problem) daha önce bahsetmiştim. Bu yazımda bu problemi çözmek için kullanılan algoritmalardan kısaca bahsedip, Johnson Algoritması’nın üzerinde duracağım. En Kısa Yol Problemi için üretilen algoritmaların bazıları şunlardır;

  • Djikstra Algoritması
  • Bellman Ford Algoritması
  • Floyd – Warshall Algoritması
  • Johnson Algoritması
  • A* Search Algoritması
  • Dinitz Algoritması
  • Tarjan Algoritması
  • GOR Algoritması
  • Dial Algoritması

Algoritmalardan bazılarına kısaca göz atacak olursak;

  • Dijkstra Algoritması: Single Source, Single Pair ve Single Destination problemlerini çözmek için kullanılır. Döngüye girme ihtimalinden dolayı negatif ağırlıklı bağlantıları kabul etmez. Basit bir algoritmadır. Buna karşı performansı yüksektir.
  • Bellman Ford Algoritması: Single Source problemlerini kenar ağırlıkları negatif olduğu durumlarda da çözebilmektedir.
  • A* Search Algoritması: İki nokta arasındaki en kısa yolu aramayı hızlandırmak için sezgisel yöntemler kullanarak çözüm arar.
  • Floyd – Warshall Algoritması : All pairs probleminin çözümünde kullanılır.
  • Johnson Algoritması : Floyd Warshall Algoritması’ndaki gibi all pairs problemini çözmeye yarar. Sparse(dağınık) ve yönlü graflar için kullanılan bir algoritmadır. Sparse graflarda Floyd-Warshall’dan daha hızlı çalışır. Daha yoğun grafiklerde daha hızlı çalışabilir.En önemli özelliği negatif kenarlar içeren graflar için çözüm sunar.

Johnson Algoritması (Johnson’s Algorithm)

1977 yılında Donald B. Johnson tarafından geliştirilmiştir. Bellman Ford, Reweighting ve Dijkstra Algoritması tabanlı, All pairs problemini çözmek için kullanılan bir algoritmadır. Sparse(dağınık) ve directed(yönlü) graflar için kullanılan güzel bir çözüm yoludur. Bağlantıların negatif olmasına izin vermektedir ve bu en önemli özelliğidir. Negatif bağlantıları reweighting yöntemiyle işlem sırasında ağırlıkları yeniden hesaplayarak pozitif ağırlıklara güncellemektedir. Bu yönüyle Floyd Warshall’a benzemektedir fakat O(V3) olan çalışma süresi Johnson Algoritması’nın tercih edilmesine neden olur. Ayrıca Floyd Marshall daha sık graflarda tercih edilirken, Johnson seyrek graflarda daha iyidir. Ağırlıkların pozitif olması durumunda Dijkstra’nın kullanılması daha iyi performans sağlar. Algoritmanın adımlarını aşağıdaki graf üzerinde açıklayalım.

1

  • Adım 1: Öncelikle grafa aşağıda görüldüğü üzere yeni bir düğüm ve bu düğümden grafta bulunan tüm düğümlere bağlantılar eklenir. Bu düğümün ve bağlantılarının ağırlığı sıfır olarak belirlenir.

2

  • Adım 2: Her düğüm için BellmanFord Algoritması bir kez çalıştırılır ve düğümlerin ağırlıkları belirlenir. Aşağıda görüldüğü üzere her düğümün ağırlığı içerisine yazıldı.

image

  • Adım 3 : Adım 4’te Dijkstra Algoritması kullanılacaktır. Bilindiği üzere Dijkstra Algoritması negatif bağlantı uzunluklarını kabul etmemektedir. Bu yüzden bu adımda ağırlıklar tekrar hesaplama yöntemiyle yenilecek ve negatif bağlantı kalmayacaktır. Yeniden hesaplama yöntemi şu şekildedir;  ŵ(u, v) = w(u, v) + d(s, u) – d(s, v)

4 x

Ağırlıkların yeniden hesaplanması Reweighting Teorem ile yapılır. Formülde yeni kenar ağırlığı eski kenar ağırlığı ile düğümün, algoritmanın birinci adımında eklenen yeni düğümüne olan ağırlığı ile toplanır. Bu değerden gidilecek olan düğümün S düğümüne olan ağırlığı çıkarılır ve yeni ağırlık bulunur. Reweightin işlemi sonucunda shortest path değişmezken, ağırlıkların hepsi nonnegative olur. Burada akla şu soru gelebilir; ağırlıkları bu şekilde hesaplayacağımıza tüm düğümlere minimum bağlantı uzunluğunu eklesek olmazmı? Olmaz çünkü bu en kısa yolun değişmesine sebep olabilir. Aşağıda ağırlıkların güncellenmiş hali bulunmaktadır. Kenarların yeni ağırlıklarının bulunma işlemine örnek verecek olursak ; eski ağırlığı 8 olan kenarın yeni ağırlığı yukarıda bahsettiğimiz yöntemle 8 + 0 – (-5) = 13 ‘e olarak hesaplanır.

3

Aşağıdaki grafikta tüm düğümlere minimum düğüm ağırlığının eklenmesi durumunda ortaya çıkacak bozulma görülmektedir. Birinci durumda kısa yol alttaki iken, ikinci durumda üstteki oluyor. Bu metod görüldüğü üzere kısa yolun değişmesine sebep oluyor.
5

  • Adım 4 : Birinci adımda eklenen düğüm graftan silinir ve geri kalan tüm düğümler için Dijkstra Algoritması uygulanır. Tüm çiftler arası en kısa yol bulunur. Aşağıda tüm düğümler için ağırlıkların Dijkstra Algoritması’yla yeniden hesaplanması görülmektedir.

8 9 10

ALGORİTMANIN KARMAŞIKLIĞI

Algoritmanın karmaşıklığına bakalım. Algoritmanın adımlarını kontrol edelim.

  • İlk adımda yeni düğüm ekleniyor ve her düğümün ağırlığı Bellman Ford ile hesaplanıyor. Bu durumun getirdiği karmaşıklık O(VE)’dir.
  • Daha sonra negatif kenarlardan kurtarmak için reweighting işlemi yapılıyor. Bu durumun getirdiği karmaşıklık O(E)’dir.
  • Her düğüm için Djikstra Algoritması’nın getirdiği karmaşıklık O(V2 logV + VE logV )’dir.

Bu durumda Johnson Algoritması’nın karmaşıklığı O(V2 logV + VE logV) olarak hesaplanır.

(V: Düğümler Kümesi , E: Bağlantılar Kümesi )

Kaynaklar

Shortest Path Problem – En Kısa Yol Problemi

Shortest Path Problem yani En Kısa Yol Problemi’nden önce bu konuyla ilgili olan Graph Theory’den bahsetmek istiyorum.

Graph Theory

Graf Teori yani Çizge Kuramı, çizgeleri yani grafları inceleyen matematik dalıdır. Graflar node (yada vertice) yani düğümler ve edge yani bağlantılardan oluşan bir çeşit ağ yapısıdır. Bağlantıların her birinin değeri vardır ve tek yada çift yönlü olabilirler. Bir G grafı, G = (V,E) şeklinde ifade edilir. Burada V düğümler kümesi , E ise bağlantılar kümesini ifade eder.

Shortest Path Problem

Shortest Path Problem, Graph Theory içerisinde önemli bir problemdir. Graf içerisinde belirtilen node’lar arasındaki en kısa yolu bulmayı amaçlar. Bu özelliğiyle Gezgin Satıcı Problemi’ne de (Travelling Salesman) benzer. Ancak Gezgin Satıcı’dan iki noktada ayrılır. Birincisi, hedef düğüme giderken tüm düğümlere uğramak zorunda değiliz. İkincisi de hedefe vardıktan sonra başlangıca dönmüyoruz.

En kısa yollar döngüler içeremez, ancak negatif bağlantı değerleri bulundurabilirler. Bununla birlikte n tane düğümün olduğu bir grafta en kısa yol n-1 kenardan daha fazla kenara sahip olamaz.

Kaynak nodun diğer tüm node’lara olan en kısa yollarını bularak Graph Theory içerisinde yer alan En Kısa Yol Ağacı’nı da (Shortest Path Tree) oluşturabiliriz.

Shortest Path Problemleri

· Single-Source (Single – Destination) : Verilen bir node’dan diğer tüm node’lara olan en kısa yolun bulunması problemidir.

  • Single-Pair: Verilen iki node arası en kısa yolun bulunması problemidir.
  • All-Pairs : Grafta bulunan tüm ikililer arası en kısa yolun bulunması problemidir.

En Kısa Yol Problemi’nin Görüldüğü Yerler

En Kısa Yol Problemi’ni çözen çeşitli algoritmalardan daha sonra bahsedeceğiz, ancak daha önce bu problem nerelerde görülür onlardan bahsetmek istiyorum.

  • Navigasyon cihazlarında güzergah ayarlaması sırasında
  • Dynamic Routing kullanan Network’lerde En ucuz yada hızlı hat ayarlaması yaparken
  • Limancılık, havacılık, postacılık güzergah ayarlaması esnasında
  • Hatta Rubik Cube’ü en az hamlede çözmek için dahi kullanılabilir.
  • Robot hareket planlaması

Kaynaklar

Quad Tree (Dörtlü Ağaç)

Quad dörtlü, tree ağaç demektir. QuadTree adı üstünde bir ağaç yapısıdır. Her nodun (node) dört adet çocuğu (child) vardır. İki boyutlu uzayda kullanılmaktadır. Üzerinde çalışılan bölge dörtlü alanlara bölünerek uygulanır.

Örnek verecek olursak; İlgilendiğimiz alan aşağıdaki gibi olsun. Alanı iki boyutlu bir uzay gibi  düşünelim. Bu bölgeye her hangi bir eleman geldiğinde bölge dörde bölünür. Ağacın şekli üçüncü resimdeki gibi olur. Root’un sadece ilk elemanı doludur.

1  3 2

Bölgeye eleman gelmeye devam etsin. İkinci eleman ilk elemandan farklı bir bölgede olduğu için alan bölme işlemine gerek kalmadı. Ağaçta ise root’un ikinci elemanı B nodu oldu.

quadtree1 5

Yeni elemanımız B ile aynı bölgede olsun. Bu durumda B’nin bulunduğu bölge dörde bölünecek ve ağacın yapısı değişecektir.

6 7

Bölgeye birkaç eleman daha ekleyelim ve ağacın durumuna bakalım.

8 9

E elemanı bölgeye eklendiğinde B’nin bulunduğu alan tekrar dörde bölünür. Ağaçta B bir alta geçerek E ile kardeş olur.

10 11

Bölgeye F elemanı eklendiğinde ise durum aşağıdaki ağaçtaki gibi olur.12 13

Sorularınız olursa yardımcı olmaya çalışırım. Konuyla ilgili buradan da bilgiye ulaşabilirsiniz.