一些算法
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了一些算法,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含921字,纯文字阅读大概需要2分钟。
内容图文
![一些算法](/upload/InfoBanner/zyjiaocheng/1091/3ce6d932b7674cf8a3dc854c58f900d6.jpg)
1.分支界限算法
在历届NOIP竞赛中,有4道初赛题和5道复赛题均涉及到背包问题,所谓的背包问题,可以描述如下:
一个小偷打劫一个保险箱,发现柜子里有N类不同大小与价值的物品,但小偷只有一个容积为M的背包来装东西,背包问题就是要找出一个小偷选择所偷物品的组合,以使偷走的物品总价值最大。
如有4件物品,容积分别为: 3 4 5 8
对应的价值分别为: 4 5 7 10
小偷背包的载重量为:12
则取编号为1 2 3的物品,得到最大价值为16。
2.A*算法
A*[1](A-Star)算法是一种静态路网中求解最短路最有效的直接搜索方法。
注意是最有效的直接搜索算法。之后涌现了很多预处理算法(ALT,CH,HL等等),在线查询效率是A*算法的数千甚至上万倍。
公式表示为: f(n)=g(n)+h(n),
其中 f(n) 是从初始点经由节点n到目标点的估价函数,
g(n) 是在状态空间中从初始节点到n节点的实际代价,
h(n) 是从n到目标节点最佳路径的估计代价。
保证找到最短路径(最优解的)条件,关键在于估价函数h(n)的选取:
估价值h(n)<= n到目标节点的距离实际值,这种情况下,搜索的点数多,搜索范围大,效率低。但能得到最优解。并且如果h(n)=d(n),即距离估计h(n)等于最短距离,那么搜索将严格沿着最短路径进行, 此时的搜索效率是最高的。
如果 估价值>实际值,搜索的点数少,搜索范围小,效率高,但不能保证得到最优解。
3.广度优先算法
最佳解:若所有边的长度相等,广度优先搜索算法是最佳解——亦即它找到的第一个解,距离根节点的边数目一定最少;但对一般的图来说,BFS并不一定回传最佳解。这是因为当图形为加权图(亦即各边长度不同)时,BFS仍然回传从根节点开始,经过边数目最少的解;而这个解距离根节点的距离不一定最短。这个问题可以使用考虑各边权值,BFS的改良算法成本一致搜寻法(en:uniform-cost search)来解决。然而,若非加权图形,则所有边的长度相等,BFS就能找到最近的最佳解。
原文:http://www.cnblogs.com/-yan/p/4271853.html
内容总结
以上是互联网集市为您收集整理的一些算法全部内容,希望文章能够帮你解决一些算法所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。