Shortest Path - En Kısa Yol Problemi
Seyyar satıcı problemi şu şekilde tanımlanabilir:
Bir seyyar satıcı var;
Bu satıcı, mallarını n şehirde satmak istiyor;
Öte yandan, mantıklı bir şekilde, bu satıcı bu şehirleri mümkün olan en kısa şekilde ve her bir şehre maksimum bir kere uğrayarak turlamak istiyor.
Problemin amacı, satıcıya bu en kısa yolu sunabilmektir.
Bu problem, bir matematiksel problem olarak 1930'lu yıllarda formüle edilmiştir. Optimizasyon konusunda en derin inceleme konularından biridir. "Hesaplamanın karmaşıklığı" teorisine göre çözümü NP-Tam olan en önemli algoritma problemlerinden biridir. Bundan dolayı seyyar satıcı problemlerini etkin olarak çözebilecek bir algoritma olmadığı kabul edilmektedir. Diğer bir deyimle en kötü durumda algoritma kullanılırken yapılan hesapların sayısının (yanı bilgisayar kullanma zamanının) şehir sayıları arttıkça üssel olarak artması çok olasıdır. Bazı durumlarda sadece yüz şehirlik liste olmasına rağmen çözüm yapılırken çözümün yıllar alabileceği iddia edilmektedir.
Diğer optimizasyon problemlerine bir nirengi noktası ve bir mihenk taşı gibi yol gösterici ve değerleyici problem olarak kullanılmaktadır. Problem sonucunu hesaplamak, çok zor olmakla beraber hem tam sonuç verebilecek ve hem de "sezgisel (heuristic)" sonuçlar verebilecek birçok çözüm yöntemi bilinmektedir ve pratikte bazen on binlerce şehri ihtiva eden listelerden oluşan problemlerin çözülebileceği bilinmektedir.
Çözüm :
Basit bir şekilde:
Başlangıç için seçebileceği n , değişik şehir vardır
İlk şehirde, satıcının n-1 , değişik şehir arasında seçim hakkı vardır
İkinci şehirde, satıcının n - 2 , değişik şehir arasında seçim hakkı vardır
vs.
Dolayısıyla, sonuç olarak satıcının (n)! , değişik tur arasından seçim hakkı olacaktır. Bu, 100 şehirlik bir tur için bile 9,33 * 10 ^ { 157 } , değişik tur etmektedir!
Su an itibariyle bulunabilmiş en güçlü kesin çözüm sunan algoritma (Dinamik Programlama)ile O (n ^ { 2 } * 2 ^ { n }) , zamanda çözulebilmektedir. Mesela, 100 şehirlik bir tur için bu 1,26 * 10 ^ {30} , adım etmektedir.
Bugüne kadar çözülen en büyük seyyar satıcı problemi 24.978 noktalıdır ve İsveç'te yerleşimi olan her nokta için çözülmüştür. Bu çözüm, Intel Xeon 2,8 Ghz bir işlemcinin 92 yılına denk bir sürede yapılmıştır (öte yandan, 96 bilgisayarlı bir ağ üzerinde çözüldüğünden çözülmesi 3 yıl sürmüştür). Şu anda çözülmeye çalışılan en büyük problem dünya üzerinde kayıtlı yerleşim olan her nokta için en kısa yolun ne olduğudur. Bu problem 1.904.711 şehir içermektedir.
Bu problem, seyyar satıcılardan öte internet üzerinde paketlerin yönlendirilmesi gibi konuların çözümünde de faydalı olacağından önemli bir problemdir.
Aşağıdakı kod, çözümde verilen yöntemin c++'da uygulanmış halidir.
Şehirlerle ilgili veriler shortestpath2.in ve çıktılar shortestpath2.out dosyasında bulunmaktadır.
Aşağıdaki görsel ve kaynak kodunu inceleyebilirsiniz.
Bir seyyar satıcı var;
Bu satıcı, mallarını n şehirde satmak istiyor;
Öte yandan, mantıklı bir şekilde, bu satıcı bu şehirleri mümkün olan en kısa şekilde ve her bir şehre maksimum bir kere uğrayarak turlamak istiyor.
Problemin amacı, satıcıya bu en kısa yolu sunabilmektir.
Bu problem, bir matematiksel problem olarak 1930'lu yıllarda formüle edilmiştir. Optimizasyon konusunda en derin inceleme konularından biridir. "Hesaplamanın karmaşıklığı" teorisine göre çözümü NP-Tam olan en önemli algoritma problemlerinden biridir. Bundan dolayı seyyar satıcı problemlerini etkin olarak çözebilecek bir algoritma olmadığı kabul edilmektedir. Diğer bir deyimle en kötü durumda algoritma kullanılırken yapılan hesapların sayısının (yanı bilgisayar kullanma zamanının) şehir sayıları arttıkça üssel olarak artması çok olasıdır. Bazı durumlarda sadece yüz şehirlik liste olmasına rağmen çözüm yapılırken çözümün yıllar alabileceği iddia edilmektedir.
Diğer optimizasyon problemlerine bir nirengi noktası ve bir mihenk taşı gibi yol gösterici ve değerleyici problem olarak kullanılmaktadır. Problem sonucunu hesaplamak, çok zor olmakla beraber hem tam sonuç verebilecek ve hem de "sezgisel (heuristic)" sonuçlar verebilecek birçok çözüm yöntemi bilinmektedir ve pratikte bazen on binlerce şehri ihtiva eden listelerden oluşan problemlerin çözülebileceği bilinmektedir.
Çözüm :
Basit bir şekilde:
Başlangıç için seçebileceği n , değişik şehir vardır
İlk şehirde, satıcının n-1 , değişik şehir arasında seçim hakkı vardır
İkinci şehirde, satıcının n - 2 , değişik şehir arasında seçim hakkı vardır
vs.
Dolayısıyla, sonuç olarak satıcının (n)! , değişik tur arasından seçim hakkı olacaktır. Bu, 100 şehirlik bir tur için bile 9,33 * 10 ^ { 157 } , değişik tur etmektedir!
Su an itibariyle bulunabilmiş en güçlü kesin çözüm sunan algoritma (Dinamik Programlama)ile O (n ^ { 2 } * 2 ^ { n }) , zamanda çözulebilmektedir. Mesela, 100 şehirlik bir tur için bu 1,26 * 10 ^ {30} , adım etmektedir.
Bugüne kadar çözülen en büyük seyyar satıcı problemi 24.978 noktalıdır ve İsveç'te yerleşimi olan her nokta için çözülmüştür. Bu çözüm, Intel Xeon 2,8 Ghz bir işlemcinin 92 yılına denk bir sürede yapılmıştır (öte yandan, 96 bilgisayarlı bir ağ üzerinde çözüldüğünden çözülmesi 3 yıl sürmüştür). Şu anda çözülmeye çalışılan en büyük problem dünya üzerinde kayıtlı yerleşim olan her nokta için en kısa yolun ne olduğudur. Bu problem 1.904.711 şehir içermektedir.
Bu problem, seyyar satıcılardan öte internet üzerinde paketlerin yönlendirilmesi gibi konuların çözümünde de faydalı olacağından önemli bir problemdir.
Aşağıdakı kod, çözümde verilen yöntemin c++'da uygulanmış halidir.
Şehirlerle ilgili veriler shortestpath2.in ve çıktılar shortestpath2.out dosyasında bulunmaktadır.
Aşağıdaki görsel ve kaynak kodunu inceleyebilirsiniz.
Kaynak Kodu :
//C++
Programming Language
// zafercavdar
#include <cstdlib>
#include <cstdio>
#include <cmath>
FILE *inputf = fopen ("shortestpath2.in","r");
FILE *outputf = fopen ("shortestpath2.out","w");
int city_number,a=1;
int way_number;
double distance[1000][1000];
int start,end;
int checkway[1000][1000];
double minimumway[1000];
int updatedby[1000];
int map[1000];
void getinput()
{
int a,b;
double d;
fscanf(inputf,"%d",&city_number);
fscanf(inputf,"%d",&way_number);
for (int i=0 ; i<way_number ; i++)
{
fscanf(inputf,"%d %d %lf",&a,&b,&d);
distance[a][b]=distance[b][a]=d;
checkway[a][b]=checkway[b][a]=1;
}
fscanf(inputf,"%d",&start);
fscanf(inputf,"%d",&end);
for (int ff=1; ff<city_number+1; ff++)
minimumway[ff]=99999;
}
void drawway(int city_start)
{
if (city_start!=end)
for (int c=1; c<city_number+1 ; c++)
if (c!=city_start && checkway[city_start][c]==1)
if (distance[city_start][c]+minimumway[city_start] < minimumway[c])
{
minimumway[c]=distance[city_start][c]+minimumway[city_start];
updatedby[c]=city_start;
drawway(c);
}
}
void createmap(int city_end)
{
map[a++]=city_end;
if (city_end!=start)
createmap(updatedby[city_end]);
}
void drawoutput()
{
fprintf(outputf,"From : City %d\nTo : City %d\n\n",start,end);
fprintf(outputf,"Minimum Travel Time : %0.2lf hours.\n",minimumway[end]);
fprintf(outputf,"Total Visited Cities : %d\n\nFollow this way : \n\n",a-1);
for (int i=a-1; i>0; i--)
{
if (i!=1)
fprintf(outputf,"(City %d) || after %0.2f hours -> ",map[i],distance[map[i]][map[i-1]]);
if (i==1)
fprintf(outputf,"(City %d)\n",map[i]);
}
}
void callfunction()
{
getinput();
minimumway[start]=0;
drawway(start);
createmap(end);
drawoutput();
}
void closefiles()
{
fclose(inputf);
fclose(outputf);
}
int main()
{
callfunction();
closefiles();
return 0;
}
// zafercavdar
#include <cstdlib>
#include <cstdio>
#include <cmath>
FILE *inputf = fopen ("shortestpath2.in","r");
FILE *outputf = fopen ("shortestpath2.out","w");
int city_number,a=1;
int way_number;
double distance[1000][1000];
int start,end;
int checkway[1000][1000];
double minimumway[1000];
int updatedby[1000];
int map[1000];
void getinput()
{
int a,b;
double d;
fscanf(inputf,"%d",&city_number);
fscanf(inputf,"%d",&way_number);
for (int i=0 ; i<way_number ; i++)
{
fscanf(inputf,"%d %d %lf",&a,&b,&d);
distance[a][b]=distance[b][a]=d;
checkway[a][b]=checkway[b][a]=1;
}
fscanf(inputf,"%d",&start);
fscanf(inputf,"%d",&end);
for (int ff=1; ff<city_number+1; ff++)
minimumway[ff]=99999;
}
void drawway(int city_start)
{
if (city_start!=end)
for (int c=1; c<city_number+1 ; c++)
if (c!=city_start && checkway[city_start][c]==1)
if (distance[city_start][c]+minimumway[city_start] < minimumway[c])
{
minimumway[c]=distance[city_start][c]+minimumway[city_start];
updatedby[c]=city_start;
drawway(c);
}
}
void createmap(int city_end)
{
map[a++]=city_end;
if (city_end!=start)
createmap(updatedby[city_end]);
}
void drawoutput()
{
fprintf(outputf,"From : City %d\nTo : City %d\n\n",start,end);
fprintf(outputf,"Minimum Travel Time : %0.2lf hours.\n",minimumway[end]);
fprintf(outputf,"Total Visited Cities : %d\n\nFollow this way : \n\n",a-1);
for (int i=a-1; i>0; i--)
{
if (i!=1)
fprintf(outputf,"(City %d) || after %0.2f hours -> ",map[i],distance[map[i]][map[i-1]]);
if (i==1)
fprintf(outputf,"(City %d)\n",map[i]);
}
}
void callfunction()
{
getinput();
minimumway[start]=0;
drawway(start);
createmap(end);
drawoutput();
}
void closefiles()
{
fclose(inputf);
fclose(outputf);
}
int main()
{
callfunction();
closefiles();
return 0;
}