Center Selection慕课视频播放-算法设计与分析-MOOC慕课视频教程-柠檬大学

我们再来看中心选址问题

给定n个位置s_1,…,s_n

我们希望选取k个中心

对这些位置进行服务

令选取的中心的集合为C

使得每个位置

到离其最近中心的距离的最大值最小

这就是中心选址问题

在学校商场

及公共设施建设中有广泛的应用

比如下图中黑色方块表示位置

令k=4

蓝色圆圈表示所选的中心

那么每个位置对应一个离它最近的中心

对于每个中心

我们以它为圆心画一个圆

覆盖它所服务的位置

令圆的半径为

所有位置到它对应中心距离的最大值

因为k=4 我们得到4个圆

中心选址问题就是要求圆的半径最小

对于中心选址问题

我们先给出一些定义

dist(x,y)为x和y的距离

dist(s_i,C)为s_i到C中最近的中心的距离

r(C)为所有位置

到它对应中心距离的最大值

我们称为覆盖半径

我们的目标是求中心的集合C

使得r(C)最小

且C中恰有k个中心

对于距离函数

我们需要

到自身的距离为0

即dist(x,x)=0

对称性

即dist(x,y)=dist(y,x)

还要满足三角不等式

即dist(x,y)≤dist(x,z)+dist(z,y)

我们先尝试一个简单的贪婪策略

我们每一步选择一个当前最好的中心

进行k步

算法终止

比如对下面的例子

有若干个位置

聚集成2组

选择第一个中心的时候

为了使覆盖半径最小

我们把中心设立在2组位置的中间

然后设置第二个中心

我们发现

不管把它设立在什么位置

它几乎不减少第一步得到的覆盖半径

而最优解

显然是在两组位置附近各设立一个中心

贪婪算法得到的解可以任意差

我们来看另一个贪婪算法

我们在n个位置中选择中心的设立

每步选择一个中心

使得它离已经设立的中心距离最远

算法伪代码如下

先令C为空集

在每一步选择一个位置si

使得它到C的距离最大

把si作为中心加入C中

直到已经选择了k个中心

初始的时候

可以选择任意的一个位置

我们发现

若算法终止时的覆盖半径为r(C)

那么C中任意两个中心的距离至少为r(C)

首先在算法的过程中

随着中心的加入

每个点到离其最近的中心距离

是单调不增的

所以r(C)是单调不增的

算法每一步都加入离已有中心最远的点

它到任何已有中心的距离

一定不小于当前的r(C)

因此算法终止的时候

C中任意两个中心的距离至少为r(C)

下面来证明算法是2近似的

令C^*是最优解中的中心集合

那么r(C)≤2r(C^*)

我们用反证法

假设 r(C^*)<½r(C)

对于C中的每个点

我们做一个半径为½r(C)的圆

因为C中任意两个中心的距离至少为r(C)

那么任意两个圆至多交于1点

因为最优解的覆盖半径r(C^*)<½r(C)

而C中的中心都选自位置

两组解中都有k个中心

那么每个圆中

恰包含一个最优解中的中心

令C中的中心ci所确定的圆中

包含了C^*中的中心c_i^*

下面考察任意的一个点s

和在C**中距离它最近的中心c_i^*

dist(s,C)≤dist(s,c_i)

根据三角不等式

它≤dist(s,c_i*)+dist(c_i^*,c_i)

这两部分都≤r(C^*)

因此r(C)≤2r(C^*)

与假设矛盾

由以上讨论可知

这个贪婪算法是2近似的

贪婪算法只在给定的位置上选择中心

如果更加自由的选择

是否能得到更好的结果呢

比如3/2近似 4/3近似的结果呢

实际上可以证明

除非P=NP

对于任何ρ<2

中心选址问题不存在ρ近似算法

算法设计与分析课程列表：

1 Introduction of Algorithm

-1.1 Introduction

--Introduction

-1.2 A First Problem: Stable Matching

--A First Problem: Stable Matching

-1.3 Gale-Shapley Algorithm

--Gale-Shapley Algorithm

-1.4 Understanding Gale-Shapley Algorithm

--Understanding Gale-Shapley Algorithm

-Homework1

-Lecture note 1

--Lecture note 1 Introduction of Algorithm

2 Basics of Algorithm Analysis

-2.1 Computational Tractability

--Computational Tractability

-2.2 Asymptotic Order of Growth

--Asymptotic Order of Growth

-2.3 A Survey of Common Running Times

--A Survey of Common Running Times

-Homework2

-Lecture note 2

--Lecture note 2 Basics of Algorithm Analysis

3 Graph

