Untitled

Özel Algoritmalar 2 Dijkstra Algoritması 2

Bu yazımda işe basit kısmından başlayıp, “en kısa yol (shortest-path)” algoritmasından bahsetmek istiyorum.

Bu algoritma ne için ortaya çıkmıştır?

Diyelim ki yolculuk yapıyoruz, bir yerden yola çıkıp başka bir yere ulaşmak istiyoruz. Bunun için birden fazla seçeneğimiz olabilir. Örneğin arabayla İstanbul’dan yola çıkıp İzmir’e gitmek istiyoruz. Batı kesiminde sahil yolunu izleyip Balıkesir üzerinden de gidebiliriz, daha içeride kalıp Manisa üzerinden de. Normal olarak düşündüğünüzde içerideki yolu izleyerek gitmemiz gerektiğini hemen söyleyebilirsiniz. Hatta elinizde doğrudan her iki rotanın da mesafe bilgisi varsa, yol şartlarının eşit olduğunuz kabul edersek, doğrudan tek seferde içeriden gidilmesi gerektiğini kolayca söyleyebilirsiniz.

Peki elimizde böyle bir veri yoksa ve ulaşmamız gereken son noktaya kadar yol üzerinde uğrayabileceğimiz noktalar ve bunların arasındaki mesafeler biliniyorsa nasıl bir çözüm izleyebiliriz? Bu noktada ağ modeli denilen kavram karşımıza çıkıyor. Ağ modeli belli noktaları ve bunların arasındaki bağlantıları içeren bir veri modelidir. Noktaları istasyon, durak, havaalanı gibi varılacak ve yola çıkılacak yerler olarak kabul edebilirsiniz. Noktalar arasındaki bağlantılar da otobanları, demiryollarını ya da uçuşları ifade edebilir.  Ağ modelinin görsel örneğini aşağıda görebilirsiniz.

 

gt

Şemada görüldüğü gibi A, B, C gibi noktalar varılacak/yola çıkılacak noktaları, aralarındaki bağlantı çizgileri de iki nokta arasındaki ulaşım süresini gösterir. Benzerlik kurmak gerekirse, şemadaki noktaları, şehirler, havaalanları, istasyonlar, aralarındaki bağlantıları da ulaşım süresi ya da  taşıma maliyeti gibi düşünebilirsiniz.

Örneğe göre A noktasından doğrudan J noktasına ya da E noktasına erişim yoktur. Bu durumda en kısa yoldan iki nokta arasındaki ulaşım nasıl hesaplanabilir? Bunun için en kısa yol algoritması çözüm olmaktadır. A ve E arasındaki ulaşımı örnek alacak olursak, A->B->E, A->C->E, A->D->E gibi üç alternatif vardır. Burada bir özelliği de belirtmekte yarar var. Bu tür ağ modellerinde bağlantıların yönlü ya da yönsüz olması durumu da problemin tanımında verilmelidir. Örnek şemada bağlantı okları yönlü olarak verilmiştir, bu durumda bahsettiğimiz üç alternatif rota sözkonusudur. Yön önemli olmasaydı, alternatiflerin sayısı da ciddi şekilde artardı, örneğin A->D->G->H->E rotası da kullanılabilirdi. Şimdilik bağlantıların yönlü olduğunu kabul edelim. Buna göre bahsettiğimiz üç rotanın hangisinin daha kısa olduğunu nasıl hesaplarız?

En kısa yol algoritması başlangıç olarak kabul edilen noktadan, ulaşılması istenen noktaya gelinceye kadar sıradaki komşu noktalara olan mesafeleri hesaplar, sonra en kısa mesafedeki komşudan devam ederek aynı hesaplamaları onun için yapar. Bu işlem hedef noktaya varılıncaya kadar devam eder. Burada önemli olan, her nokta için birikimli (kümülatif) mesafenin hesaplanmasıdır, hedef noktaya ilk seferde ulaşılması her zaman doğru sonucu vermeyebilir. Bunu daha basit bir örnek ile açıklayayım. Basit bir ağ modeli düşünün, üç noktası olsun, A, B ve C. A noktasından B’ye, oradan da C’ye varabiliyoruz. Ayrıca A noktasından doğrudan C noktasına da varılabilsin. Bu durumda A’dan C’ye ulaşmak için en kısa yol, A->C arasıdır diyebilir miyiz? A->B arası 5 saat, B->C arası 3 saat, A->C arası 10 saat ise yanıtımız hatalı olur.

