本课程将继续我们的数据结构和算法专业，重点讲解如何使用线性和整数编程公式来解决算法问题，以寻求资源分配、调度、任务分配和旅行推销员问题变体等领域问题的最优解。接下来，我们将研究 NP 难问题的算法，这些算法的解保证在最佳解的某个近似因子范围内。这类算法通常相当高效，并能提供有用的最优解界限。学习将得到教师提供的笔记、教科书中的阅读内容和作业的支持。作业包括概念性选择题以及涉及编程和测试算法的解题作业。
逼近算法与线性规划
了解顶级公司的员工如何掌握热门技能
积累特定领域的专业知识
本课程是 数据结构和算法基础 专项课程 专项课程的一部分
在注册此课程时，您还会同时注册此专项课程。
- 向行业专家学习新概念
- 获得对主题或工具的基础理解
- 通过实践项目培养工作相关技能
- 获得可共享的职业证书
该课程共有4个模块
本模块介绍了线性规划的基础知识，并展示了一些算法问题（如网络流问题）如何以线性规划的形式提出。我们将提供如何用 Python 提出并解决线性规划问题的实践教程。最后，我们将简要介绍线性规划算法，包括著名的求解线性规划的 Simplex 算法。问题集将引导您提出并解决一些有趣的问题，如金融投资组合问题和线性规划的最优运输问题。
涵盖的内容
7个视频5篇阅读材料6个作业1个编程作业4个非评分实验室
本模块将介绍整数线性规划及其在解决 NP 难（组合优化）问题中的应用。我们将举例说明什么是整数线性规划，如 Knapsack、Vertex Cover 和 Graph Coloring 等问题。接下来，我们将学习积分差距的概念，并研究顶点覆盖问题的积分差距特例。最后，我们将讲解如何使用 python 库 Pulp 编制和求解整数线性规划。
涵盖的内容
6个视频5个作业1个编程作业4个非评分实验室
我们将介绍解决 NP 难问题的近似算法。这些算法速度很快（通常是贪婪算法），可能不会产生最优解，但能保证其解与最佳解不会 "相差太远"。我们将从对相关概念的基本介绍开始，介绍其中的一些算法，然后介绍调度问题、顶点覆盖问题和最大可满足性问题的一系列近似算法。
涵盖的内容
5个视频4个作业1个编程作业3个非评分实验室
我们将介绍旅行推销员问题（TSP）：一个非常重要且广泛应用的组合优化问题、其 NP 难度以及用常数因子逼近一般 TSP 的难度。 我们将介绍整数线性规划公式和一种简单而优雅的动态规划算法。我们将介绍 Christofides 提出的 3/2 因子近似算法，并讨论一些求解 TSP 的启发式方法。最后，我们将介绍 knapsack 问题的近似方案。
涵盖的内容
11个视频5个作业1个编程作业3个非评分实验室
获得职业证书
将此证书添加到您的 LinkedIn 个人资料、简历或履历中。在社交媒体和绩效考核中分享。
攻读学位
课程 是 University of Colorado Boulder提供的以下学位课程的一部分。如果您被录取并注册，您已完成的课程可计入您的学位学习，您的学习进度也可随之转移。
位教师
授课教师评分
(11个评价)
人们为什么选择 Coursera 来帮助自己实现职业发展
Felipe M.
自 2018开始学习的学生
''能够按照自己的速度和节奏学习课程是一次很棒的经历。只要符合自己的时间表和心情，我就可以学习。'
Jennifer J.
自 2020开始学习的学生
''我直接将从课程中学到的概念和技能应用到一个令人兴奋的新工作项目中。'
Larry W.
自 2021开始学习的学生
''如果我的大学不提供我需要的主题课程，Coursera 便是最好的去处之一。'
Chaitanya A.
''学习不仅仅是在工作中做的更好：它远不止于此。Coursera 让我无限制地学习。'
从 计算机科学 浏览更多内容
University of Colorado Boulder
École normale supérieure
University of Colorado Boulder
École normale supérieure