2016华为软件精英挑战赛:低级案例—暴力出奇迹(一)


比赛今天截止,最终只得了83分左右(稍微有点点波动),只最后一名多0.07分,多少有些辜负队友的期望,本来是打着要进入32强的旗 比赛的。厉害的人真多啊,特别是最终的排行榜上绝大部分都是成电的,身处同一个环境差距还是有的,你们是我前进的动力!

2016华为软件精英挑战赛:低级案例---暴力出奇迹(一)

尽管华为比赛没能进入32强,但是还是学到了不少东西。在这里分享一下针对华为前五个低级案例的解决方案,当然我相信有很多同学前五个案例也是这种解决方法


二,比赛感受

当自己最初的算法设计被证实有问题时感觉好无助。从本次比赛的过程中其实最大的感受就是强者太多,山外总是有山,人外总是有人啊,自己永远也不会是最牛的,永远都不要骄傲。

三,算法设计思想

针对前五个低级案例的解决方案:

1,从起点开始深度优先搜索,并用数组记录沿途边 ,当遇到终点时,此时就已经搜索到一条路径,否则就一直深度优先访问下去。

2,这条路径不一定全部经过毕竟点,所以要检查一下是否包含全部必经点。

3,如果全部包含必经点,则存储该路径,以后遇到比该路径权值更小的就更新路径。

4,显然这是一个递归的思路。


四,算法分析

这是一个暴力搜索,从起点到终点的路径随着顶点个数的增多有趋近指数级的条数,并且还要搜索出很多无效路径,所以相当费时。


五,代码的实现:

注意:

1),采用邻接矩阵建图,矩阵中每个元素存储着边的索引 和

2)头文件中类的完整声明

其中图是一个全局变量(邻接矩阵)!

声明:本站部分文章及图片源自用户投稿,如本站任何资料有侵权请您尽早请联系jinwei@zod.com.cn进行处理,非常感谢!

上一篇 2016年3月9日
下一篇 2016年3月10日

相关推荐