En kısa yol algoritmasında A’dan başlanır, A’nın komşuları olan B ve C’ye ulaşım mesafeleri hesaplanır. B (5), C (10) olur, A noktası işlenenler grubuna dahil edilir. C’ye ulaşıldığı için çözüm durdurulmaz, B’den devam edilir. B’nin komşusu C’dir, A da B’nin komşusudur (bağlantılarda yön olmasa) ancak A daha önce işlendiği için hesaba katılmaz. C’nin birikimli mesafesi tekrar hesaplanır, bu durumda C’nin yeni birikimli mesafesi, B’nin birikimli mesafesine (5), B->C arasındaki mesafe (3) eklenerek bulunur ve sonuçta 8 elde edilir. 8 değeri, C’nin o andaki birikimli mesafesinden (10) daha küçük olduğu için C’nin birikimli mesafesi 8 olarak değiştirilir. B noktası da işlenenler grubuna dahil edilir. İşlenmeyen noktalar arasında bir tek C noktası kaldığı için ve hedef nokta olduğu için çözüm sonlanır. Burada bir noktanın komşu noktalarının tek tek değerlendirilip, her biri için mesafe hesaplanmasını ve aynı işlemin sıradaki komşu noktadan devam ettirilmesini BFS (Breadth-First-Search) (Sığ Öncelikli Arama) algoritması olarak isimlendiriyoruz. Sıradaki komşu noktalardan ilkini alıp hemen onunla devam eden ve onun da ilk komşu noktasını alıp ilerleyen algoritama da DFS (Depth First Search – Derin Öncelikli Arama) olarak isimlendirilir. DFS yöntemi, ağ üzerinde bir noktadan başka bir noktaya mesafeleri dikkate almaksınız ulaşmada BFS algoritmasına göre çok daha hızlı sonuç verir. +En kısa yol probleminde ise komşu noktaların her biri, hedef noktaya ulaşmada birer alternatif olduğu için ve hangisinin en kısa yol üzerinde olduğu bilinmediği için BFS yöntemini tercih etmek daha doğru olur. Aslında hangisinin tercih edilmesi gerektiği daha çok ağ yapısına bağlıdır. Ağ içindeki noktalar genelde sıralı olarak bağlılar ise (buna seyrek ağ (sparse graph) denir), DFS kullanmak daha hızlı sonuç üretir. Ağ daha yoğun (dense graph) ise (noktaların komşu sayısı fazla ise) BFS daha hızlı sonuç üretebilir. Bunu ağ içindeki bağlantı ve nokta sayılarına bağlı olarak karar verebilirsiniz.

En kısa yol algoritmasını oluşturan kişi Edsger W. Dijkstra’dır. Algoritma 1956 yılında yayımlanmıştır ve genellikle Dijkstra algoritması olarak bilinir. Algoritmanın zayıf yönü bağlantılar üzerinde tanımlı olan mesafe, taşıma maliyeti gibi ifade edilen değerlerin negatif değerleri için çalışmamasıdır, bu değerlerin sıfır ya da sıfırdan büyük olması gereklidir.

Üç noktalı bir ağ modelinde çözümün iki adımda (iterasyonda) bulunması kolaydır, ancak noktalar ve aralarındaki bağlantı sayıları arttıkça problem kağıt kalemle çözümlenemeyecek kadar karmaşık hale gelir. Bunun için bilgisayar yardımıyla çözülebilen yazılım modeli kurmak gerekir. Öncelikle yazılım oluşturacak veri modeli nasıl olmalıdır? Noktalar ve aralarındaki bağlantılar nasıl ifade edilecektir?

Ağın içinde noktalar kümesi ve bağlantılar kümesi olmak zorundadır. Bağlantıları nasıl tarif edebiliriz? Her bir noktanın komşularının bilinmesi gereklidir. Bu sebeple nokta bazında bir komşu listesi tanımlamak gerekecektir. Noktaların komşu listesi, ilgili noktaya komşu olan diğer noktaları içereceğinden, bağlantı listesi de kendiliğinden tanımlanmış olur, sonuçta bir bağlantı, başlangıç ve bitiş noktası ile birlikte ifade edilir. Her bağlantı için mesafe bilgisinin saklanması gerekecektir. Her nokta için de, o noktanın birikimli mesafesi ve ek kısa yolda kendisine gelen önceki komşu noktanın numarası saklanmalıdır.

Buna göre Nokta, Komsu, Ag isimli yapılar tanımlanmıştır. Ağ yapısı, nokta listesini içerir, nokta ekleme çıkarma, bağlantı ekleme çıkarma gibi metotları eklenmiştir.

Bir sonraki yazımda bu algoritmayı kodladığım programı sizlerle paylaşacağım.

Pdf İndir

21 Tolga Togan Düz

Facebook Sayfamizdan Bizleri Takip Edebilirsiniz