查看: 4413|回复: 3

[国赛经验] 公交路线最小换乘次数的路径选择算法（C代码）（请求高手指教）

[复制链接]

字体大小: 正常放大

舞情＿Dong

6 主题	7 听众	676 积分

升级 19%

TA的每日心情

	奋斗 2015-11-13 15:06

签到天数: 210 天

[LV.7]常住居民III

群组: Matlab讨论组

群组: 数学建摸协会

群组: 全国大学生数学建模竞

群组: 学术交流A

群组: 学术交流B

电梯直达

1^#

发表于 2012-8-19 18:02 |只看该作者 |倒序浏览

|招呼Ta 关注Ta

第三天了，关于交通路线的选择，用C语言写成了个样子，下面代码可以正常运行，就是路线选择的结果不是很好，结果有好多重复的，有些站点似乎选不出来，这和存放交通路线的数组a有关，我们是把公交路线的上行和下行放在二维数组的同一行的，肯定有重复，但对程序算法也有质疑，实在是惭愧，自己不才，对其它语法实在是不太了解，用的都是for，if循环嵌套，还请仁兄指教。这是2007年的全国竞赛题，网上也有各种算法（基于不同语言），我们建模培训做真题，按自己想法用C编写了下面的程序，但结果不是很好，自己对其它的语句又不是很了解，实在没辙了，真心请教各位大侠，现在在改数组，打算将同一条交通路线的上行和下行放入数组的不同行里，真心寻求帮助，请求仁兄指导，谢谢！

编写的C代码如下，由于数组a的数据带大，粘贴不过来（520条数据）
本人实在是很惭愧，对C其他语法语句不是很熟悉，用的全是for，if循环嵌套，还请仁兄耐心查看

uint value1,value2;
uint a[200],a1[200];//定义一个数组
uint b[200],b1[200];
uint c[200];

void routes()
{

uint i,j,j1,j2,j3,j4,c1,c2,k=0,k1=0,k2=0;
uint linshi1,linshi2,e=0,f=0;
uint q1,q2,q3,t;
uint luxian1=0;
uint m=0;
uint n=0;
for(i=0;i<520;i++)
{
for(j=0;j<200;j++)
{
if(y[i][j]==value1)//寻找包含起点的所有路线,将路线值放入数组a
{
a[m]=i;
//a1[m]=j;
m++;
}
if(y[i][j]==value2)//寻找包含终点的所有路线，将其放入数组b
{
b[n]=i;
//b1[n]=j;
n++;
}
}
}
printf("所有经过起点的路线a为：");
for(i=0;i<m;i++)
{
printf("%d  ",a[i]);
}
printf("\n");
printf("所有经过终点的路线b为：");
for(i=0;i<n;i++)
{
printf("%d  ",b[i]);
}
printf("\n");

for(i=0;i<m;i++)//直达路线的寻找
{
for(j=0;j<n;j++)
{
if(a[i]==b[j])
{
c[k]=a[i];
k++;
}
}
}
printf("您查询的站点的直达路线有：");
for(i=0;i<k;i++)
{
if(c[i]!=0)
printf("%d  ",c[i]);
}
printf("\n");//若没有直达路线这数组c为零，接着下面转乘一次路线的寻找

if(k==0)
{
for(c1=0;c1<m;c1++)//转乘一次路线的寻找
{
for(j=0;j<200;j++)
{
linshi1=a[c1];
k1=y[linshi1][j];//取出a中每一条路线上每一个站点，接着与b中站点进行比较，查询公共点。
for(c2=0;c2<n;c2++)
{
for(j=0;j<200;j++)//该算法不是很好，j小于200时还得往后遍历。
{
linshi2=b[c2];
k2=y[linshi2][j];//将b中的站点取出与k1进行比较判断。
if(k1==k2/*||k1==k2+1||k1==k2-1*/&&(k1!=0)&&(linshi1!=0)&&(linshi2!=0))//寻找数组a,b中的站点，有相同的及为转乘一次的转乘点，并输出。
{
printf("您可以转乘一次，起始路线为:%d ，中间转站点为：%d ,%d终点路线为：%d\n",linshi1,k1,k2,linshi2);
luxian1++;
}
}
   }
}
}
}

if(luxian1==0&&k==0)
{
for(c1=0;c1<m;c1++)//转乘两次路线的寻找
{
for(j=0;j<200;j++)
{
linshi1=a[c1];
k1=y[linshi1][j];//取出a中每一条路线上每一个站点，接着与b中站点进行比较，查询公共点。
for(c2=0;c2<n;c2++)
{
for(j=0;j<200;j++)//该算法不是很好，j小于200时还得往后遍历。
{
linshi2=b[c2];
k2=y[linshi2][j];//将b中的站点取出与k1进行比较判断。
for(i=0;i<520;i++)
{
for(j=0;j<200;j++)
{
if(k1==y[i][j]&&k1!=0)
{
f=i;
e=j;
for(j=0;j<200;j++)
{
if(k2==y[i][j]&&k2!=0&&(e<j)&&(linshi1!=0)&&(linshi2!=0))
{
printf("您需转乘两次，起始路线为：%d ,第一个转车站点为：%d,中间路线为：%d,第二个转车站点为：%d,终点路线为：%d\n",linshi1,y[i][e],f,y[i][j],linshi2);
//q1=abs(e-a1[c1]);//计算每条路线上经过的站点数
//q2=abs(j-e);
//q3=abs(b1[c2]-j);
//t=3*(q1+q2+q3)+10;
//printf("该路线总共计时为：%d 分钟\n",t);
}
}
}
}
}
}
}
}

}
}

}

void main()
{
printf("请输入起始站点和终止站点（中间空格间开）: \n");
scanf("%d %d",&value1,&value2);
routes();

}

zan

算法, 公交路线选择, C语言