» Dijkstra (dikestra)Algoritması - En Kısa Yol Algoritmalari

Yayinlanma Zamani: 2011-02-10 19:14:00





Dijkstra (dikestra)Algoritması ile En Kısa Yolların Bulunması

 

Dikjstra algoritması, kaynak düğümüyle ağdaki başka bir düğüm arasındaki en kısa yolu belirlemek üzere tasarlanmıştır. Algoritma bir etiketleme prosedürü kullanır. Etiketleme şu şekilde yapılmaktadır:

ui ----- 1.düğümden i.düğüme en kısa uzaklık,

dij (>=0) ----- (i,j) bağlantısının uzunluğu olmak üzere;

j düğümü için etiket:

[uj ,i] = [ui + dij ,i] , dij >=0 şeklindedir.

 

Düğüm etiketleri geçici ve kalıcı olarak işaretlenirler. Geçici etiket, aynı düğüme daha kısa bir yol bulunursa başka bir etiketle değiştirilir. Daha iyi bir yol bulunamayacaksa etiket kalıcı olarak işaretlenir. Algoritma adım adım şu şekilde açıklanabilir:

 

0.adım : 1.düğüm(başlangıç düğümü) kalıcı etiketle [0,-] şeklinde işaretlenir.i = 1 dir.

i.adım :

  • j’nin kalıcı etiketlenmemiş olması koşuluyla, i. düğümden ulaşılabilen her j düğümü için geçici [ui + dij ,i] etiketleri hesaplanır. j düğümü başka bir k düğümü içinde [uj ,k] ile zaten etiketli ise ve ui + dij < uj ise [uj ,k] , [ui + dij ,i] ie değiştirilir.

  • Tüm etiketler kalıcı ise işlem durdurulur. Aksi halde tüm geçici etiketler arasından [ur ,s] nin en kısa mesafeli( = ur ) olanı seçilir(eşitlik varsa herhangi biri seçilebilir.) i=r olarak atanır ve i. adım tekrarlanır.

 

Örnek: Aşağıdaki verilen ağı kullanarak dijkstra algoritması ile kısa yolları bulalım. Kutu içindeki sayılar mesafeleri göstermektedir.

dijkstra

 

0.adım: 1.düğüme [0,-] kalıcı etiketi atanır.

1.adım: 2. ve 3. düğümlere 1.düğümden (en son kalıcı etiketlenen) ulaşılır ve düğümler aşağıdaki gibi etiketlenir.

 

dijkstra

 

3.düğüm en kısa yolu verdiği için bir sonraki tabloda statüsü kalıcı olarak işaretlenecektir.

2. adım: 4. ve 5. düğümlere 3.düğümden ulaşılmaktadır ve yeni etiketleme aşağıdaki gibidir.

 

 

 

3.adım : 2. ve 5. düğümlere 4.düğümden ulaşılabilir. 4. düğümün statüsü değiştirilir.

 

 

 

en kisa yol

 

 

 

 

 

2.düğümün etiketi daha kısa yol bulunduğundan değiştirilir. 5. düğümüm 2 seçeneği vardır.

4.adım: 2. düğümden sadece 3. düğüme gidilebilir. 3.düğümün etiketi kalıcı olduğu için yeniden etiketlenemez.2.düğümdeki etiket de kalıcı olarak işaretlenir. 5. düğümden diğer düğümlere gidiş olmadığı için işlem tamamlanır.

 

 

1.düğüm ile ağdaki başka bir düğüm arasındaki en kısa yolu bulmak için, istenen varış düğümünden başlanır ve kalıcı etiketler kullanılarak geriye doğru gidilir. Örneğin 1.düğümden 2. düğüme giden en kısa yol;

 

(2) ---- [55,4]---- (4)---- [40,3] ----- (3) -----[30,1] ------(1)

 

Aranan yolun uzunluğu 1----3---- 4---- 2 şeklinde olup toplam mesafe 55 km dir.

 

Aynı algoritmayı ağda yer alan düğümleri boyayarak da uygulayabiliriz.

1.adım: a düğümünden başlanıyor, a düğümü [0/-] diğerleri [∞ / - ] olarak etiketlenir.

 

 

2.adım: a düğümü seçilip boyanıyor, bu düğümden çıkan dallar da renklendiriliyor

 

 

3.adım: minimum mesafe seçiliyor,seçilen düğüm boyanıyor

 

 

4.adım : f düğümü seçilip boyanıyor

 

 

5.adım: b düğümü seçilerek devam ediliyor

 

 

6. adım: d düğümü seçiliyor ve en kısa yol bulunarak e düğümü de boyanıyor

 

 

Deterministik Dinamik Programlama ile En Kısa Yolun Bulunması

 

Dinamik programlama, n değişkenli bir problemin optimum çözümünü, problemi n aşamaya ayırarak ve her aşamada tek değişkenli bir alt problemi çözerek belirler. Hesaplamalar yinelenerek yapıldığı için bir alt problemin optimum çözümü bir sonraki problemin girdisini oluşturur. Son alt problem çözüldüğünde optimum çözüme ulaşılır. Algoritmada önemli olan konu problemin nasıl parçalara ayrıştırılacağıdır. Bir örnekle algoritmayı inceleyelim.

 

 

