优化2：组合优化Combinatorial Optimization.

maltadirk · 发表于 2023-1-16 09:54

本笔记旨在介绍组合算法和算法效率理论。主要包括两大主题：

图上的网络和极值问题。network flows and extremal problems on graphs;
组合算法理论。theory of combinatorial algorithms;

会覆盖以下知识点：
图问题：最短路径、生成树、匹配。
组合算法：排序、合并、二叉树。
网络流：最大流、积分流、它们的应用、二部图中的匹配。
算法和复杂性：图灵机；多项式和指数时间算法之间的区别，NP 完全问题，可满足性问题；库克定理；多项式等价。

Chapter 1:

1.1 Motivating examples.

例1：Euclidean traveling salesman Problem. ETSP.
A helicopter has to visit 27 sites. The locations and distances are known, the target is to find in which order it should visit the sites in order to minimize the total distance flown. This give rise to a more general task called the Euclidean Traveling Salesman Problem, ETSP for short. In this problem sites (or points) v1, . . . , vn are given in the plane and for a permutation P π of {1, . . . , n} we let L(π) = n 1 |vπ(i+1)  vπ(i) | where |a  b| is the distance between points a, b ∈ R 2 , and vn+1 = v1 by convention.
Brute force approach;
Nearest neighbor approach;
ETSP 属于一大类众所周知的难题，目前尚无快速或有效的算法。通常假设（但目前还没有证据）事实上，没有用于 ETSP 的快速算法。
例2：Minimum cost path problem.
Given a road map with two specified locations u, v, and specified costs for travelling along each road, find the cheapest path from u to v.
There is a fast algorithm solving the minimum cost path problem.
例3：Decision problem.
Consider two sets S, T with S  T. Given t ∈ T, decide if t ∈ S or not.

1.2 Algorithms and running times.

上面的例子表明，要研究组合优化问题，我们应该研究算法，即可以遵循的解决问题的程序。通俗地说，我们会将算法视为“接受输入并产生解决某些任务的输出的过程”。大多数时候，我们将坚持算法的这种非正式概念，并研究针对特定问题的算法的具体示例。在本笔记的末尾，我们将学习图灵机，这是一种定义算法的数学精确方法（这使我们能够证明关于它们的定理）。
Running time.
Given a task, the running time of an algorithm A on an input I of this task is T(A, I) = number of steps taken by A on I. When it is clear what algorithm we are looking at, we abbreviate this to T(I).
这个定义目前还不完整，因为它没有定义什么是“步骤”即step。“step” or “operation”是算法执行的一个基本操作。在整个模块中，在不同的上下文中，以略有不同的方式计算步数会很方便。我们将在特定算法中计算步骤的特定方式称为该算法使用的“计算模型”。我们学习四种Models of computation。
1.3 Asymptotic analysis of algorithms.

算法的性能取决于所使用的机器或计算机。我们想摆脱这种依赖，希望独立于机器来比较算法。这个想法是使用渐近分析。也就是说，我们查看 T(n) 如何随着 n → ∞ 增长，而忽略可能取决于特定计算机或程序员技能的常数项和更小的阶项。例如，如果 T(n) = 6n^3 +7n^2  11n，则 T(n) 渐近 n=3，我们只是简单地删除了低阶项和常数。
1.4 4 types Models of computation.

		自动登录	找回密码
密码			立即注册