最远优先遍历
在计算几何中，紧致度量空间的最远优先遍历（）是该空间中的一个点序列。首个点任意选取，此后每次都选取距已有点集最远的点。这个概念也适用于有限几何点集，即只需将候选点限定在该点集中。也可等价地将这些点视为一个有限度量空间。对于有限度量空间或有限几何点集，由此得到的序列是全部点的排列，又称贪心排列。 最远优先遍历的任一前缀都能得到一组彼此疏离、又接近其余各点的点集。更确切地说，任何规模相同的点集，其点间距至多为该点集的两倍。而其余点到点集的最…
标签：#近似演算法
共 7 篇文章
多项式时间近似算法
在计算机科学领域，多项式时间近似算法（PTAS）是一种用于优化问题（最常见的是NP-hard优化问题）的近似算法。 PTAS使用一个大于0的参数 ε，产生一个对于最小化问题能在 1 + ε 倍最优解内的解决方案（或最大化问题的 1 − ε 倍）。例如，对于欧几里得旅行商问题，现有的最好PTAS 将产生一个长度最多为 (1 + ε) L 的解，其中L是最短行程的长度。 ε的大小越小，PTAS的近似性能比越靠近1，也即说明这个PTAS的计算…
近似的困难性
计算机科学中，近似的複雜性（hardness of approximation）是研究最佳化問題中，有關尋找接近最佳解的計算複雜性理論。 範圍 近似的複雜性補足了近似算法的研究，後者證明了，針對一些問題，有關問題是否可以有效找到近似解，有一些限制因子。一般來說這些限制會有一個近似因子，若是超過，問題就會變成NP困难，也就是除非NP=P，不然不可能找到多項式时间复杂度的近似解。有些近似複雜性的結果，不過是建立在一些假設上，其中最出名的是。…
集合覆盖问题
集合覆盖问题（Set covering problem，SCP）是组合数学、计算机科学和计算复杂性理论中的一个经典问题。 集合覆盖的决定性问题是卡普的二十一个NP-完全问题之一。 定义 给定全集\mathcal{U}，以及一个包含n个集合且这n个集合的并集为全集的集合\mathcal{S}。集合覆盖问题要找到\mathcal{S}的一个最小的子集，使得他们的并集等于全集。 例如\mathcal{U} = \{1, 2, 3, 4, 5\…
最邻近搜索
最邻近搜索（Nearest Neighbor Search, NNS）又称为“最近点搜索”（Closest point search），是一个在尺度空间中寻找最近点的优化问题。问题描述如下：在尺度空间M中给定一个点集S和一个目标点q ∈ M，在S中找到距离q最近的点。很多情况下，M为多维的欧几里得空间，距离由欧几里得距离或曼哈顿距离决定。 高德纳在《计算机程序设计艺术》（1973）一书的第三章中称之为邮局问题，即居民寻找离自己家最近的邮…
近似算法
在计算机科学和运筹学中，近似算法（）是指能为最优化问题寻找近似解的算法，该类算法找到的近似解与最优解之间的差值需能证明不超过某个值。由于人们普遍猜测P≠NP，许多优化问题因此无法在多项式时间内得到精确解决。进而，理論計算機科學领域内自然而然地出现了试图在多项式时间复杂度内得到近似最优解的近似算法。在绝大多数情况下，近似算法得到的近似值位于最优解到最优解乘以某个特定的值之间，这个特定的值被称作近似比。不过，也有一些算法得到的近似值是在最优…
克里斯托菲德斯算法
克里斯托菲德斯算法（）是旅行商问题在度量空间（即距离对称且满足三角不等式）上的一个近似算法。 该算法可以保证相对最优哈密尔顿回路长度有3/2的近似比。于1976年首次发表了这个算法，故以他的名字命名之。 ，这一算法仍然是一般性旅行商问题的算法中近似比最好的结果。 算法 令 G = (V,w) 是旅行商问题的一个实例。 即， G 是一顶点集V 上的一个完全图，函数 w 给 G 的每条边指定了一个非负实边权。 依三角不等式，对每三个顶点 u…