《试卷合理均衡分配问题最佳乘车路线问题》由会员分享，可在线阅读，更多相关《试卷合理均衡分配问题最佳乘车路线问题（9页珍藏版）》请在金锄头文库上搜索。
1、第一部分 训练任务简介任务一：考试公平性是评价考试质量的重要方面，也是一个受到广泛关注的问题。现代教育虽然趋向现代化，许多教学可以通过计算机实现，但也有许多的问题是计算机无法解决的，由绝大部分的考试是离不开评委亲自的审查，因为许多的学术问题上，计算机是不会知道的，所以工作量只可以是人为的评改。体现最主要的，就是试卷的合理均匀的分配。在大学生数学建模竞赛的评卷工作中，M 个评委（M 个评委来自不同的学校）要完成 N 份试卷的打分，竞赛试卷来自 K 个学校，第 i 个学校有竞赛试卷 1 份，为节省人力，每份试卷只要由其中 p(pMKB,表示有从A 站的下一站就是B 站的公交线路,但没有从B 站的下
2、一站是A站的公交线路。AB 表示即有从A 站的下一站是B 站的公交线路又有从B 站的下一站是A 站的公交线路。模型如下定义结点之间的距离，设代表A 站的图上的结点为a,代表B 站的图上的结点为b。设A 站的下一站就是B 站。出发点为S 站,代表S 站的图上的结点为s，目的地为D 站，代表D 站的图上的结点为d.求解最少换乘的乘车路线时求a 到b 的连线的长度：设从出发站到A 站的最短乘车路线上，到A 站时乘坐的公交线路集合为Ca, 设从出发站经A 站到B 站的最短乘车路线上，到B 站时乘坐的公交线路集合为Cb, A 站下一站就是B 站的公交线路的集合为Ca-b,如果Ca与Ca-b 的集合非空，
3、则Cb 等于Ca 与Ca-b 的交集，a 到b 的连线的距离为0，如果Ca 与Ca-b 的集合为空，则Cb 等于Ca-b，a 到b 的连线的距离为1。出发点S 站的Cs 等于空集。如图1图1图中结点为公交站，连线上的数字代表公交线路Ca=1,2,Ca-b=1,4,因为Ca 交Ca-b 非空，所Cb=Ca 交Ca-b=1 a 到b 的连线的长度为0。Cb-c=3,Cb 交Cb-c 为空集，所以Cb 等于Cb-c，b 到c 的连线的长度为1。要注意的是在求解最少换乘的乘车路线时求a 到b 的连线的长度是在求最短路径时动态确定的。而求解经过最少站点的乘车路线时求a 到b 的连线的长度是恒定为1 的求
4、解经过最少站点的乘车路线时求a 到b 的连线的长度：如果A 站的下一站就是B 站的公交线路存在，a 到b 的连线的长度就为1。一旦定义了结点之间的距离，就可以采用Dijkstra 算法计算出发站点到目的站点的最佳乘车路线，也就是结点s 到结点d 的最短路径。Dijkstra 算法在各本图论或离散数学的书上都有介绍，这里就不做介绍了。五、模型的计算机实现源代码（附于文章之后，从略）测试结果测试数据(data.txt):A B C D E F1 2 3 41 A B D F2 A B E3 A C E4 A E F出发站点：A目的站点: F最少换乘（最经济）的乘车路线：A-B-D-F经过最少站点（最短距离，最省时间）的乘车路线：A-E-F六、模型的改进求解最少换乘的乘车路线由于结点过多，可能导致计算效率下降，可以如下改进：设图的结点代表公交线路，代表X 路公交线路的图上的结点为x,代表Y 路公交线
