Basic Reduction Strategies I慕课视频播放-算法设计与分析-MOOC慕课视频教程-柠檬大学

建立不同问题的规约有很多方法

往往需要很强的技巧性

这里我们介绍几种常用的规约方法

包括简单的问题等价性的规约

从特殊情形到一般情形的规约

以及通过一个小装置来完成规约

之前介绍过独立集问题

给定一个图G=(V, E)和一个整数k

是否有一个点的子集S

使得S中元素个数大于等于k

并且图中任何一条边

至多有一个端点属于S

比如对如下的图

是否有一个至少包含6个点的独立集呢

答案是肯定的

浅色的6个点构成了一个独立集

是否有一个至少包含了7个点的独立集呢

答案是否定的

我们再介绍顶点覆盖问题

给定一个图G=(V, E)和一个整数k

是否有一个点的子集S

使得S中元素个数小于等于k

并且图中任何一条边

至少有一个端点属于S

比如对如下的图

是否有一个至少包含4个点的顶点覆盖呢

答案是肯定的

深色的4个点就构成了一个顶点覆盖

是否有一个至多包含3个点的顶点覆盖呢

答案是否定的

我们证明顶点覆盖问题

多项式时间等价于独立集问题

我们只需证明S是一个独立集

当且仅当V-S是一个顶点覆盖

先来证明必要性

令S是一个独立集

考虑任意一条边(u, v)

因为S是独立集

我们有u∉S或者v∉S

推出 u或者v∈V-S

即 V-S是一个顶点覆盖

再来证明充分性

令V-S是一个顶点覆盖

考虑S中的两个顶点u和v

因为V-S是一个顶点覆盖

一定有(u, v)∉E

因此S中任意两点都没有边相连

得到S是一个独立集

我们再给一个

从特殊情形到一般情形的规约

我们先给出集合覆盖问题

给定一个集合U

以及它的一些子集S_1, S_2, . . . , S_m

和一个整数k

是否存在不超过k个子集

使得它们的并等于集合U

或者说这k个子集覆盖集合U

我们有下面的例子

U={ 1, 2, 3, 4, 5, 6, 7 }

k=2

S_1={3, 7}

S_2={3, 4, 5, 6}

S_3={1}

S_4={2, 4}

S_5={5}

S_6={1, 2, 6, 7}

可以发现S_2和S_6的并等于U

因此这个例子的回答是“yes”

我们将证明VERTEX-COVER

多项式规约为SET-COVER

任意给定一个VERTEX-COVER的实例

即给定图G=(V, E)和数k

我们构建一个SET-COVER的例子

在这个例子中取同样的数k

令U=E, S_v=和点v关联的边集

比如下例中

VERTEX-COVER的实例有6个点和7条边

k=2

令SET-COVER的实例为

U={1, 2, 3, 4, 5, 6, 7}

k=2

S_a={3, 7}

S_b={2, 4}

S_c={3, 4, 5, 6}

S_d={5}

S_e={1}

S_f={1, 2, 6, 7}

VERTEX-COVER实例中

点f和c覆盖了所有的边

显然集合S_a和S_f的并等于全集

我们有SET-COVER中

不超过k个集合覆盖U

当且仅当VERTEX-COVER中

存在不超过k个点的顶点覆盖

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

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

Basic Reduction Strategies I在线视频