Örnek: Aşağıda verilen ağ ,şehirler ve aralarındaki tüm kullanılabilecek yolları uzaklıkları ile göstermektedir. Birinci şehirden yedinci şehre giden en kısa yolu bulmaya çalışalım.

 

 

Problem 1 ila 7.düğümler arasındaki tüm yolları tek tek hesaplayarak çözülebilir. Ancak çok büyük bir ağda bu imkansızlaşır. Bundan dolayı problemi matematik olarak ifade etmeliyiz. Problemi dinamik programlama ile çözmek için önce parçalara ayırmak gerekir. Yöntemdeki genel düşünce, bir aşamanın(parçanın) son düğümlerine olan en kısa (kümülatif) uzaklıkları hesaplamak, sonra bu değerleri, izleyen aşamada girdi olarak kullanmaktır. Bu problem aşağıda gösterildiği gibi üç aşamaya ayrılabilir.

 

 

1.aşama:

2.düğüme en kısa uzaklık =7 km (1.düğümden)

3. düğüme en kısa uzaklık =8km (1.düğümden)

4. düğüme en kısa uzaklık =5 km (1.düğümden)

2.aşama:

5 ve 6. düğümlere en kısa toplam uzaklıkları belirliyoruz. 5. düğümü ele alırsak üç rota bulunmaktadır. (2,5), (3,5) ve (4,5) bunlardan en kısası şu şekilde belirlenir:

 

 

 

6.düğüm için de benzer şekilde;

 

 

7. düğüme en kısa uzaklık 21 km dir. Optimum yolu veren şehirler şu şekilde belirlenir. 3. aşamanın sonucundan haraket ederek 7.düğüm, 5.düğüme bağlanır. Daha sonra 2.aşamanın sonucuna bakılarak 5.düğüm, 4.düğüme bağlanır. Son olarak 1.aşamanın sonucuna bakılarak 4.düğüm, 1. düğüme bağlanır.

 

Optimum yol 1----- 4----- 5----- 7 yoludur.

 

Dinamik programlamanın yinelenen hesaplamalarını matematik olarak şu şekilde ifade edebiliriz:

 

fi (xi ) ----- i. aşamada xi . düğüme en kısa uzaklık,

d(xi-1 ,xi )----- xi-1 . düğümden xi . düğüme olan uzaklık olarak tanımlanırsa fi aşağıdaki eşitlik yardımıyla fi-1 den hesaplanır:

 

fi (xi) = min ( d(xi-1 ,xi ) + fi-1(xi-1 ))

tüm uygun

(xi-1, xi ) yolları

i=1,2,3

Başlangıçta i=1 ve f0 (x0) = 0 olarak alınır. Dinamik programlama terminolojisinde xi den i. aşamada sistemin durumu olarak söz edilir.i. aşamada sistemin durumu, aşamaları birbirine bağlayan bir bilgidir.Durumun uygun bir biçimde tanımlanması, her aşamayı ayrı ayrı hesaplamayı sağlar ve çözümün tüm aşamalar için uygun olmasını garantiler.

 

İleriye ve geriye doğru yineleme

 

Ele alınan örnekteki hesaplamalar birinci aşamadan başlayıp üçüncü aşamaya geçilerek ileriye doğru bir yineleme ile yapılmıştır. Aynı örnek üçüncü aşamadan başlayıp birinci aşamada bitecek şekilde geriye doğru yineleme ile de çözülebilir. Her iki hesaplama da aynı sonucu verecektir. İleriye doğru hesaplama daha mantıklı görünse de dinamik programlama literatüründe daha çok geriye doğru hesplamanın kullanıldığını görmekteyiz. Bunun nedeni de geriye doğru yinelemenin hesaplama açısından daha etkili olmasıdır. Ele alınan örnek için geriye doğru yineleme denklemi şu şekilde yazılabilir:

 

fi (xi) = min ( d(xi ,xi+1) + fi+1(xi+1 ))

tüm uygun

(xi ,xi+1 ) yolları

i=1,2,3

 

bu örnekte x4 = 7 için f4 (x4) =0 alınır. Hesaplamalara ait sıra f3f2f1 şeklindedir.

Şimdi aşamaları geriden başlayarak adım adım izleyelim.

 

3.aşama:

7. düğüm (x4 = 7), 5. ve 6. düğümlere (x3 = 5 ve 6) sadece bir yolla bağlı olduğundan seçim şu şekilde yapılır:

 

 

Birinci aşamada , birinci şehir dördüncü şehire bağlanıyor. İkinci aşamada optimum çözüm, dördüncü şehrin beşinci sehre bağlandığını gösteriyor. Üçüncü aşamada da beşinci şehir yedinci şehire bağlanıyor. Optimum çözüm (1- 4 – 5 – 7 ) numaralı düğümlerden geçmekte ve uzunluğu da 21 km . olmaktadır.


 

Sonraki Konu

Atama Modelleri - Assignment Method


Duyuru

Facebook sayfamiza üye olun


Duyuru
Sitemizde güncelleme çalismalari devam etmektedir.
Görüs ve önerilerinizi bizimle paylasabilirsiniz ! mail adresimiz : endustrimuhendisligi@hotmail.com