Dijkstra's Shortest Path

[Razu]

Öncelikle neden burdan yardım istiyorsun git birine sor diyenler olabilir ama sınavım yarın ve evdeyim bulabileceğim kimse yok,belki burdan biri yardım eder diye umuyorum.

http://rapidshare.com/files/240870844/Lecture_15-16-Network_Models.ppt.html

şimdi su adreste bir tane en kısa yolu bulmak için bir algorithm var,ama en sonundaki tabloya nasıl ulaştımıza bir türlü beynim basmıyor.umarım bilen biri vardır.

eyvs

[Ardeth]

penth falan almıştır ben de görmüştüm algoritma dersinde ama 2 sene oluyor aklımda kalmamış ama istersen şuraya bir bak (yarın sınavım olmasa tekrar çalışıp anlatırdım ama malesef var sdf)

http://en.wikipedia.org/wiki/Dijkstra's_algorithm

yanlış hatırlamıyorsam bütün olasıkları tüketen bir algoritmaydı ama bu yani kısacası yoğun olmayan ağaçlarda sıra sıra başlangıç düğümünden her düğüme olası yolları hesaplayıp yol hesapladıkça daha küçük bulursa onla değiştiriyordu. yani bu problemi çözmek için aklına gelebilecek ilk yöntem bu, hiç bir özelliği yok olası bütün yolları hesaplıyor.

[asinanyavuz]

Çok basitçe Dijkstra şey yapıyor diye hatırlıyorum, başladığın node'un adjacent nodelarına distance larını belirliyorsun, minimum olan node'u known belirleyip o node'a devam ediyorsun. O node da adjacent nodelara distanceları hesaplıyorsun (tabii bir önceki node ile ortak komşu node varsa, hangi uzaklık küçükse onu bırakıyorsun). Şu ana kadar distance set ettiğin nodelardan en kısa distance hangisiyse o node'u known belirleyip o node a geçiyorsun. Tüm graph'ı tarayana kadar bu şekilde devam ediyorsun.

Tablo da yaptığı da aynısı. İlk adımda NY den başlamış. NY ye komşu olan yerlere uzaklığını koymuş. Minimum Pittsburgh. Onu known seçmiş artık, devam etmiş. Pittsburgh'un komşularına distancelarını belirlemiş. Bakmış en kısa uzaklık Atlanta, onu known ilan edip, onun komşularına bakmış (iteration 3 e geldik). .... diye devam ediyor işte.

Çok iyi anlatamamış olabilirim, pardons.

[Razu]

en kısa yolu hesaplamak sorun değil zaten, bazı nodelardan bazı nodelara geçerken yazmıyor mesela en son tabloda.olay tabloyu tam anlamıyla yapabilmek zaten,gerisi tırt.

[Ardeth]

edit:

tamam bakıyorum tabloya şimdi T_T

[asinanyavuz]

Tamam da yazmış işte adam negzel negzel. Ben anlamadım orada nereye takıldığını. Her node u known ilan ettikten sonra bi daha onun distance valuesunu yazmamış, o mu sorun?

[Razu]

mesela neden pitsburg'da 1 tane normal parantez bir tane köşeli parantez kullanıp s.t 3 normal 1 köşeli kullanması.köşeli parantez sanırım senin dediğin known olarak yada permanent label olarak geçiyor.

[Ardeth]

tabloda birşey yok gibi.

birinci döngüde newyorktan yola çıkıp bütün komşularına (=tek bir adımda ulaşabileceğin komşular) olan uzaklığa bakıyorsun (kendine olan uzaklığı sıfır). Diğerlerinin uzaklığı çizgi daha onlara hiç bakmadın. İkinci döngüde komşularından birini seçip onla devam ediyorsun (önemli değil hangisi bir komşusu olsun yeter bütün ağacı dolaşacaksın zaten). pitsburgu seçmiş adam, pitsburga olan daha önceki yol 450, şimdi pitsburgun bütün komşularına olan uzaklığına bakıyorsun, üzerine 450 ekliyorsun böylece newyorka pitsburg üzerinden olan uzaklığını buluyorsun. daha önce üzerine mesafe yazılmış olan şehirler varsa SADECE yeni hesapladığın değer eskisinden küçükse değiştiriyorsun yoksa öyle bırakıyorsun. Böyle böyle devam ediyor işte, bir olayı yok.

[Ardeth]

Razu said:

mesela neden pitsburg'da 1 tane normal parantez bir tane köşeli parantez kullanıp s.t 3 normal 1 köşeli kullanması.köşeli parantez sanırım senin dediğin known olarak yada permanent label olarak geçiyor.

