图论算法小结
2021-05-06 19:29
阅读：733
标签：难点 动态规划 问题 过程 难度 floyd 网络 小结 最短路径问题 图论算法内容难度较大，且灵活多变，本篇是对前述内容的小结 1. 图论算法设计难点 （1）如何将一个实际问题转化成图上的搜索问题（建模难） （2）如何选择最优的搜索方式，搜索代价的代价函数怎么设计（构造难） 2. 算法一览 （1）图论基本算法（DFS、BFS、最小生成树（prim（贪心）、kruskal（贪心））、最短路径（dijkstra（贪心）、floyd（动态规划））） （2）网络流算法（FF算法）：算法过程、算法证明（最大流和最小割的对偶性） （3）最大二分匹配算法：FF算法（最大匹配和最小覆盖的对偶性）、匈牙利算法 （4）可行解的搜索算法：爬山法（局部贪心）、Best-first（全局贪心） （5）最优解的搜索算法：分支界限（例：多阶段图最短路径问题、人员安排问题）、A*算法（例：最短路径问题） 图论算法小结 标签：难点 动态规划 问题 过程 难度 floyd 网络 小结 最短路径问题 原文地址：https://www.cnblogs.com/duanshuai/p/13187713.html
评论
亲，登录后才可以留言！