Şehirler Arası Elektrik Aktarım Algoritması
Size bir bölgenin haritası veriliyor, şehirlerin konumlarını biliyorsunuz, şehirler arası mesafeleri biliyorsunuz ama bir sorununuz var: bölgede çok sayıda kasaba ve şehir var. Sizin göreviniz elektrik direklerini en mantıklı, en etkili şekilde döşemek. Minimum maliyete bir merkezden elektrik dağıtımını sağlamak. İstediğiniz şehirden istediğinize elektrik taşıyabiliyorsunuz fakat işinizin sonunda çıkardığınız ağ haritası, çekilmesi gereken minimum uzunluktaki elektrik tellerinden oluşmak zorunda. Bunu nasıl yapabilirsiniz ? Ya da bir algoritma geliştirerek bunu 3000 şehir ve değişken elektrik dağıtım merkezlerini de göz önünde bulundurarak en kısa yolu nasıl bulabiliriz ?
Bunun için "shortest path" algoritmasını kullanmalıyız.
Bunun için "shortest path" algoritmasını kullanmalıyız.
Shortest path algoritması şöyle işler ;
1 - Bir merkezin bağlantılı olabileceği tüm şehirlere bir cost değeri verilir. Bu değer merkeze olan uzaklık değeridir.
2 - Bu işlem merkezin bağlantılı olduğu her bir şehir için tekrar uygulanır. (Queue Data Diagram ile bu yapılır.) Diyelim 1.şehir için cost değeri ilk tur için 5 olsun.
Eğer Merkezden 3.şehire gidilip ordan 1.şehire geçildiğinde cost değeri 4 oluyorsa 5 değeri silinir artık yolumuz 4 lük yol olur. Böylece tüm harita taranana kadar minimum cost değerleriyle ilerleyerek ve tüm bağlantıların sağlandığından emin olarak ilerleriz.
3 - Haritada tüm ağlar kurulduğunda ve Queue Data Diagram sonlandığında önümüzdeki cost değerleriyle yapmamız gereken tek şey haritayı oluşturmaktır.
Aşağıdaki kodu inceleyebilirsiniz. elec.in ve elec.out girdi çıktı dosyası açmasını unutmayın.
1 - Bir merkezin bağlantılı olabileceği tüm şehirlere bir cost değeri verilir. Bu değer merkeze olan uzaklık değeridir.
2 - Bu işlem merkezin bağlantılı olduğu her bir şehir için tekrar uygulanır. (Queue Data Diagram ile bu yapılır.) Diyelim 1.şehir için cost değeri ilk tur için 5 olsun.
Eğer Merkezden 3.şehire gidilip ordan 1.şehire geçildiğinde cost değeri 4 oluyorsa 5 değeri silinir artık yolumuz 4 lük yol olur. Böylece tüm harita taranana kadar minimum cost değerleriyle ilerleyerek ve tüm bağlantıların sağlandığından emin olarak ilerleriz.
3 - Haritada tüm ağlar kurulduğunda ve Queue Data Diagram sonlandığında önümüzdeki cost değerleriyle yapmamız gereken tek şey haritayı oluşturmaktır.
Aşağıdaki kodu inceleyebilirsiniz. elec.in ve elec.out girdi çıktı dosyası açmasını unutmayın.
Kaynak Kodu :
//C++ Programming Language
// zafercavdar
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
FILE *outputf=fopen("elec.out","w");
FILE *inputf=fopen("elec.in","r");
int numofcity;
int city[50][2];
int distance[50][50];
int sehirharitasi[1000][1000],maxx=0,maxy=0;
void oku()
{
fscanf(inputf,"%d",&numofcity);
for(int i=0;i<numofcity;i++)
for(int j=0;j<2;j++)
{
fscanf(inputf,"%d",&city[i][j]);
if (j==0)
if (city[i][j]>maxx)
maxx=city[i][j];
if (j==1)
if (city[i][j]>maxy)
maxy=city[i][j];
}
}
double getdistance(int s1,int s2)
{
int x1=city[s1][0];
int y1=city[s1][1];
int x2=city[s2][0];
int y2=city[s2][1];
return sqrt((double)(x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
}
void ciz()
{
for(int i=0;i<maxx+1;i++)
for(int j=0;j<maxy+1;j++)
sehirharitasi[i][j]=-1;
for (int i=0;i<numofcity;i++)
sehirharitasi[city[i][0]][city[i][1]]=i;
for (int i=0;i<maxx+1;i++)
{
for (int j=0;j<maxy+1;j++)
{
if (sehirharitasi[i][j]==-1)
fprintf(outputf," ");
if (sehirharitasi[i][j]>-1)
fprintf(outputf,"%d*",sehirharitasi[i][j]);
}
fprintf(outputf,"\n");
}
}
void init()
{
for(int i=0;i<numofcity;i++)
for(int j=i;j<numofcity;j++)
distance[i][j]=distance[j][i]=getdistance(i,j);
}
void findpair(int electricity[50],int *pn1,int *pn2)
{
int minuzaklik=9999999,minn1,minn2;
for (minn1=0;minn1<numofcity;minn1++)
if (electricity[minn1]==1)
{
for (minn2=0;minn2<numofcity;minn2++)
if (electricity[minn2]==0 && minn2!=minn1)
if (distance[minn1][minn2]<minuzaklik)
{
minuzaklik=distance[minn1][minn2];
*pn1=minn1;
*pn2=minn2;
}
}
}
void yap()
{
double totalcost=0.0;
int turn=0;
int electricity[50]={0,};
electricity[0]=1;
while(turn++<numofcity-1)
{
int n1,n2;
findpair(electricity,&n1,&n2);
fprintf(outputf,"%d-->%d : %f\n",n1,n2,getdistance(n1,n2));
totalcost+=getdistance(n1,n2);
electricity[n1]=1;
electricity[n2]=1;
}
fprintf(outputf,"Total Cost : %f\nCity Map : \n",totalcost);
}
int main()
{
oku();
init();
yap();
ciz();
fclose(inputf);
fclose(outputf);
system("PAUSE");
return 0;
}
// zafercavdar
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
FILE *outputf=fopen("elec.out","w");
FILE *inputf=fopen("elec.in","r");
int numofcity;
int city[50][2];
int distance[50][50];
int sehirharitasi[1000][1000],maxx=0,maxy=0;
void oku()
{
fscanf(inputf,"%d",&numofcity);
for(int i=0;i<numofcity;i++)
for(int j=0;j<2;j++)
{
fscanf(inputf,"%d",&city[i][j]);
if (j==0)
if (city[i][j]>maxx)
maxx=city[i][j];
if (j==1)
if (city[i][j]>maxy)
maxy=city[i][j];
}
}
double getdistance(int s1,int s2)
{
int x1=city[s1][0];
int y1=city[s1][1];
int x2=city[s2][0];
int y2=city[s2][1];
return sqrt((double)(x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
}
void ciz()
{
for(int i=0;i<maxx+1;i++)
for(int j=0;j<maxy+1;j++)
sehirharitasi[i][j]=-1;
for (int i=0;i<numofcity;i++)
sehirharitasi[city[i][0]][city[i][1]]=i;
for (int i=0;i<maxx+1;i++)
{
for (int j=0;j<maxy+1;j++)
{
if (sehirharitasi[i][j]==-1)
fprintf(outputf," ");
if (sehirharitasi[i][j]>-1)
fprintf(outputf,"%d*",sehirharitasi[i][j]);
}
fprintf(outputf,"\n");
}
}
void init()
{
for(int i=0;i<numofcity;i++)
for(int j=i;j<numofcity;j++)
distance[i][j]=distance[j][i]=getdistance(i,j);
}
void findpair(int electricity[50],int *pn1,int *pn2)
{
int minuzaklik=9999999,minn1,minn2;
for (minn1=0;minn1<numofcity;minn1++)
if (electricity[minn1]==1)
{
for (minn2=0;minn2<numofcity;minn2++)
if (electricity[minn2]==0 && minn2!=minn1)
if (distance[minn1][minn2]<minuzaklik)
{
minuzaklik=distance[minn1][minn2];
*pn1=minn1;
*pn2=minn2;
}
}
}
void yap()
{
double totalcost=0.0;
int turn=0;
int electricity[50]={0,};
electricity[0]=1;
while(turn++<numofcity-1)
{
int n1,n2;
findpair(electricity,&n1,&n2);
fprintf(outputf,"%d-->%d : %f\n",n1,n2,getdistance(n1,n2));
totalcost+=getdistance(n1,n2);
electricity[n1]=1;
electricity[n2]=1;
}
fprintf(outputf,"Total Cost : %f\nCity Map : \n",totalcost);
}
int main()
{
oku();
init();
yap();
ciz();
fclose(inputf);
fclose(outputf);
system("PAUSE");
return 0;
}