Yazan : Şadi Evren ŞEKER
Bilgisayar bilimlerinde kullanılan ve algoritmayı literatüre kazandıran kişinin ismini taşıyan dijkstra algoritması, verilen bir şekilde (graph) en kısa yolu (shortest path) bulmak için kullanılır.
Bu algoritmanın çalışmasını örnek bir şekil( graph ) üzerinden göstermeye çalışalım. Bu gösterimin ardından Dijkstra algoritmasının başarısını ve zafiyetlerini tartışabiliriz.
[flashvideo file=http://www.bilgisayarkavramlari.com/wp-content/uploads/dijkstra.flv /]
Örnek olarak yukarıda bulunan şekli ele alalım. Dijkstra algoritması herhangi bir şekildeki bir düğümden diğer bütün düğümlere giden en kısa yolu hesaplar.
Örneğimizde başlangıç düğümü (node) olarak A düğümünü seçtiğimizi düşünelim ve algoritmanın çalışmasını bu düğümden başlayarak gösterelim.
Algoritma başlangıçta bütün düğümlere henüz erişim olmadığını kabul ederek sonsuz (¥ ) değeri atar. Yani başlangıç durumunda henüz hiçbir düğüme gidemiyoruz.
Ardından başlangıç düğümünün komşusu olan bütün düğümleri dolaşarak bu düğümlere ulaşım mesafesini günceller.
Bu güncelleme işleminden sonra güncellenen düğümlerin komşularını günceller ve bütün düğümler güncellenene ve şekil üzerinde yeni bir güncelleme olmayana kadar bu işlem devam eder.
Örneğin yukarıda A düğümünün komşusu olan düğümler (B ve C) güncellendiler. Bir sonraki adımda bu düğümlerin komşuları güncellenecektir. İstediğimiz bir düğüm ile başlayalım. Örneğin önce B sonra C düğümünün komşularını güncelleyelim:
Yukarıdaki şekilde, B düğümünün komşusu olan E ve F düğümleri güncellenmiştir. Bu güncelleme işlemi sırasında B düğümünün üzerindeki mevcut maliyet ile E ve F düğümlerine gidişten doğan maliyet toplanmıştır.
Örneğin E düğümü için 2 + 5 = 7 ve F düğümü için 2 + 2 = 4 değerleri bulunmuştur.
Şimdi bir sonraki düğüm olan C düğümünden güncelleme yapalım:
Bu aşamada güncellenen düğümler, C düğümünün komşusu olan D ve F düğümleridir. Bu düğümlerden, F düğümü daha önce güncellenmişti ve değer olarak 7 taşımaktaydı, ancak yeni gelen değer, F için C üzerinden 1 + 2 = 3 olarak hesaplanmış ve bu değer daha önceden hesaplanan 7 değerinden düşük olduğu için 7’nin üzerine yazılarak 3 olmuştur.
Algoritmanın çalışmasını sonraki düğümlerin güncellenmesi ile sürdürelim. Bu sefer örneğin D düğümünün komşularını güncelleyelim ( şu anda D, F ve E düğümleri aynı derecede yeni güncellenmiştir bunlardan herhangi birisi ile başlanması Dijkstra algoritmasına uygundur. Ancak recursive (özyineli) bir kodlama yapılıyorsa koda göre elbette yakın olan komşular güncellenecektir)
D düğümünün hiçbir komşusu güncellenmemiştir bunun sebebi hesaplanan değerlerin mevcut değerlerden yüksek olması ve dolayısıyla daha iyi bir sonuç bulunamamasıdır.
F için 2 + 5 = 7 > 3
E için 2 + 7 = 9 > 4
Dolayısıyla bir sonraki düğümü seçerek devam ediyoruz
F düğümünün komşularında da bir değişiklik olmuyor ve son olarak E düğümü deneniyor:
Son halimizde de bir değişiklik olmayarak şeklimiz (graph) kararlı bir halde ( daha fazla değişiklik olmadığı için) dolaşılmış ve bitmiş oluyor.
Yukarıdaki bu grafta, düğümler üzerinde yazılı olan değerler, A düğümünden başlanarak her düğüme gidilebilen en kısa yol mesafesini vermektedir. Örneğin şekildeki F düğümüne ulaşma maliyeti 3 olarak hesaplanmıştır ve Dijkstra algoritması, A düğümünden F düğümüne daha kısa bir yol bulunamayacağını iddia eder ( eşit farklı yollar bulunabilir ama en kısa yol yine de 3 olur)
Dijkstra algoritmasının zayıf yönü
Algoritma ne yazık ki eksi (-) değer taşıyan bir kenar bulunması halinde başarılı çalışmaz. Bunun sebebi eksi (-) değerdeki kenarın sürekli olarak mevcut durumdan daha iyi bir sonuç üretmesi ve algoritmanın hiçbir zaman için kararlı hale gelememesidir.
Örneğin aşağıdaki basit şekli ele alalım:
Yukarıdaki bu şekilde B-C kenarı (edge) -2 değerinde verilmiştir. Bu durumda A düğümünden başlayarak en kısa yolları hesaplamak istersek, öncelikli olarak A düğümünden komşusu olan düğümlere güncelleme yapılacaktır:
Ardından bu düğümlerin komşuları güncellenecektir. İki düğümde birbirine -2 değerini ekleyerek daha kısa bir yol bulacak ve birbirlerini güncelleyerek daha kısa sonuçlara ulaşacaktır.
Bu işlem ne yazık ki sonsuza kadar giden bir sürecin başlangıcıdır ve hiçbir zaman daha iyi bir sonuç bulma işlemi bitmez.
Sürekli olarak mevcut durumdan daha iyi bir durum bulunacak ve daha küçük değerler güncellenecektir. Bu yüzden Dijkstra algoritması, eksi (-) değer taşıyan şekillerde (graph) başarılı çalışmaz.
Teşekkürler hocam 🙂 İlaç gibi geldi sınav öncesinde.
http://www.ahmetalpbalkan.com
Bu arada negatif olma olayı en düşük negatif sayıyı bulup bütün sayılara o sayının mutlak değeri kadar ekleyip hepsini pozitif yaparak çözülebilir galiba.
Yine bu arada şu eklentiyi kurarsanız hoş olur :)) http://txfx.net/code/wordpress/subscribe-to-comments/
http://www.ahmetalpbalkan.com
“B ve C’den devam etmemizin bir önemi yok” diyorsunuz videoda. Ama amacımız hedefe en düşük maliyetli yoldan ulaşmak değilmi? o yüzden B’den devam edip sırasyla güncelleme yapmamız gerekmiyor mu?
sorunuzda haklı olabilirdiniz, şayet bir hedef olsaydı. Bakın videoda anlatılan dijkstra algoritması, bütün düğümlere olan en kısa yolu bulmayı hedeflemektedir.
Sorunuzu anlıyorum, şayet bir hedef (bazı kaynaklarda target, bazılarında ise sink olarak da geçer) bulunursa bu durumda bu hedefe gitmek için en kısa yolu almak ve düğümlerden birini tercih etmek gibi işlemler yapılabilir. Örneğin floyd-warshall algoritmasına veya Bellman Ford algoritmasına bakabilirsiniz.
Dijkstra algoritmasında ise, başlangıç olarak seçilen düğümden, diğer bütün düğümlere en kısa yol hesaplanır. Dijkstra algoritmasında bir hedef düğüm yoktur.
Problem olarak bir hedef düğüm tanımlı olursa, bu durumda Dijkstra algoritması bütün düğümlere olan en kısa yolu bulur sonra bunlardan birisi seçilir. Yani bir hedefiniz olsun veya olmasın, Dijkstra algoritmasını kullanıyorsanız, bütün düğümlere olan en kısa mesafe hesaplanır. Şayet bir hedefiniz varsa, bu hedefe giden en kısa yol da zaten hesaplanmış olunur. Ama dijkstra algoritması her hal-ü kârda bütün düğümlere olan en kısa yolları hesaplar.
Bu durumda, B veya C düğümlerinden istediğimiz birisiyle devam edebiliriz çünkü önce B’yi alırsak sonra C veya önce C’yi alırsak sonra B mutlaka hesaplanacaktır. Hangisinden başladığımızın bir önemi yoktur, zaten bütün düğümler hesaplanacaktır.
program DijkstraShortestPath;
{Bu uygulama bir “Optimum Güzergah Belirleme (Route Optimization)” uygulaması
olarak gereçekleştirilmiş olup; “Dijkstra alg.” örneklemesi olarak
hazırlanmıştır.
Türkiye üzerindeki iller düğüm (verticies), illerin birbirilerine olan
komşulukları ve uzaklıkları-ağırlıkları ayrıt (edge) olarak değerlendirilmiş ve
bu değerler komşuluk matrisi (Adjacency Matrix) kullanılarak deklare edilmiştir.
}
{$APPTYPE CONSOLE}
uses
SysUtils;
type
{İller alg. içerisinde “düğüm” olarak record veri yapısı ile ifade edilmektedir.
}
City_Node = record
City_Name: String [13]; // = Düğüm adları
Label_Leng: integer; // = Düğümün, başlangıç düğümünden geçici uzaklık değ.
Label_Path: String; // = Düğümün, geçici rotası.
Selected: Boolean; // = Düğümün kalıcı olarak işaretlenip-mediği gösterir.
end;
var
I: integer; // = Sayaç
City_Nodes: array of City_Node; // = Düğümleri dizisi.
Adj: array of array of integer; // = Düğümlerin komşuluk matrisi.
J, K, L, D: integer;
ShortPath: integer;
const N: Shortint = 81; // = Düğüm sayısı.
{Her düğümün komşuluk değeri; ilk iki karakter kaynak-source takip eden iki
karakter hedef-destination düğümün numarası olmak üzere müteakip üç karakterse
uzaklık-ağırlık değerini ifade etmek üzere 10 karakter ile ifade edilmiştir
(Boşluk karakteri ile birlikte).}
const Adj_Value_Stream: array[0..4239] of Char =
‘ 01 31 191 01 33 069 01 38 333 01 46 185 01 51 205 01 80 085 02 21 205’ +
‘ 02 27 150 02 44 185 02 46 164 02 63 110 03 15 170 03 20 225 03 26 144’ +
‘ 03 32 169 03 42 223 03 43 100 03 64 116 04 13 234 04 25 183 04 36 216’ +
‘ 04 49 245 04 65 232 04 76 143 05 19 092 05 55 132 05 60 114 05 66 196’ +
‘ 06 11 313 06 14 191 06 18 131 06 26 233 06 40 185 06 42 258 06 68 225’ +
‘ 06 71 076 06 78 215 07 15 122 07 32 130 07 33 489 07 42 323 07 48 313’ +
‘ 07 70 376 08 25 226 08 53 159 08 75 117 09 20 126 09 35 126 09 45 156’ +
‘ 09 48 099 10 16 151 10 17 207 10 35 173 10 43 221 10 45 137 11 06 313’ +
‘ 11 14 216 11 16 095 11 26 080 11 41 139 11 43 110 11 54 102 12 21 144’ +
‘ 12 23 142 12 24 271 12 25 180 12 49 114 12 62 141 13 04 234 13 21 209’ +
‘ 13 49 083 13 56 097 13 65 168 13 72 135 14 06 191 14 11 216 14 26 296’ +
‘ 14 54 114 14 67 159 14 78 134 14 81 045 15 03 170 15 07 122 15 20 150’ +
‘ 15 32 051 15 48 241 16 10 151 16 11 095 16 41 132 16 43 173 16 54 159’ +
‘ 16 77 069 17 10 207 17 22 217 17 59 188 18 06 131 18 19 156 18 37 114’ +
‘ 18 71 105 18 78 195 19 05 092 19 18 156 19 37 195 19 40 216 19 55 173’ +
‘ 19 57 299 19 60 178 19 66 104 19 71 167 20 03 225 20 09 126 20 15 150’ +
‘ 20 32 157 20 45 206 20 48 145 20 64 152 21 02 205 21 12 144 21 13 209’ +
‘ 21 23 153 21 44 251 21 47 095 21 49 258 21 63 176 21 72 100 22 17 217’ +
‘ 22 39 062 22 59 140 23 12 142 23 21 153 23 24 265 23 44 098 23 62 135’ +
‘ 24 12 271 24 23 265 24 25 189 24 28 293 24 29 131 24 44 363 24 58 246’ +
‘ 24 62 130 24 69 154 25 04 183 25 08 226 25 12 180 25 24 189 25 36 203’ +
‘ 25 49 247 25 53 377 25 61 303 25 62 243 25 69 125 25 75 231 26 03 144’ +
‘ 26 06 233 26 11 080 26 14 296 26 42 338 26 43 078 27 02 150 27 31 196’ +
‘ 27 46 080 27 63 137 27 79 063 27 80 120 28 24 293 28 29 162 28 52 044’ +
‘ 28 58 298 28 61 137 29 24 131 29 28 162 29 58 357 29 61 100 29 69 078’ +
‘ 30 56 287 30 65 202 30 73 189 31 01 191 31 27 196 31 79 147 31 80 127’ +
‘ 32 03 169 32 07 130 32 15 051 32 20 157 32 42 264 33 01 069 33 07 489’ +
‘ 33 42 348 33 51 198 33 70 235 34 39 211 34 41 111 34 59 132 35 09 126’ +
‘ 35 10 173 35 45 036 36 04 216 36 25 203 36 75 092 36 76 140 37 18 114’ +
‘ 37 19 195 37 57 183 37 74 182 37 78 112 38 01 333 38 46 273 38 50 081’ +
‘ 38 51 128 38 58 195 38 66 175 39 22 062 39 34 211 39 59 121 40 06 185’ +
‘ 40 19 216 40 50 091 40 66 112 40 68 110 40 71 113 41 11 139 41 16 132’ +
‘ 41 34 111 41 54 037 41 77 065 42 03 223 42 06 258 42 07 323 42 26 338’ +
‘ 42 32 264 42 33 348 42 51 241 42 68 148 42 70 119 43 03 100 43 10 221’ +
‘ 43 11 110 43 16 173 43 26 078 43 45 316 43 64 139 44 02 185 44 21 251’ +
‘ 44 23 098 44 24 363 44 46 223 44 58 247 44 62 233 45 09 156 45 10 137’ +
‘ 45 20 206 45 35 036 45 43 316 45 64 193 46 01 185 46 02 164 46 27 080’ +
‘ 46 38 273 46 44 223 46 58 345 46 80 100 47 21 095 47 56 230 47 63 188’ +
‘ 47 72 149 47 73 204 48 07 313 48 09 099 48 15 241 48 20 145 49 04 245’ +
‘ 49 12 114 49 13 083 49 21 258 49 25 247 49 72 218 50 38 081 50 40 091’ +
‘ 50 51 082 50 66 190 50 68 075 51 01 205 51 33 198 51 38 128 51 42 241’ +
‘ 51 50 082 51 68 123 52 28 044 52 55 152 52 58 314 52 60 219 53 08 159’ +
‘ 53 25 377 53 61 074 53 69 252 54 11 102 54 14 114 54 16 159 54 41 037’ +
‘ 54 81 069 55 05 132 55 19 173 55 52 152 55 57 163 55 60 231 56 13 097’ +
‘ 56 30 287 56 47 230 56 65 265 56 72 087 56 73 098 57 19 299 57 37 183’ +
‘ 57 55 163 58 24 246 58 28 298 58 29 357 58 38 195 58 44 247 58 46 345’ +
‘ 58 52 314 58 60 108 58 66 224 59 17 188 59 22 140 59 34 132 59 39 121’ +
‘ 60 05 114 60 19 178 60 52 219 60 55 231 60 58 108 60 66 207 61 25 303’ +
‘ 61 28 137 61 29 100 61 53 074 61 69 178 62 12 141 62 23 135 62 24 130’ +
‘ 62 25 243 62 44 233 63 02 110 63 21 176 63 27 137 63 47 188 64 03 116’ +
‘ 64 20 152 64 43 139 64 45 193 65 04 232 65 13 168 65 30 202 65 56 265’ +
‘ 65 73 363 66 05 196 66 19 104 66 38 175 66 40 112 66 50 190 66 58 224’ +
‘ 66 60 207 66 71 141 67 14 159 67 74 089 67 78 177 67 81 114 68 06 225’ +
‘ 68 40 110 68 42 148 68 50 075 68 51 123 69 24 154 69 25 125 69 29 078’ +
‘ 69 53 252 69 61 178 70 07 376 70 33 235 70 42 119 71 06 076 71 18 105’ +
‘ 71 19 167 71 40 113 71 66 141 72 13 135 72 21 100 72 47 149 72 49 218’ +
‘ 72 56 087 72 73 185 73 30 189 73 47 204 73 56 098 73 65 363 73 72 185’ +
‘ 74 37 182 74 67 089 74 78 088 75 08 117 75 25 231 75 36 092 76 04 143’ +
‘ 76 36 140 77 16 069 77 41 065 78 06 215 78 14 134 78 18 195 78 37 112’ +
‘ 78 67 177 78 74 088 79 27 063 79 31 147 80 01 085 80 27 120 80 31 127’ +
‘ 80 46 100 81 14 045 81 54 069 81 67 114’;
begin
try
{ TODO -oUser -cConsole Main : Insert code here }
SetLength(City_Nodes, N); // Düğümler dizisinin boyutu “N” değerine eşit.
SetLength(Adj, N + 1, N + 1); //Komşuluk dizisinin boyutu “N + 1” deg. eşit.
//—-Şehir adları düğüm adlarına eşitleniyor.—//
City_Nodes[01].City_Name := ‘Adana’;
City_Nodes[02].City_Name := ‘Adiyaman’;
City_Nodes[03].City_Name := ‘Afyon’;
City_Nodes[04].City_Name := ‘Agrı’;
City_Nodes[05].City_Name := ‘Amasya’;
City_Nodes[06].City_Name := ‘Ankara’;
City_Nodes[07].City_Name := ‘Antalya’;
City_Nodes[08].City_Name := ‘Artvin’;
City_Nodes[09].City_Name := ‘Aydın’;
City_Nodes[10].City_Name := ‘Balikesir’;
City_Nodes[11].City_Name := ‘Bilecik’;
City_Nodes[12].City_Name := ‘Bingol’;
City_Nodes[13].City_Name := ‘Bitlis’;
City_Nodes[14].City_Name := ‘Bolu’;
City_Nodes[15].City_Name := ‘Burdur’;
City_Nodes[16].City_Name := ‘Bursa’;
City_Nodes[17].City_Name := ‘Canakkale’;
City_Nodes[18].City_Name := ‘Cankiri’;
City_Nodes[19].City_Name := ‘Corum’;
City_Nodes[20].City_Name := ‘Denizli’;
City_Nodes[21].City_Name := ‘Diyarbakir’;
City_Nodes[22].City_Name := ‘Edirne’;
City_Nodes[23].City_Name := ‘Elazig’;
City_Nodes[24].City_Name := ‘Erzincan’;
City_Nodes[25].City_Name := ‘Erzurum’;
City_Nodes[26].City_Name := ‘Eskisehir’;
City_Nodes[27].City_Name := ‘Gaziantep’;
City_Nodes[28].City_Name := ‘Giresun’;
City_Nodes[29].City_Name := ‘Gümushane’;
City_Nodes[30].City_Name := ‘Hakkari’;
City_Nodes[31].City_Name := ‘Hatay’;
City_Nodes[32].City_Name := ‘Isparta’;
City_Nodes[33].City_Name := ‘Mersin’;
City_Nodes[34].City_Name := ‘Istanbul’;
City_Nodes[35].City_Name := ‘Izmir’;
City_Nodes[36].City_Name := ‘Kars’;
City_Nodes[37].City_Name := ‘Kastamonu’;
City_Nodes[38].City_Name := ‘Kayseri’;
City_Nodes[39].City_Name := ‘Kirklareli’;
City_Nodes[40].City_Name := ‘Kirsehir’;
City_Nodes[41].City_Name := ‘Kocaeli’;
City_Nodes[42].City_Name := ‘Konya’;
City_Nodes[43].City_Name := ‘Kutahya’;
City_Nodes[44].City_Name := ‘Malatya’;
City_Nodes[45].City_Name := ‘Manisa’;
City_Nodes[46].City_Name := ‘Kahramanmaras’;
City_Nodes[47].City_Name := ‘Mardin’;
City_Nodes[48].City_Name := ‘Mugla’;
City_Nodes[49].City_Name := ‘Mus’;
City_Nodes[50].City_Name := ‘Nevsehir’;
City_Nodes[51].City_Name := ‘Nigde’;
City_Nodes[52].City_Name := ‘Ordu’;
City_Nodes[53].City_Name := ‘Rize’;
City_Nodes[54].City_Name := ‘Sakarya’;
City_Nodes[55].City_Name := ‘Samsun’;
City_Nodes[56].City_Name := ‘Siirt’;
City_Nodes[57].City_Name := ‘Sinop’;
City_Nodes[58].City_Name := ‘Sivas’;
City_Nodes[59].City_Name := ‘Tekirdag’;
City_Nodes[60].City_Name := ‘Tokat’;
City_Nodes[61].City_Name := ‘Trabzon’;
City_Nodes[62].City_Name := ‘Tunceli’;
City_Nodes[63].City_Name := ‘Sanlıurfa’;
City_Nodes[64].City_Name := ‘Usak’;
City_Nodes[65].City_Name := ‘Van’;
City_Nodes[66].City_Name := ‘Yozgat’;
City_Nodes[67].City_Name := ‘Zonduldak’;
City_Nodes[68].City_Name := ‘Aksaray’;
City_Nodes[69].City_Name := ‘Bayburt’;
City_Nodes[70].City_Name := ‘Karaman’;
City_Nodes[71].City_Name := ‘Kirikkale’;
City_Nodes[72].City_Name := ‘Batman’;
City_Nodes[73].City_Name := ‘Sirnak’;
City_Nodes[74].City_Name := ‘Bartin’;
City_Nodes[75].City_Name := ‘Ardahan’;
City_Nodes[76].City_Name := ‘Igdır’;
City_Nodes[77].City_Name := ‘Yalova’;
City_Nodes[78].City_Name := ‘Karabuk’;
City_Nodes[79].City_Name := ‘Kilis’;
City_Nodes[80].City_Name := ‘Osmaniye’;
City_Nodes[81].City_Name := ‘Duzce’;
//-/-/-/-/-/-/-/-/-/-/-/-/-/-/-/-/-/-/-/-/-/-/-/-//
{Komşuluk Değerleri “Adj_Value_Stream” sabit değeri içerisinden okunarak
komşuluk matrisi içerisine alınmakta:}
{Başlangıçta düğümlerin kendilerine uzaklıkları hariç bütün uzaklıklar MaxInt
değerine eşitlenmekte, düğümlerin kendilerine komşulukları ise 0 değerine
eşitlenmektedir. }
for K := 1 to N do
begin
for J := 1 to N do
begin
Adj[K, J] := High(integer);
end;
end;
J := 0;
while J ‘);
Readln(K);
Write(‘Gitmek istediginiz sehrin plaka kodunu giriniz=>’);
Readln(D);
Writeln;
//————————Dijkstra’nın En Kısa Yol Alg.————————-
//1.Adım:***********************************************************************
for J := 1 to N do
begin
City_Nodes[J].Label_Leng := High(integer);
City_Nodes[J].Selected := False;
end;
City_Nodes[K].Label_Leng := 0;
City_Nodes[K].Selected := True;
City_Nodes[K].Label_Path:= City_Nodes[K].Label_Path + City_Nodes[K].City_Name;
I := 0;
L := 0;
//——————————————————————————
//2.Adım:***********************************************************************
repeat
{Seçili düğümün; komşu düğümlerinde kalıcı olarak seçili olmayan ve
seçili düğümün etiket uzaklık değeri ile komşu düğüme
uzaklık değeri toplamı komşu düğümün etiket uzaklık
değerinden küçükse komşu düğümün uzaklık ve rota
değerlerini seçili düğüm üzerinden olacak şekilde
değiştir.
}
for J := 1 to N do //J komşu düğümün indisidir.
begin
if ((City_Nodes[J].Selected = False) and //K ise seçili düğümün indisidir.
((City_Nodes[K].Label_Leng + Adj[K, J]) < (City_Nodes[J].Label_Leng))) then begin City_Nodes[J].Label_Leng := City_Nodes[K].Label_Leng + Adj[K, J]; City_Nodes[J].Label_Path := City_Nodes[K].Label_Path + ' ' + City_Nodes[J].City_Name; end; end; {Komşu düğümlerden; kalıcı olarak etiketlenmemiş ve etiket uzaklık değeri en küçük olanı kalıcı olarak etiketle ve seçili düğüme ata.} ShortPath := High(integer); for J := 1 to N do begin if ((City_Nodes[J].Selected = False) and (Adj[K, J] N -1); Writeln('Izlemeniz Gereken Rota=> ‘ + City_Nodes[D].Label_Path);
Writeln(‘Toplam Mesafe=> ‘ + IntToStr(City_Nodes[D].Label_Leng));
Readln;
except
on E:Exception do
Writeln(E.Classname, ‘: ‘, E.Message);
end;
end.
ShortPath := High(integer);
for J := 1 to N do
begin
if ((City_Nodes[J].Selected = False) and (Adj[K, J] N -1);
//satırı kırıp tekrar ekledim.
ShortPath := High(integer);
for J := 1 to N do
begin
if ((City_Nodes[J].Selected = False) and
(Adj[K, J] N -1);
kodunuzu buraya alırken sanırım bir kısmında problem yaşanmış. Sanırım delphi ile kodluyorsunuz ve kodunuzdan anlayabildiğim kadarıyla, şehirler arası mesafeleri tuttuğunuz dizi üzerinden işlem yapıyorsunuz. Bu bir hatadır ve hiç bir zaman birden fazla şehirden geçerek ulaştığınız mesafe, iki şehir arasındaki mesafeden kısa olamaz.
Bu durumu bir örnek üzeirinden açıklamaya çalışalım.
Yukarıdaki yazıda, verilen şekli düşünün. Buradaki şekilde bulunan düğümleri dolaşan iç içe iki döngüye ihtiyaç vardır. Yani birinci döngü bütün düğümleri sırayla dolaşacak ikinci döngü ise bu sıradaki düğümden komşu olan düğümlere gidilen yolları güncelleyecektir. Örneğimizde sırasıyla aşağıdaki güncellemeler yapılacaktır
A-B
A-C
B-F
B-E
C-F
C-D
…
Görüldüğü üzere dış döngü A,B,C şeklinde giderken, iç döngü önce B,C sonra F,E sonra F,D şeklinde dönüyor. Yani, örneğin, kuvvetli bağlı bir şekilde (strongly connected), n x (n-1) kere dönecek iç içe bir döngüden bahsediyoruz.
Sizin kodunuzda bulunan ve şehirlerin değerlerini güncelleyen koda baktığımızda:
”
for J := 1 to N do //J komşu düğümün indisidir.
begin
if ((City_Nodes[J].Selected = False) and //K ise seçili düğümün indisidir.
((City_Nodes[K].Label_Leng + Adj[K, J]) < (City_Nodes[J].Label_Leng))) then " şeklinde yazmışsınız. Buradaki döngü, gördüğünüz üzere tek bir döngüdür ve J ile K şehirleri arasındaki mesafeleri günceller. Buradaki J değişkeni, döngü değişkeni olduğuna göre sürekli değişmektedir. Oysaki K sabit kalmata ve yine kodunuzdan anladığım kadarıyla başlangıç şehrini temsil etmektedir. (kodunuzda bu değeri kullanıcıdan okuttuğunu ve gidilecek şehir sorusundan hemen önce okuttuğunuz için bu yorumu yapıyorum). Yukarıdaki problemi, kodunuzda 2. adım yorumuyla belirttiğiniz kısım çalıştıktan sonra, dizinin içeriğini ekrana bastırarak da test edebilirsiniz. Dizi içeriğinin beklediğiniz gibi her düğümden diğer her düğüme mesafe güncellemesi yapmadığını göreceksiniz. Şayet yapıyorsa ben kodunuzu yanlış okuyorum demektir ve kodunuzu bana mail yoluyla ulaştırmanız halinde size daha fazla yardımcı olmaya çalışırım. başarılar
peki dijkstra shortest path algoritmasının runing time nedir?
dijkstra algoritması, sadece komşuluk matrisi üzerinden (adjacency matrix) çalışabilen bir algoritmadır. Bütün komşuların hesaplanması ve güncellenmesi durumunda V adet düğüm (node, vertex) içeren bir şekil için O(V2) olarak hesaplanır. (burada komşuluk matrisinin kare matris olduğunu hatırlayınız).
Ancak algoritma üzerinde yapılan iyileştirmelerle bu değeri düşürmek mümkündür.
başarılar
merhaba şadi bey o kadar mutluyum ki siizn gibi birinin bizi aydınlatmasında videolarınız ççok beğeniyorum ve dinamik ve doğrusal programlama alanında ve daha bir çok konuda da olmasını isterdim teşekkurler
Teşekkürler hocam anlatım için çok iyi oldu.
http://www.volkanulutas.net
yapay zeka ile pac-man oyunu nasl çözülür.mesela A*,kruskal,prim,dijkstra algoritmaları nasl uygulanır oyuna
oyunların çoğunda sonucu bulmak için arama işlemi yapılmaktadır. Yani oyunu oynayan bilgisayar, insana benzer şekilde en mantıklı çözümü aramaktadır. Ancak bahsettiğiniz algoritmalar birbiri ile çok karşılaştırılabilir değiller.
Örneğin a* (astar) algoritması sezgisel (heuristic) algoritmadır (aşağıdaki bağlantıları okumanızda yarar var):
http://www.bilgisayarkavramlari.com/2009/03/02/a-yildiz-arama-algoritmasi-a-star-search-algorithm-a/
http://www.bilgisayarkavramlari.com/2008/12/22/sezgisel-algoritmalar-bulussal-algoritmalar-heuristic-algorithms/
Kruskal ve prims algoritmaları birer arama algoritması (search algorithm) değildir. Birer asgari tarama ağacı (minimum spanning tree) algoritmasıdır ve bu tip oyun çözümlerinde özel bir durum olmadıkça kullanılmaz. Örneğin pac-man için kullanışlı olabilir çünkü pac-man’in bütün ekranı dolaşma derdi vardır. Burada kullanışlı olabilir ama örneğin satranç, tictactoe gibi oyunlarda sonuç aranırken kullanışlı değillerdir (yine aşağıdaki algoritmaları okuyunuz).
http://www.bilgisayarkavramlari.com/2007/12/24/kruskal-asgari-tarama-agaci-algoritmasi/
http://www.bilgisayarkavramlari.com/2007/12/24/dijkstra-algoritmasi/
Dijkstra algoritması ise en kısa yol (shortest path) algoritmasıdır ve bir sonuca giden en kısa yol için kullanışlıdır. Şayet problem modeliniz sezgisel olmayan ve belirli (deterministic) yapıya sahipse kullanışlı olabilir.
Ayrıca oyun örneği olarak bir iki bağlantı aşağıda veriyorum bunları da okumanızda yarar var:
http://www.bilgisayarkavramlari.com/2011/06/23/hirsiz-oyunu-game-of-nim/
http://www.bilgisayarkavramlari.com/2009/04/29/minimax-agaclari-minimax-tree/
http://www.bilgisayarkavramlari.com/2012/01/15/prolog/
http://www.bilgisayarkavramlari.com/2011/11/04/labirentte-yol-bulma-kodu/
http://www.bilgisayarkavramlari.com/2011/11/13/sezgisel-fonksiyonlar-heuristic-functions/
Başarılar
Teşekkürler, sınav konusuydu. Bu sayfada anlayabildim sayenizde 🙂
dijkstra hangi cihazda kullanilir
Hocam ben yükseklisans öğrencisiyimde tezim için engelli bir yolda Dijikstra algoritmasının Matlab kodları gereklidir.Yardımcı olursanız sevinirim.