Yol Algoritması

[4Ever]

Selam,

Aşağıdaki matris deki şehirleri gezecek en kısa yolu çizmem gerekiyor.



Rota: Ankara-İstanbul-Trabzon-İzmir-Antalya-Bursa-Ankara

Yukarıda rotanın şehirlerini birbirlerinin mesafelerine göre dizmem gerekiyor ve toplamda bana en kısa rotayı çıkartması gerekiyor.

Tabi algoritma dediysem :) bunun Excel VBA kullanarak Excel de yapacağım. Yardımlarınız gerekiyor.

[forgiver]

http://www.biology.arizona.edu/biomath/tutorials/trigonometric/graphics/trig_30_60_90.gif

hipotenüs çek

[SeaGle]

30-60-90 üçgeni.

[riglous]

Google: "breadth first search with vb"

[aquila]

hosgeldin traveling salesperson.

[ginaly]

Solver add-in kullan, vba hic ugrasma bence

[4Ever]

Malesef VBA kullanarak yapmam gerekiyor. En son düzgün halini göstermem lazım.

Aslında orada 4 5 şehir var ama normalde matrisdeki şehir sayısı çok fazla. Dedikleri gibi satıcının gezeceği şehirlerin en kısa rotadan gitmesini sağlamam gerekiyor ve en sonunda başladığı noktaya dönmesi gerekiyor.

[elesso]

istanbul
bursa
izmir
antalya
ankara
trabzon



ben olsam böyle giderdim asfd

[Suark]

abi ben anlamadım ya ne istendiğini

[4Ever]

Şimdi,

Bu şehirlere gitmem gerekiyor. Ama hangi sırayla gidersem daha az KM yol yapmış oluyorum onu bulmam gerekiyor.

Matrise göre
Ankara-İstanbul-Trabzon-İzmir-Antalya-Bursa-Ankara = 365 Km.

Ankara-İstanbul-Bursa-İzmir-Trabzon-Antalya-Ankara = 345 Km.

yazdığım 2 rota arasında 20KM gibi bir fark oluyor bunun gibi tüm şehirlere uğrayarak gidilebilecek en kısa yolu çıkartmalıyım.

ama başlangıç ve bitiş ankara olmak zorunda.

[Kojiroh]

DİJKASTIRA çak gitsin ya http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm

[4Ever]

DİJKASTIRA. Sadece 1 hedefe giden en kısa yolu bulmaya yaramıyor mu? Benim tüm şehirlerede gitmem gerekiyor ama.

[Kojiroh]

Abi düz adam yolunu seçtim ben, her şehir için birer dijkastıra çakıp en ufağını almayı :P

[Suark]

e bodoz yapalım abı o zaman
şehirleri harflere kodladım diyelim A ankara gerisi b c d e f diye sıraladık


A - B - C - D - E - F - A boldlular aralarında değişecekler.
ne edio bu 5! mi?

loopa alıp hesaplattırıp minimumu çıkartsak ^^. Nedir yani 120 route var farklı, hepsini çıkartıp sonra minimumu alacak.

hatta daha güzeli şu

Yol değeri bizim toplam mesafemiz olsun,
eğer bi önceki yol değeri şu an hesapladığından ufaksa hiç kaale alma bunu diğerine geç diyip hızlandırabilirsin.

[Kharon]

efficiency diye bisey vardi en son.

bakilmasi gereken "all-pairs shortest path"
dijkstra , johnson ,flloyd falan uygulanabiliyordu.

[fizban]

shortest hamiltonian cycle diye arat iste. ama polynomial time'da cozen bir algoritma yok.

[elesso]

http://www.slideshare.net/alonasalva/shortest-route-and-mst

[fizban]

adamin aradigi sey o degil. dijkstra, i ve j node'lari arasindaki en kisa yolu verir. aranan sey, tum node'lari iceren en kisa rotayi bulmak. tum node'lari iceren yol hamiltonian cycle demek. minimum cost hamiltonian cycle da tsp'nin tanimi zaten.

[Rasmon]

http://www.gokhanca.com/index.php?option=com_content&task=view&id=44&Itemid=31

[fizban]

bu da degil.

[Sparkcaster]

fizban çok bilmiyo arkadaşlar bu programcılık işlerini, dinlemeyin.

[fizban]

bu hic degil.

[4Ever]

Bunlara baktım cogu hedefe giden en kısa yolu gösteriyor. Benim yapmak istediğim rotamdaki şehirlerin sırasını değiştirmek ve toplamda en kısa yolu bulmak.

[fizban]

tamam iste, hamiltonian cycle diyorum. travelling salesman problem diyorum. onlara bak

al mesela google'layinca cikan 3. sonuc mu ne
http://goo.gl/Ts8sK

[Suark]

yazdım ben kanka işte
oda bi algoritma sayılır brutal force tarzı.

zaten 120 route var, ne kadar inneficient olunabilir ki