Главная страница
Исходный код программы на С++. Решение задачи коммивояжера методом ветвей и границ.
Находится только одна ветвь, в случае если ветвей несколько.
Программа консольная, программная платформа Windows XP SP3,
компилируется в "Командной строке" утилитой bcc32,
входящей в состав фреймворка Borland C++ Builder 6.
В командной строке вводятся размер матрицы, элементы матрицы,
выводятся промежуточные данные, стоимость проезда по кратчайшему пути,
список дуг кратчайшего пути.
#include <stdio.h>
#include <iostream.h>
int uz [50][50];
int vich[50][50];
int mstr[50];
int msto[50];
int kp[50];
int msh[50][50];
int mshstr[50][50];
int mshsto[50][50];
int d[50][2],c[50];
int g[50][2];
int k[50][2];
int m[50][2];
int a,b,e,f;
int h;
int n;
int sp=0;
int r;
int i, j;
main()
{
//Vvod razmera matrici
cin>>r;
//prisv diag elm znach -444
for(i=0;i<=(r-1);i++)
{
uz[i][i]=-444;
}
//vvod elem matrizi
for(i=0;i<=(r-1);i++)
{
for(j=0;j<=(r-1);j++)
{
if(uz[i][j]!=-444)scanf("%d",&uz[i][j]);
}
}
//viv ish dan
for(i=0;i<=(r-1);i++)
{printf("\n");
for(j=0;j<=(r-1);j++)
{
printf("\t%d",uz[i][j]);
}
}
//prisv perv znach matr g[][]
for(j=0;j<=(r-1);j++)
{
g[j][0]=j+1;
g[j][1]=j+1;
}
//pech perv znach g
for(i=0;i<=(r-1);i++)
{
printf("\n");
for(j=0;j<=1;j++)
{
printf("\t%d",g[i][j]);
}
}
//prisv znach matr vich
for(i=0;i<=(r-1);i++)
{
for(j=0;j<=(r-1);j++)
{
vich[i][j]=uz[i][j];
}
}
//prisv perv znach 0 matr m[][]
for(j=0;j<=(r-2);j++)
{
m[j][0]=0;
m[j][1]=0;
}
//nachalo zikla shsaga zadachi
for(h=1;h<=5;h++)
{
printf("\n%dШаг",h);
//vichisl min elem strok
for(i=0;i<=(r-h);i++)
{
for(j=0;j<=(r-h);j++)
{
if(vich[i][j]!=-444){mstr[i]=vich[i][j];break;}
}
}
for(i=0;i<=(r-h);i++)
{
for(j=0;j<=(r-h);j++)
{
if(vich[i][j]!=-444)
{
if(mstr[i]>vich[i][j])mstr[i]=vich[i][j];
}
}
}
//pech min elem strok
for(i=0;i<=(r-h);i++)
{
printf("\n%d",mstr[i]);
}
//vichit min elem strok
for(i=0;i<=(r-h);i++)
{
for(j=0;j<=(r-h);j++)
{
if(vich[i][j]!=-444)vich[i][j]=vich[i][j]-mstr[i];
}
}
//viv posle vich min elem strok
for(i=0;i<=(r-h);i++)
{printf("\n");
for(j=0;j<=(r-h);j++)
{
printf("\t%d",vich[i][j]);
}
}
//vichisl min elem stolbc
for(j=0;j<=(r-h);j++)
{
for(i=0;i<=(r-h);i++)
{
if(vich[i][j]!=-444){msto[j]=vich[i][j];break;}
}
}
for(j=0;j<=(r-h);j++)
{
for(i=0;i<=(r-h);i++)
{
if(vich[i][j]!=-444)
{
if(msto[j]>vich[i][j])msto[j]=vich[i][j];
}
}
}
//pech min el sto
for(j=0;j<=(r-h);j++)
{
printf("\n%d",msto[j]);
}
//vichit min elem stolb
for(j=0;j<=(r-h);j++)
{
for(i=0;i<=(r-h);i++)
{
if(vich[i][j]!=-444)vich[i][j]=vich[i][j]-msto[j];
}
}
//vivod posle vich min el stol
for(i=0;i<=(r-h);i++)
{printf("\n");
for(j=0;j<=(r-h);j++)
{
printf("\t%d",vich[i][j]);
}
}
//zapom sum konst priv na shage
for(i=0;i<=(r-h);i++)
{
kp[h-1]=kp[h-1]+mstr[i]+msto[i];
}
//pech sum konst priv
printf("\n%d",kp[h-1]);
//perech na shage poslednem
if(h==r-1)goto e;
//prisv msh -111
for(i=0;i<=(r-h);i++)
{
for(j=0;j<=(r-h);j++)
{
msh[i][j]=-111;
}
}
//vich min shtr u nuley v stolb i strokah
for(i=0;i<=(r-h);i++)
{
for(j=0;j<=(r-h);j++)
{
if(vich[i][j]==0)
{
//vich shtr v str
for(a=0;a<=(r-h);a++)
{
if(vich[i][a]!=-444)
{
if(a!=j)
{
mshstr[i][j]=vich[i][a];goto A;
}
}
}
A:
for(a=0;a<=(r-h);a++)
{
if(vich[i][a]!=-444)
{
if(a!=j)
{
if(mshstr[i][j]>vich[i][a])mshstr[i][j]=vich[i][a];
}
}
}
//vich shtr v stolb u nuley
for(b=0;b<=(r-h);b++)
{
if(vich[b][j]!=-444)
{
if(b!=i)
{
mshsto[i][j]=vich[b][j];goto B;
}
}
}
B:
for(b=0;b<=(r-h);b++)
{
if(vich[b][j]!=-444)
{
if(b!=i)
{
if(mshsto[i][j]>vich[b][j])mshsto[i][j]=vich[b][j];
}
}
}
//vich shtrafa
msh[i][j]=mshstr[i][j]+mshsto[i][j];
}
}
}
//vivod strafov na shage
for(i=0;i<=(r-h);i++)
{printf("\n");
for(j=0;j<=(r-h);j++)
{
printf("\t%d",msh[i][j]);
}
}
//nahoz perv strafa maks
for(i=0;i<=(r-h);i++)
{
for(j=0;j<=(r-h);j++)
{
if(msh[i][j]!=-111)
{
c[h-1]=msh[i][j];d[h-1][0]=i;d[h-1][1]=j;goto C;
}
}
}
C:
for(i=0;i<=(r-h);i++)
{
for(j=0;j<=(r-h);j++)
{
if(msh[i][j]!=111)
{
if(msh[i][j]>c[h-1])
{
c[h-1]=msh[i][j];d[h-1][0]=i;d[h-1][1]=j;
}
}
}
}
//pech max shtraf na shage, n stroki i stolbza virez na shage
cout<<"\n"<<c[h-1]<<"\t"<<d[h-1][0]<<"\t"<<d[h-1][1];
//prisv matr k znach na shage
k[h-1][0]=g[d[h-1][0]][0];
k[h-1][1]=g[d[h-1][1]][1];
//uresanie stroki matrizi
for(i=0;i<=(r-h-1);i++)
{
if(i==d[h-1][0])
{
for(e=i;e<=(r-h-1);e++)
{
for(f=0;f<=(r-h);f++)
{
vich[e][f]=vich[e+1][f];
}
}
}
}
//pech posle urez stroki
for(i=0;i<=(r-h-1);i++)
{printf("\n");
for(j=0;j<=(r-h);j++)
{
printf("\t%d",vich[i][j]);
}
}
//uresanie stolbza matrizi
for(j=0;j<=(r-h-1);j++)
{
if(j==d[h-1][1])
{
for(e=j;e<=(r-h-1);e++)
{
for(f=0;f<=(r-h-1);f++)
{
vich[f][e]=vich[f][e+1];
}
}
}
}
//pech posle urez stolbza
for(i=0;i<=(r-h-1);i++)
{printf("\n");
for(j=0;j<=(r-h-1);j++)
{
printf("\t%d",vich[i][j]);
}
}
//prisv matr g nomerov strok i stolbzov
for(i=d[h-1][0];i<=(r-h-1);i++)
g[i][0]=g[i+1][0];
for(i=d[h-1][1];i<=(r-h-1);i++)
g[i][1]=g[i+1][1];
//pech tek znach g
for(i=0;i<=(r-h-1);i++)
{
printf("\n");
for(j=0;j<=1;j++)
{
printf("\t%d",g[i][j]);
}
}
//proverka est li protiv elem, esli est prisv beskonechn
for(i=0;i<=(r-h-1);i++)
{
for(j=0;j<=(r-h-1);j++)
{
if (k[h-1][0]==g[j][1]&&k[h-1][1]==g[i][0])
{
vich[i][j]=-444;printf("\n%d",vich[d[h-1][1]][d[h-1][0]]); goto D;
}
}
}
//nahoz vseh zepey(prisoed dugi v nachale)
for(i=0;i<(h-1);i++)
{
if(k[h-1][0]==k[i][1])
{
m[h-1][0]=k[i][0];m[h-1][1]=k[h-1][1];
}
}
//nahoz vseh zepey(prisoed dugi v konce)
for(i=0;i<(h-1);i++)
{
if(k[h-1][1]==k[i][0])
{
if(m[h-1][0]==0)
{
m[h-1][0]=k[h-1][0];m[h-1][1]=k[i][1];
}
else m[h-1][1]=k[i][1];
}
}
//proverka mozno prisoedinit zepi i prisoedinenie
for(i=0;i<h-1;i++)
{
if(m[i][0]!=0)
{
if(k[h-1][0]==m[i][1])
{
m[h-1][0]=m[i][0];
}
}
}
for(i=0;i<h-1;i++)
{
if(m[i][0]!=0)
{
if(k[h-1][1]==m[i][0])
{
m[h-1][1]=m[i][1];
}
}
}
//zapret zepi na shage - prisv -444
for(i=0;i<=(r-h-1);i++)
{
for(j=0;j<=(r-h-1);j++)
{
if (m[h-1][0]==g[j][1]&&m[h-1][1]==g[i][0])
{
vich[i][j]=-444;
}
}
}
D:
//pech dugi m na shage
printf("\n%d",m[h-1][0]);
printf("\n%d",m[h-1][1]);
}
e:
//vivod matrizi d
for(i=0;i<=(r-3);i++)
{
printf("\n");
for(j=0;j<=1;j++)
{
printf("\t%d",d[i][j]);
}
}
//prisv dvuch posl strok v mass k
int l=2;
for(i=0;i<=1;i++)
{
for(j=0;j<=1;j++)
{
if(vich[i][j]==0)
{
k[r-l][0]=g[i][0]; k[r-l][1]=g[j][1];l=l-1;
}
}
}
//rasch stoim proezda
for(i=0;i<=r-1;i++)
{
sp=sp+uz[k[i][0]-1][k[i][1]-1];
}
//vivod stoim proezda
printf("\n%d",sp);
//vivod matrizi k
for(i=0;i<=(r-1);i++)
{
printf("\n");
for(j=0;j<=1;j++)
{
printf("\t%d",k[i][j]);
}
}
}
Главная страница