请选择 进入手机版 | 继续访问电脑版
4258 5

数学建模图论算法部分的一些总结 [推广有奖]

  • 0关注
  • 0粉丝

大专生

10%

还不是VIP/贵宾

-

威望
0
论坛币
7 个
通用积分
0.0012
学术水平
0 点
热心指数
0 点
信用等级
0 点
经验
1873 点
帖子
15
精华
0
在线时间
34 小时
注册时间
2015-8-23
最后登录
2018-8-8

+2 论坛币
k人 参与回答

经管之家送您一份

应届毕业生专属福利!

求职就业群
赵安豆老师微信:zhaoandou666

经管之家联合CDA

送您一个全额奖学金名额~ !

感谢您参与论坛问题回答

经管之家送您两个论坛币!

+2 论坛币

最小生成树:这算是最简单的图论算法之一了吧,常用的有PrimKruskal算法,对于Prim算法,它 和求最短路径的O(N^2)算法Dijkstra是有相通之处 的。PrimKruskal算法的时间效率相差不多,个 人感觉Prim算法容易理解,可以视作涨水的模型来 看,的却显得巧妙异常。(以USACO 3.1 Agri-Net 为例) 这道题目是一个标准的最小生成树,不用任何转化 或者优化,Prim算法思想就是不断找点,更新,再找点….算法实现代码如下:

fori:=1 to n-1 do begin min:=maxlongint; for j:=1 to n do if (f[j]0) then beginmin:=f[j]; k:=j; end; zong:=zong+min; f[k]:=0; for j:=1 to n do iff[j]>map[k,j] then f[j]:=map[k,j]; end; 事实上,图论算法的代码都是相当死的,若不能理 解,你完全可以将它记下来,做过更难的图论算法 后你才会发现,图论算法的精髓在于建图,而不是 在于算法。

最短路径:最短路径是使用极为频繁的一种图论模 型,其解题主要实现方式是松弛操作,即是先将两 点距离视为极大值,然后用其它点作中转进行优 化,常见的算法有SPFA算法,Dijkstra算法以及 Floyed算法,前两者的时间复杂度为O(N^2) Floyed算法为O(N^3),为什么要把一个N^3的算法 放在这里呢,因为其代码极为简洁,如果数据规模 允许的情况下通常采用Floyed算法,事实上, SPFA算法和Dijkstra算法是求单点的距离,Floyed 算法求的是任意两点距离,所以说Floyed的效率与 这两者相比哪个更好还有待讨论啊。 因为spfa可以处理权值为负的情况,所以建议使用 spfa算法,spfa算法的模块与宽搜(bfs)的模块 大致相似,也较容易理解: l:=0;r:=1;line[r]:=a;h[a]:=true; repeatinc(l); h[line[l]]:=false; t:=line[l]; for i:=1 to n do begin if(i<>t)and(连接) thenbegin if 松弛 thenbegin 松弛 if h=falsethen begin inc(r); line[r]:=i; h:=true; end;end; end; end; until l>=r; 代码很简单的,至于代码的解释就引用资料上的一 段话我们用数组d记录每个结点的最短路径估计值,而且用邻接表来存储图G。我们采取的方法是 动态逼近法:设立一个先进先出的队列用来保存待 优化的结点,优化时每次取出队首结点u,并且用u 点当前的最短路径估计值对离开u点所指向的结点v 进行松弛操作,如果v点的最短路径估计值有所调 整,且v点不在当前的队列中,就将v点放入队尾。 这样不断从队列中取出结点来进行松弛操作,直至 队列空为止。,具体内容请自行揣摩。 N短路算法:有了最短路算法,自然要有第N 路算法,虽然我不知道这在实际应用中有什么用 处,实际上这种变形是很好求解的: *第二最短路径:枚举最短路径上的每条边,每次 删除一条,然后求新图的最短路径,取这些路径中 最短的一条即为第二最短路径。 *同理,第n最短路径可在求解第n-1最短路径的基 础上求解。 那么,怎样枚举最短路的每条边呢,可以想到如果 F[1,N]=F[1,K]+F[K,N],那么K点一定在1N的最短 路上,那么重复枚举此过程,就可以求得每一条 边,然后再根据上面的步骤求解第N短路即可。代 码就不给了。


二维码

扫码加我 拉你入群

请注明:姓名-公司-职位

以便审核进群资格,未注明则拒绝

关键词:数学建模 Kruskal算法 Kruskal prim算法 repeat 数学建模 模型 小菜 知识 资料

lvv5802001 发表于 2015-9-9 16:16:34 |显示全部楼层 |坛友微信交流群
楼主 这是什么语言呀

使用道具

hanws 发表于 2016-2-26 16:30:18 |显示全部楼层 |坛友微信交流群
提示: 作者被禁止或删除 内容自动屏蔽

使用道具

TY2551318543 学生认证  发表于 2016-12-12 14:30:55 |显示全部楼层 |坛友微信交流群
这个还不错

使用道具

TY2551318543 学生认证  发表于 2016-12-12 14:31:13 |显示全部楼层 |坛友微信交流群
要是有代码就好了

使用道具

TY2551318543 学生认证  发表于 2016-12-12 14:31:48 |显示全部楼层 |坛友微信交流群
不过还不错啦,祝你每天开心快乐

使用道具

您需要登录后才可以回帖 登录 | 我要注册

本版微信群
加JingGuanBbs
拉您进交流群

京ICP备16021002-2号 京B2-20170662号 京公网安备 11010802022788号 论坛法律顾问:王进律师 知识产权保护声明   免责及隐私声明

GMT+8, 2024-3-29 20:40