数学建模-无向图最短路径

《数学建模-无向图最短路径》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、参赛队编号：244赛题类型代码：B无向图最优路径摘要：在实际生活中，我们经常会遇到“最优路径”问题，例如，城市之间的最短线路，或者城市之间最节省的交通费用等问题都属于该类问题。同样，在自然界也存在着“最优路径”。在复杂多变的蚁巢中，蚂蚁总是能以最快、最高效的方式游历在各个储藏间，今天，蚁后让小蚁同学按照自己特定的要求寻找食物，针对蚁后的要求，我们采用了大量科学分析方法，并进行了反复验证，我们建立如下的模型：首先对问题进行分析，对约束条件逐一列举、分析实质，必须经过N7、N12两个点，必须经过两条直线，实质是经过四个点N2、N4、N13、N14，但这四个点又与前边两个点有所不同，N

2、2和N4要相邻，N13和N14要相邻，必须经过起始和终止点（针对此处的歧义，在假设中解决）深入分析可知，若最多经过9个点是无法完成的，因此求次优解。其次遍历所有路径找到符合约束条件的，遍历时使用穷举法，走遍每一条可以走的路，在过走点数超过限制的最多点数或者已经走到了终点，是，则停止，判断这条是否满足约束条件，满足则记录这条路的信息，不满足什么都不做；否，则继续向前走。最后可以找到所有经过不超过限制点数、满足约束条件的路径。再计算每一条符合要求的费用（事实上可以集成到上一步中，但为了模块独立化，利用分而治之思想，在这里将其分开），按照费用排序，在所走点数的基础上，在费用上再做分析，

3、选出最优路径。最后对模型进行分析与评价，以及改进与退关，模型的适用性较强，只要对数据稍加改动就可以成为求有向图最佳路径的模型。关键字：无向图最优路径，C语言，图论，算法目录一、问题重述1二、模型假设与符号说明22.1模型假设22.2符号说明2三、问题分析23.1整体分析23.2约束条件分析23.3可行性分析2四、模型建立与求解34.1模型准备34.2模型建立与求解34.2.1确定所有路线表达式34.2.2对路径的筛选44.2.3费用分析54.2.4算法设计64.2.5模型求解74.3对模型的检验7五、模型评价95.1模型优缺点95.1.1模型优点105.1.2模型缺点105.2模

4、型改进10参考文献10附录11无向图最优路径模型一、问题重述最强大脑中的收官蜂巢迷宫变态级挑战，相信大家都叹为观止！最强大脑收官战打响后，收视率节节攀升，就连蚁后也不时出题难为一下她的子民们。在动物世界中，称得上活地图的，除了蜜蜂，蚂蚁当仁不让。在复杂多变的蚁巢中，蚂蚁总是能以最快、最高效的方式游历在各个储藏间（存储食物）。今天，她看完最新一期节目，又发布了一项新任务：小蚁同学，我需要玉米库的玉米，再要配点水果，去帮我找来吧。小蚁正准备出发，蚁后又说：哎呀，回来，我还没说完呢，还有若干要求如下：1.小蚁同学，你需要尽可能以最少的花费拿到食物（附件图中路线上的数值表示每两个储物间的

5、花费）；2.小蚁同学，你最多只能经过9个储藏间拿到食物（包含起止两个节点，多次通过同一节点按重复次数计算）；3.小蚁同学，你必须经过玉米间，水果间（附件图中标绿色节点）；4.别忘了，食蚁兽也在路上活动呢，一旦与食蚁兽相遇，性命危矣！不过小蚁微信群公告已经公布了敌人信息（附件图中标红色路段）；5.最后，千万别忘了，还有两段路是必须经过的，那里有我准备的神秘礼物等着你呢(附件图中标绿色路段)。这下小蚁犯难了，这和它们平时找食物的集体活动规则不一样嘛,看来这次需要单独行动了。要怎么选路呢？小蚁经过一番苦思冥想，稿纸堆了一摞，啊，终于找到了！亲爱的同学们，你们能否也设计一种通用的路径搜索

6、算法，来应对各种搜索限制条件，找到一条最优路径，顺利完成蚁后布置的任务呢？注：1、蚁巢，有若干个储藏间（附件图中圆圈表示），储藏间之间有诸多路可以到达(各储藏间拓扑图见附件);2、节点本身通行无花费；3、该图为无向图，可以正反两方向通行，两方向都会计费，并且花费相同；4、起止节点分别为附件图中S点和E点。5、最优路径：即满足限制条件的路径。图116二、模型假设与符号说明2.1模型假设1.因为题目中并未明确给出是否是从起始点开始到达终止点，即从s到e，为防止歧义、方便计算，假设每条路径都是从起点到终点；2.下文中说到的点或点数均代表存储室或存储室数量；3.通过图1各路段关系，可以假

7、设，为得到最优路径，不会再从N1、N2、N3走回起点。2.2符号说明符号含义N最多经过的点的个数xn经过的第n个点Pj[i]第j个集合Pj个点中的第i的数值，即将要走向的下一个点Pj[i]Pj第j个点所有与其相邻的点的集合APCk和第k个点相邻的点的总数ik走过的第k个点集合元素的下标，从0到APCi-1Fk走第k条路所需要的总费用fij从编号为i的点到编号为j的点的费用，即表3i行j列对应的值表1三、问题分析3.1整体分析题目的总体思路是在各种约束条件下求出一条从起点到终点的最