-3.1 Basic Definitions and Applications

--Basic Definitions and Applications

-3.2 Graph Traversal

--Graph Traversal

-3.3 Testing Bipartiteness

--Testing Bipartiteness

-3.4 Connectivity in Directed Graphs

--Connectivity in Directed Graphs

-3.5 DAG and Topological Ordering

--DAG and Topological Ordering

-Homework3

-Lecture note 3

--Lecture note 3 Graph

4 Greedy Algorithms

-4.1 Coin Changing

--Coin Changing

-4.2 Interval Scheduling

--Interval Scheduling

-4.3 Interval Partitioning

--Interval Partitioning

-4.4 Scheduling to Minimize Lateness

--Scheduling to Minimize Lateness

-4.5 Optimal Caching

--Optimal Caching

-4.6 Shortest Paths in a Graph

--Shortest Paths in a Graph

-4.7 Minimum Spanning Tree

--Minimum Spanning Tree

-4.8 Correctness of Algorithms

--Correctness of Algorithms

-4.9 Clustering

--Clustering

-Homework4

-Lecture note 4

--Lecture note 4 Greedy Algorithms

5 Divide and Conquer

-5.1 Mergesort

--Mergesort

-5.2 Counting Inversions

--Counting Inversions

-5.3 Closest Pair of Points

--Closest Pair of Points

-5.4 Integer Multiplication

--Integer Multiplication

-5.5 Matrix Multiplication

--Video

-5.6 Convolution and FFT

--Convolution and FFT

-5.7 FFT

--FFT

-5.8 Inverse DFT

--Inverse DFT

-Homework5

-Lecture note 5

--Lecture note 5 Divide and Conquer

6 Dynamic Programming

-6.1 Weighted Interval Scheduling

--Weighted Interval Scheduling

-6.2 Segmented Least Squares

--Segmented Least Squares

-6.3 Knapsack Problem

--Knapsack Problem

-6.4 RNA Secondary Structure

--RNA Secondary Structure

-6.5 Sequence Alignment

--Sequence Alignment

-6.6 Shortest Paths

--Shortest Paths

-Homework6

-Lecture note 6

--Lecture note 6 Dynamic Programming

7 Network Flow

-7.1 Flows and Cuts

--Flows and Cuts

-7.2 Minimum Cut and Maximum Flow

--Minimum Cut and Maximum Flow

-7.3 Ford-Fulkerson Algorithm

--Ford-Fulkerson Algorithm

-7.4 Choosing Good Augmenting Paths

--Choosing Good Augmenting Paths

-7.5 Bipartite Matching

--Bipartite Matching

-Homework7

-Lecture note 7

--Lecture note 7 Network Flow

8 NP and Computational Intractability

-8.1 Polynomial-Time Reductions

--Polynomial-Time Reductions

-8.2 Basic Reduction Strategies I

--Basic Reduction Strategies I

-8.3 Basic Reduction Strategies II

--Basic Reduction Strategies II

-8.4 Definition of NP

--Definition of NP

-8.5 Problems in NP

--Problems in NP

-8.6 NP-Completeness

--NP-Completeness

-8.7 Sequencing Problems

--Sequencing Problems

-8.8 Numerical Problems

--Numerical Problems

-8.9 co-NP and the Asymmetry of NP

--co-NP and the Asymmetry of NP

-Homework8

-Lecture note 8

--Lecture note 8 NP and Computational Intractability

9 Approximation Algorithms

-9.1 Load Balancing

--Load Balancing

-9.2 Center Selection

--Center Selection

-9.3 The Pricing Method: Vertex Cover

--The Pricing Method: Vertex Cover

-9.4 LP Rounding: Vertex Cover

--LP Rounding: Vertex Cover

-9.5 Knapsack Problem

--Knapsack Problem

-Homework9

-Lecture note 9

--Lecture note 9 Approximation Algorithms

10 Local Search

-10.1 Landscape of an Optimization Problem

--Landscape of an Optimization Problem

-10.2 Maximum Cut

--Maximum Cut

-10.3 Nash Equilibria

--Nash Equilibria

-10.4 Price of Stability

--Price of Stability

-Homework10

-Lecture note 10

--Lecture note 10 Local Search

11 Randomized Algorithms

-11.1 Contention Resolution

--Contention Resolution

-11.2 Linearity of Expectation

--Linearity of Expectation

-11.3 MAX 3-SAT

--MAX 3-SAT

-11.4 Chernoff Bounds

--Chernoff Bounds

-Homework11

-Lecture note 11

--Lecture note 11 Randomized Algorithms

Exam

-Exam

Center Selection在线视频