返回信息流无聊写了一个“坐公交看奥运”问题中，任意两个地铁站之间的选路策略，对复杂的情况，特意用了大量的If嵌套，在此拿代码来灌水一下。顺便抱怨一下Mathematica糟糕的缩进功能……
rail=Table[{\[Infinity],{}},{i,1,39},{j,1,39}];
For[i=1,i<23,i++,
rail[[i,i+1,1]]=rail[[i+1,i,1]]=2.5;
rail[[i,i,1]]=0
];
For[i=24,i<39,i++,
rail[[i,i+1,1]]=rail[[i+1,i,1]]=2.5;
rail[[i,i,1]]=0
];
rail[[26,27,1]]=rail[[27,26,1]]=rail[[32,33,1]]=rail[[33,32,1]]=\[Infinity];
rail[[26,12,1]]=rail[[12,26,1]]=rail[[12,27,1]]=rail[[27,12,1]]=rail[[32,18,1]]=rail[[18,32,1]]=rail[[18,33,1]]=rail[[33,18,1]]=rail[[39,24,1]]=rail[[24,39,1]]=2.5;
length=Table[rail[[i,j,1]],{i,1,39},{j,1,39}];
nn=39;
path=Table[{0},{i,1,nn},{j,1,nn}];
For[i=1,i<nn,i++,
For[j=i+1,j<=nn,j++,
If[length[[i,j]]!=\[Infinity],
length[[j,i]]=length[[i,j]];
path[[i,j]]={i,j};path[[j,i]]={j,i};
]
]
]
For[i=1,i<=nn,i++,
For[j=1,j<=nn,j++,
For[k=1,k<=nn,k++,
If[length[[j,i]]+length[[i,k]]<length[[j,k]],
length[[j,k]]=length[[k,j]]=length[[j,i]]+length[[i,k]];
path[[j,k]]=path[[j,i]];
AppendTo[path[[j,k]],Flatten[path[[i,k]]]];
path[[j,k]]=DeleteDuplicates[Flatten[path[[j,k]]]];
path[[k,j]]=Reverse[path[[j,k]]];
]
]
]
]
length[[12,33]]=length[[33,12]]=length[[18,26]]=length[[26,18]]=20;
length[[12,34]]=length[[34,12]]=length[[18,25]]=length[[25,18]]=22.5;
path[[12,33]]={12,27,28,29,30,31,32,18,33};
path[[33,12]]=Reverse[path[[12,33]]];
path[[18,26]]={18,32,31,30,29,28,27,12,26};
path[[26,18]]=Reverse[path[[18,26]]];
path[[12,34]]={12,26,25,24,39,38,37,36,35,34};
path[[34,12]]=Reverse[path[[12,34]]];
path[[18,25]]={18,33,34,35,36,37,38,39,24,25};
path[[25,18]]=Reverse[path[[18,25]]];
For[i=1,i<=39,i++,
For[j=1,j<=39,j++,
rail[[i,j,1]]=length[[i,j]]
]
];
For[i=1,i<=39,i++,
For[j=1,j<=39,j++,
If[j==i,Continue[]];
loc12=Position[path[[i,j]],12];
loc18=Position[path[[i,j]],18];
rail[[i,j,2]]=
If[loc12!={} && loc18=={},
If[loc12[[1,1]]==1,If[path[[i,j,2]]==11 || path[[i,j,2]]==13,{1},{2}],
If[loc12[[1,1]]==Length[path[[i,j]]],If[path[[i,j,-2]]==11 || path[[i,j,-2]]==13,{1},{2}],
If[path[[i,j,loc12[[1,1]]-1]]*path[[i,j,loc12[[1,1]]+1]]==11*13,{1},
If[path[[i,j,loc12[[1,1]]-1]]*path[[i,j,loc12[[1,1]]+1]]==26*27,{2},
If[path[[i,j,loc12[[1,1]]-1]]==11 ||path[[i,j,loc12[[1,1]]-1]]==13,{1,{12},2},{2,{12},1}
]
]
]
]
],
If[loc12=={} && loc18!={},
If[loc18[[1,1]]==1,If[path[[i,j,2]]==17 || path[[i,j,2]]==19,{1},{2}],
If[loc18[[1,1]]==Length[path[[i,j]]],If[(path[[i,j,-2]]==17) || (path[[i,j,-2]]==19),{1},{2}],
If[path[[i,j,loc18[[1,1]]-1]]*path[[i,j,loc18[[1,1]]+1]]==17*19,{1},
If[path[[i,j,loc18[[1,1]]-1]]*path[[i,j,loc18[[1,1]]+1]]==32*33,{2},
If[path[[i,j,loc18[[1,1]]-1]]==17 ||path[[i,j,loc18[[1,1]]-1]]==19,{1,{18},2},{2,{18},1}
]
]
]
]
],
If[loc12=={} ,
If[path[[i,j,1]]<=23,{1},{2}],
If[loc12[[1,1]]<loc18[[1,1]],
If[path[[i,j,loc12[[1,1]]+1]]==27,{2},
If[loc18[[1,1]]!=Length[path[[i,j]]]&&path[[i,j,loc18[[1,1]]+1]]==33,{1,{18},2},{1}
]
],
If[path[[i,j,loc18[[1,1]]+1]]==32,{2},
If[loc12[[1,1]]!=Length[path[[i,j]]]&&path[[i,j,loc12[[1,1]]+1]]==26,{1,{12},2},{1}
]
]
]
]
]
]
]
];
For[i=1,i<=39,i++,
For[j=1,j<=39,j++,
If[i==j,Continue[]];
If[rail[[i,j,2]]!={1} && rail[[i,j,2]]!={2},rail[[i,j,1]]+=4]
]
];
这是一条镜像帖。来源：北邮人论坛 / math-model / #6558同步于 2010/9/2
该镜像源已超过 30 天没有更新，可能在源站已被删除。
MathModel机器人发帖
疯狂的If嵌套——“坐公交看奥运”地铁程序片段
wangfuwei
2010/9/2镜像同步11 回复
订阅后，新回复会通过你的通知中心匿名送达。
9 条回复
纯公交车的算法代码，包含直达、转乘一次、转乘两次
Remove["`*"]
ori=ImportString[Import["D:\\data.txt"],"Table"];
data=Table[{},{i,1,1040}];
For[i=1,i<= 1039,i+=2,
data[[i]]=ori[[2*i+1]];
If[ori[[2*i+2]]=={} && ori[[2*i+1,1]]!=ori[[2*i+1,-1]],
data[[i+1]]=Reverse[data[[i]]],
data[[i+1]]=ori[[2*i+2]]
];
]
money=Table[0,{i,1,1040}];
For[i=1,i<=520,i++,
money[[2*i-1]]=money[[2*i]]=ori[[4*i-2]]
];
start=87;end=3676;
ans0t=\[Infinity];ans1t=\[Infinity];ans2t=\[Infinity];
ans0c=\[Infinity];ans1c=\[Infinity];ans2c=\[Infinity];
pans0t={};pans1t={};pans2t={};
pans0c={};pans1c={};pans2c={};
time[start_,end_,path_]:=Abs[Position[data[[path]],end][[1,1]]-Position[data[[path]],start][[1,1]]];
cost[start_,end_,path_]:=Module[{ans=money[[path,1]],len},
If[ans==0,
len=time[start,end,path];
ans=If[len<=20,1,
If[len<=40,2,3]
]
];
ans];
Matrix=Table[{},{i,1,3957},{j,1,3957}];
For[i=1,i<=1040,i++,
For[j=1;k=Length[data[[i]]],j<k,j++,
For[l=j+1,l<=k,l++,
AppendTo[Matrix[[data[[i,j]],data[[i,l]]]],i]
]
]
];
direct[]=Module[
{i,tar=Matrix[[start,end]],len=Length[Matrix[[start,end]]],t,c,temp},
ans0t=ans0c=\[Infinity];
pans0t=pans0c={};
For[i=1,i<=len,i++,
t=3*time[start,end,tar[[i]]];
c=cost[start,end,tar[[i]]];
temp=Mod[tar[[i]],2]+Quotient[tar[[i]],2];
If[t<ans0t,
ans0t=t;
pans0t={temp},
If[t==ans0t,
AppendTo[pans0t,temp]
]
];
If[c<ans0c,
ans0c=c;
pans0c={temp},
If[c==ans0c,
AppendTo[pans0c,temp]
]
]
]
];
once[]=Module[
{pstart={},pend={},ans={},sta=0,mstart,mend,i,j,m,mm,temp,temp2,t,c},
ans1t=ans1c=\[Infinity];
pans1t=pans1c={};
For[i=1,i<=1040,i++,
If[(temp=Position[data[[i]],start])!={}&& temp[[1,1]]!=Length[data[[i]]],AppendTo[pstart,{i,Drop[data[[i]],temp[[1,1]]]}],
If[(temp=Position[data[[i]],end])!={} && temp[[1,1]]!=1,AppendTo[pend,{i,Take[data[[i]],temp[[1,1]]-1]}]
]
]
];
mstart=Length[pstart];mend=Length[pend];
For[i=1,i<=mstart,i++,
For[j=1,j<=mend,j++,
If[(temp=Intersection[pstart[[i,2]],pend[[j,2]]])!={} ,
sta+=Length[temp];
For[m=1;mm=Length[temp],m<=mm,m++,
temp2={{Mod[pstart[[i,1]],2]+Quotient[pstart[[i,1]],2],{temp[[m]]},Mod[pend[[j,1]],2]+Quotient[pend[[j,1]],2]}};
If[temp2[[1,1]]==temp2[[1,3]],Continue[]];
t=3*(time[start,temp[[m]],pstart[[i,1]]]+time[temp[[m]],end,pend[[j,1]]])+5;
c=cost[start,temp[[m]],pstart[[i,1]]]+cost[temp[[m]],end,pend[[j,1]]];
If[t<ans1t,
ans1t=t;
pans1t=temp2,
If[t==ans1t,
AppendTo[pans1t,temp2];
]
];
If[c<ans1c,
ans1c=c;
pans1c=temp2,
If[c==ans1c,
AppendTo[pans1c,temp2];
]
];
]
]
]
]
];
ans1t
pans1t
ans1c
pans1c
twice[]=Module[{i,ii,j,jj,m,mm,n,nn,k,kk,temp,temp2,t,c,pstart={},pend={}},
ans2t=ans2c=\[Infinity];
pans2t=pans2c={};
(*build[];*)
For[i=1,i<=1040,i++,
If[(temp=Position[data[[i]],start])!={}&& temp[[1,1]]!=Length[data[[i]]],AppendTo[pstart,{i,Drop[data[[i]],temp[[1,1]]]}],
If[(temp=Position[data[[i]],end])!={} && temp[[1,1]]!=1,AppendTo[pend,{i,Take[data[[i]],temp[[1,1]]-1]}]
]
]
];
For[i=1;ii=Length[pstart],i<=ii,i++,
For[j=1;jj=Length[pstart[[i,2]]],j<=jj,j++,
For[m=1;mm=Length[pend],m<=mm,m++,
For[n=1;nn=Length[pend[[m,2]]],n<=nn,n++,
If[(temp=Matrix[[pstart[[i,2,j]],pend[[m,2,n]]]])!={},
For[k=1;kk=Length[temp],k<=kk,k++,
temp2={Mod[pstart[[i,1]],2]+Quotient[pstart[[i,1]],2],{pstart[[i,2,j]]},Mod[temp[[k]],2]+Quotient[temp[[k]],2],{pend[[m,2,n]]},Mod[pend[[m,1]],2]+Quotient[pend[[m,1]],2]};
(*If[(temp2[[1]]-temp2[[3]])*(temp2[[3]]-temp2[[5]])*(temp2[[1]]-temp2[[5]])==0,Continue[]];*)
t=3*(time[start,pstart[[i,2,j]],pstart[[i,1]]]+time[pstart[[i,2,j]],pend[[m,2,n]],temp[[k]]]+time[pend[[m,2,n]],end,pend[[m,1]]])+10;
c=cost[start,pstart[[i,2,j]],pstart[[i,1]]]+cost[pstart[[i,2,j]],pend[[m,2,n]],temp[[k]]]+cost[pend[[m,2,n]],end,pend[[m,1]]];
If[t<ans2t,
ans2t=t;
pans2t={temp2},
If[t==ans1t,
AppendTo[pans2t,temp2];
]
];
If[c<ans2c,
ans2c=c;
pans2c={temp2},
If[c==ans2c,
AppendTo[pans2c,temp2]
]
]
]
]
]
]
]
]
];
ans2t
pans2t
ans2c
pans2c
出结果了。。貌似两次不能完全实现，比如说纯公交两次换乘及以内从2330这个点到达不了
{45, 46, 77, 111, 147, 266, 499, 595, 724, 770, 792, 867, 998, 1006, \
1083, 1084, 1087, 1088, 1201, 1202, 1389, 1395, 1463, 1497, 1498, \
1499, 1550, 1666, 1667, 1698, 1805, 1869, 1870, 1950, 1951, 1952, \
2005, 2006, 2014, 2034, 2055, 2059, 2075, 2154, 2194, 2240, 2252, \
2328, 2350, 2352, 2368, 2376, 2399, 2413, 2414, 2496, 2497, 2548, \
2625, 2719, 2726, 2736, 2787, 2879, 2886, 2890, 2957, 3012, 3014, \
3018, 3020, 3055, 3075, 3084, 3096, 3129, 3226, 3289, 3292, 3327, \
3331, 3350, 3396, 3418, 3442, 3499, 3510, 3521, 3582, 3640, 3692, \
3745, 3762, 3764, 3785, 3792, 3812, 3861, 3867, 3924, 3955}
感觉这道题，如果不考虑复杂度（当然也是计算机允许的范围内），有了可直达和换乘一次的数据，后面都可以类推出来。
比如换乘两次的处理，就是打表处理出所有车站之间两两直达的路线数据，再在起点和终点向其所处路线的下游所有车展扩展，找这些扩展出来的两个集合之间的元素在上述“可直达表”中的数据，非空则找到一条转乘两次的路线；
转乘三次，类似的可以打表记录所有车站两两转乘一次可达的路线数据，再按照上述方法寻找这样的“过渡线路”即可；
所以有零转乘，就可以依次推得两次转乘、四次转乘、……2n次转乘的路线；技术次转乘同理。
这种算法的运算主要集中在构建公交站两两k次可达的数据矩阵上面，查询都基本是瞬间完成的。考虑到实际应用当中的公交线路查询系统基于已处理好的数据库，上述算法应该还是有一定可行性的……如果真的存在比较偏僻而不得不多次转乘的路线的话