欢迎来到天天文库
浏览记录
ID：53051095
大小：11.59 MB
页数：20页
时间：2020-04-16
《拟阵及其简单应用.ppt》由会员上传分享，免费在线阅读，更多相关内容在PPT专区-天天文库。
1、拟阵及其简单应用By川雾最大权极大线性无关组如果该线性空间在有限域上(如模2剩余类整数域)，有没有解决办法？最大权极大线性无关组拟阵拟阵理论(MatroidTheory)是组合优化的一个分支。矩阵胚拟阵理论虽然并不是因为贪心算法而引入，但是却是贪心算法的强力辅助。拟阵结构的判断并不复杂，结论也十分简单：在问题模型满足拟阵结构的情况下，贪心策略总是能够得到最优解拟阵拟阵的概念拟阵的基本性质拟阵结构基础上贪心策略的正确性拟阵的简单应用开篇：最大权极大线性无关组问题最小生成树Kruscal算法的正确性证明其他题目拟阵
2、的概念拟阵的概念拟阵的概念贪心算法拟阵的性质拟阵的性质拟阵的性质贪心算法贪心算法拟阵的简单应用拟阵的简单应用拟阵的简单应用异或和最大问题给出n个数，求从中选出尽可能多的数满足：这些数之中任意多个的异或和不为0这些数的和最大将所有数转化为二进制，以每一位作为一维，那么原问题就转化成了模二剩余类整数域上的最大权极大线性无关组问题。直接贪心即可。拟阵的简单应用拟阵的简单应用附注谢谢观赏！
此文档下载收益归作者所有
