2006年长安大学数学建模竞赛试题

A题：公交线路确定
某城镇有四条横向街道和五条纵向街道，为了市民出行方便，市政部门决定安排公交线路；公交站点均设在交叉处（如图），经调查在每天的6：00到21：00之间各站点总的基本出行人数如表（常住在该区的需要坐公交出行的人数，不包括其他区域出行而来的人数，乘客的来到是均匀的），在出行人群中，目的地为其相邻站点的人数为零，到其他各目的地（站点）的人数与两站点的距离的平方成反比，出行的人群当天全部回到原出发点。假定各街区的距离均为1km，可供选择的车型有20座和40座两种；现已初步设计了一套线路，共3路公交：A线：（0，3）—（0，2）—（1，2）—（2，2）—（3，2）—（4，2）—（4，1）—（4，0）；B线：（1，0）—（2，0）—（3，0）—（3，1）—（3，2）—（3，3）—（4，3）；C线：（0，0）—（0，1）—（1，1）—（2，1）—（2，2）—（2，3）—（1，3）。试给出各线路的车辆调度方案，并计算：
1 总运行费用、平均换乘次数、平均出行距离、平均等待时间、线路的非直线系数（各路的线路长度/起终点的直线距离）。
2 你设计一套更合理线路并给出调度方案，与原线路方案进行比较。

各站点出行人数表
0 1 2 3 4
0 104 250 490 802 1524
1 636 364 358 1678 946
2 1464 358 28 838 364
3 18 1086 1344 754 1210
.
市区街道分布图



B题：两字符串相似度计算
设S1和S2为两个由a、b、c、d四个字母组成的字符序列（字符串），n1、n2 分别表示S1、S2的序列长度，当n1不等于n2时（不妨设n1<n2），就需要在序列S1中插入n2－n1个空字符产生一个新的字符串S1’，使S1’和S2一样长，然后进行比较。
1 构造一个衡量S1’和S2相似程度的指标Q；
2 就本题给出的S1和S2，确定在S1中插入空格的位置，使Q最大。
3 对任意的序列S1、S2，给出一般的算法，并用本题给出的S1和S2进行验证。
附：S1=”abcddacbcbdadcabbdca”；S2=” aadaccbddcabacd”。