|
所在平台: Coursera |
课程主页: https://www.coursera.org/learn/linear-programming-and-approximation-algorithms
课程评论：没有评论
课程名称：近似算法与线性规划 课程概述：本课程是数据结构与算法专业化的延续，专注于如何利用线性和整数规划来解决寻求最优解的算法问题。这些问题来自资源分配、调度、任务分配以及旅行推销员问题的变种等领域。接下来，我们将研究NP难题的算法，这些算法的解决方案保证能够在某个近似因子内接近最佳解决方案。 课程大纲： 1. **线性规划**：本模块介绍线性规划的基本概念，并展示如何将某些算法问题（如网络流问题）表述为线性规划。课程将通过Python提供实践教程，指导如何构建和解决线性规划问题，并简要概述包括著名的单纯形算法在内的线性规划算法。问题集将引导学员构建和解决一些有趣的线性规划问题，如金融投资组合问题和最优运输问题。 2. **整数线性规划**：本模块将覆盖整数线性规划及其在解决NP难（组合优化）问题中的应用。我们会通过对背包问题、顶点覆盖和图着色问题等实例进行问题建模来介绍整数线性规划的概念。接下来，我们将研究整数gap的概念，以及顶点覆盖问题的特例。最后，将提供关于如何使用Python库Pulp构建和解决整数线性规划的实践教程。 3. **近似算法：调度、顶点覆盖与最大满足问题**：我们将介绍用于求解NP难问题的近似算法。这些算法通常很快（往往是贪心算法），虽然不一定产生最优解，但保证它的解决方案与最佳方案不会“相差太远”。本模块将从基础概念开始，依次介绍调度问题、顶点覆盖问题和最大满足问题的一系列近似算法。 4. **旅行推销员问题（TSP）与近似方案**：本模块将介绍旅行推销员问题，这是一种非常重要且广泛适用的组合优化问题，讨论其NP难性及用常量因子近似一般TSP的困难性。我们将展示整数线性规划的表述及一种简单而优雅的动态规划算法。课程还将介绍Christofides提出的3/2因子近似算法，并讨论解决TSP的一些启发式方法。最后，我们将展示关于背包问题的近似方案。 通过本课程，您将掌握使用线性与整数规划解决各种算法问题的基础，并了解近似算法的应用与理论。
Name:Linear Programming
Description:This module introduces the basics of linear programs and shows how some algorithm problems (such as the network flow problem) can be posed as a linear program. We will provide hands-on tutorials on how to pose and solve a linear programming problem in Python. Finally, we will provide a brief overview of linear programming algorithms including the famous Simplex algorithm for solving linear programs. The problem set will guide you towards posing and solving some interesting problems such as a financial portfolio problem and the optimal transportation problem as linear programs.
Name:Integer Linear Programming
Description:This module will cover integer linear programming and its use in solving NP-hard (combinatorial optimization) problems. We will cover some examples of what integer linear programming is by formulating problems such as Knapsack, Vertex Cover and Graph Coloring. Next, we will study the concept of integrality gap and look at the special case of integrality gap for vertex cover problems. We will conclude with a tutorial on formulating and solving integer linear programs using the python library Pulp.
Name:Approximation Algorithms : Scheduling, Vertex Cover and MAX-SAT
Description:We will introduce approximation algorithms for solving NP-hard problems. These algorithms are fast (often greedy algorithms) that may not produce an optimal solution but guarantees that its solution is not "too far away" from the best possible. We will present some of these algorithms starting from a basic introduction to the concepts involved followed by a series of approximation algorithms for scheduling problems, vertex cover problem and the maximum satisfiability problem.
Name:Travelling Salesperson Problem (TSP) and Approximation Schemes
Description:We will present the travelling salesperson problem (TSP): a very important and widely applicable combinatorial optimization problem, its NP-hardness and the hardness of approximating a general TSP with a constant factor. We present integer linear programming formulation and a simple yet elegant dynamic programming algorithm. We will present a 3/2 factor approximation algorithm by Christofides and discuss some heuristic approaches for solving TSPs. We will conclude by presenting approximation schemes for the knapsack problem.
This course continues our data structures and algorithms specialization by focussing on the use of linear and integer programming formulations for solving algorithmic problems that seek optimal solutions to problems arising from domains such as resource allocation, scheduling, task assignment, and variants of the traveling salesperson problem. Next, we will study algorithms for NP-hard problems whose solutions are guaranteed to be within some approximation factor of the best possible solutions.
