|
所在平台: Coursera |
课程主页: https://www.coursera.org/learn/delivery-problem
课程评论：没有评论
课程摘要：配送问题 课程名称：配送问题 概述：在这门在线课程中，我们将共同实现高效的程序来解决一个全球快递公司每天面临的难题——旅行推销员问题（TSP）。该问题的目标是尽快访问所有给定地点。如何快速找到该问题的最佳解决方案是一个挑战，我们仍然没有确凿有效的算法，这也是P与NP问题的核心所在。 课程大纲： 1. **旅行推销员问题** - 描述：本模块首先定义配送问题的数学模型——经典的旅行推销员问题（TSP）。接着，我们将回顾其多种应用，从简单的货物配送和旅行规划，到不太明显的数据存储与压缩、基因组组装等。随后，我们将共同迈出实现TSP程序的第一步。 2. **精确算法** - 描述：我们将深入了解应用于旅行推销员问题的两种通用技术。第一种是“分支限界法”，这是一种在组合优化中使用的经典方法，可以看作是暴力搜索的改进：我们尝试逐步构建一个排列，每一步检查是否继续构建是合理的（如果不合理则直接剪掉当前分支）。第二种是动态规划，这被认为是最流行的算法技术，通过解决一系列较小的子问题来解决整体问题。 3. **近似算法** - 描述：如前所述，精确解决旅行推销员问题是困难的，未来也不太可能有效率高的解决方案。因此，我们需要探讨是否可以高效地找到一个可能是次优的，但又接近最佳的解决方案。答案是肯定的！我们将学习两种算法。第一种算法保证快速找到长度至多为最佳解决方案两倍的解。第二种算法虽然没有这样的保证，但在实践中表现良好。 通过本课程，学员将掌握解决旅行推销员问题的基本理论与实现技巧，尤其在配送领域的应用。
Name:Traveling Salesman Problem
Description:We start this module with the definition of mathematical model of the delivery problem — the classical traveling salesman problem (usually abbreviated as TSP). We'll then review just a few of its many applications: from straightforward ones (delivering goods, planning a trip) to less obvious ones (data storage and compression, genome assembly). After that, we will together take the first steps in implementing programs for TSP.
Name:Exact Algorithms
Description:We'll see two general techniques applied to the traveling salesman problem. The first one, branch and bound, is a classical approach in combinatorial optimization that is used for various problems. It can be seen as an improvement of the brute force search: we try to construct a permutation piece by piece, but at each step we check whether it still makes sense to continue constructing the permutation (if it doesn't, we just cut off the current branch). The second one, dynamic programming, is arguably the most popular algorithmic technique. It solves a problem by going through a collection of smaller subproblems.
Name:Approximation Algorithms
Description:As we've seen in the previous modules, solving the traveling salesman problem exactly is hard. In fact, we don't even expect an efficient solution in the nearest future. For this reason, it makes sense to ask: is it possible to find efficiently a solution that is probably suboptimal, but at the same time is close to optimal? It turns out that the answer is yes! We'll learn two algorithms. The first one guarantees to find quickly a solution which is at most twice longer than the optimal one. The second algorithms does not have such guarantees, but it is known to work pretty well in practice.
In this online course we’ll implement (in Python) together efficient programs for a problem needed by delivery companies all over the world millions times per day — the travelling salesman problem. The goal in this problem is to visit all the given places as quickly as possible. How to find an optimal solution to this problem quickly? We still don’t have provably efficient algorithms for this difficult computational problem and this is the essence of the P versus NP problem, the most important o