abi köşeli parantez, o döngüde üzerinde olduğun şehir, eğik parantez ise tüm komşuları. benden bu kadar, algoritmadan ve wikipediadaki grafikten farkı yok tablonun.

neden öyle garip bir seçim yapmış dersen, seçimini en yakın komşudan en uzağa gidecek şekilde ayarlamış sanırım ondan.

yani sen newyorkun komşularına olan uzaklığını hesapladıktan sonra sırayla, ptsburgh, atlanta ve st. louise bakıyorsun (uzaklık sırası öyle çünkü ama bir önemi yok hepsini seçmeye dikkat et yeter)

[Penthesilea]

Djikstra's alg eger belli bi bitis noktasi varsa heuristic search e giriyor, exhaustive ancak bitis noktasi yoksa oluyor.

Abi Visited ve Unvisited listen var, baslangicta tum visited bos, unvisited de tum nodelar var. her node'un bi "distance" degeri var ve bu distance'in temsil ettigi sey "bu node baslangictan ne kadar uzakta(shortest path olarak)". baslangicta, tum nodelarin distance'ini sonsuz yapiyorsun.

baslangic node'undan basliyorsun, ve alttaki kisim repeat ediyo:

o anda uzerinde oldugun node'un tum komsulari icin yeni distance'i hesapla, bunu soyle yapiyorsun:
uzerinde oldugun node'un distance'i + komsuyla arasindaki arc'in degeri

sonra bu hesapladigin degeri, komsunun "distance"iyla karsilastiriyosun. eger yeni deger daha iyiyse, komsunun yeni distance'i olarak bu degeri yaziyosun. degilse bisey yapmiyosun. tum neigborlar icin bu islemi yaptiktan sonra, uzerinde oldugun node'u visited listesine ekliyosun.

sonra ayni islemi bir sonraki node icin yapiyorsun, bir sonraki node'un da unvisited listesindeki en ufak "distance" li node.

goal node'un visited listesine girdigi anda algoritmayi break edebilirsin, isin heuristic kismi burasi. bir node visited a eklendigi anda, distance'i baslangic noktasina direk shortest path olmus oluyor. ve visited'a giren node bir daha hic consider edilmiyor.

umarim yeterlidir.

[asinanyavuz]

Köşeli parantezi o iterationda bulunduğu node'u belirtmek için kullanmış. Normal parantez de diğer nodeların distanceları için kullanılmış.

[Penthesilea]

oha ben reply'a basarken hic bi cevap yoktu, kiz arkadas harass i boyle bisey iste bi yandan telefonda

[Ardeth]

biz mi dedik arkadaşım kız arkadaş yap diye dsfsd

[GEd]

Yarı ingilizce yarı türkçe bütün mesajlar , ne biçim eğitiliyoruz , bende mesaj atsam yarı almanca yarı türkçe olurda, harbi dili tüketmişiz resmen ama.

[Ardeth]

evet konuşurken bir nebze kabul edilebilir ama yazarken yapmamak lazım aslında ayıp ettik herkes editlesin mesajını

[GEd]

Yetkin var işte sen editle hepsini bence ^^


Görevimiz Türkçe :D

[asinanyavuz]

Node'un Türkçesi ne mesela? Yuvarlakçık, topçuk, nokta falan mı?

[GEd]

Düğüm ?

[Ardeth]

düğüm

[asinanyavuz]

Oha pek cahilmişim, sustum.

[Razu]

Ardeth said:

benden bu kadar, algoritmadan ve wikipediadaki grafikten farkı yok tablonun.

tamam vurma abi : ( ben tabloyu en başından beri farklı yorumluyormuşum onun için salak salak bakıyordum öylece.

neyse birazcık anladım gibi bi kaç daha örnek bakarsam yaparım herhalde o kadarsa kasış bişi değil(sonuç olarak introduction zaten :)),yardım etmeye çalışan herkese teşekkürler bide

[Razu]

ha bide bir şey sorayım mesela pitsburgdan st. louis'e geçiş yok aynı bırakıyoruz değil mi onu?

[Penthesilea]

abi dedim ya sadece komsulara bakicaksin

turkce muhabbetine gelince ben yapay zeka derslerini isvec ve amerika'da aldim, boyle ogrendim, itu gibi ceviremicem.

[Ardeth]

evet her döngüde, sadece üzerinde bulunduğun düğümün komşuları üzerinde hesap yapıyorsun.

[Ardeth]

Penthesilea said:

turkce muhabbetine gelince ben yapay zeka derslerini isvec ve amerika'da aldim, boyle ogrendim, itu gibi ceviremicem.

oo yapay zeka, isveç, amerika çok güzel de bunların dijikstra algoritması gibi tırışkadan bir algoritma ve içerdiği 2 terimle ilgisi nedir sdf