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

我们讨论一些关于顺序问题的NP完全性

哈密尔顿圈问题是

给定一个无向图G=(V, E)

是否存在一个简单圈

包含V中的每个点恰好一次

对于下面的图

这是一个两分图含有9个节点

不存在哈密尔顿圈

而对于一般的图

我们将证明这个问题是NP完全的

我们先证明有向哈密尔顿圈问题

可以多项式规约为哈密尔顿圈问题

有向哈密尔顿圈问题

是给定一个有向图G=(V, E)

是否存在一个简单的有向圈

包含V中的每个点恰好一次

下面来证明有向哈密尔顿圈问题

可以多项式规约为哈密尔顿圈问题

给定一个有向图G=(V, E)

构建一个无向图G'

包含3n个节点

构建方法如图所示

对于图G中任意点v

在G'中对应3个节点v_in,v,v_out

它们被标记成红蓝绿

并依次相连

对于G中的弧(a,v)

对应G'中的边(a_out, v_in)

我们有 G有一个有向哈密尔顿圈

当且仅当G'有哈密尔顿圈

先证充分性

假设G有一个有向哈密尔顿圈Γ

那么在G'中有个同顺序的哈密尔顿圈

其中任意点v替换成v_in,v,v_out依次相连的顺序

再证必要性

假设G'有哈密尔顿圈Γ'

那么其中节点的颜色

一定是蓝绿红蓝绿红…的顺序

或蓝红绿蓝红绿…的顺序

这里因为在哈密尔顿圈中

蓝色节点一定连着红色和绿色节点各一个

而三种颜色节点各n个

所以只能依次出现

如上面的顺序排列

以上顺序中

所有蓝色节点对应的顺序或反序

对应G中一个有向哈密尔顿圈

下面我们证明3-SAT问题

多项式时间规约为有向哈密尔顿圈问题

给定3-SAT的实例Φ

我们构建有向哈密尔顿圈问题的实例

使得存在一个有向哈密尔顿圈

当且仅当Φ是适定的

首先我们构建一个图

它存在2^n个哈密尔顿圈

对应着3-SAT问题的2^n个可能的赋值

令3-SAT的实例Φ有n个变量x_i及k个分句

构建一个图G

有一个起点s 一个终点t

还有n组节点对应Φ的n个变量

每组包含3k+3个节点

每组中的节点双向连接

s指向第一组首末两个节点

每组首末两个节点

指向下一组首末两个节点

最后一组首末两个节点指向t

t指向s

在访问n组节点时

可以从左到右

也可以从右到左

共有2^n个哈密尔顿圈

直觉上

我们可以把第i组从左到右的访问

对应为x_i=1

对于每个分句

在图G中增加一个分句节点和六条边

每组节点中包含3k+3个节点

我们可以顺序地分给每个句子3个节点

比如第一个句子C_1中出现了x_1

那么在第一组中用顺序的两个节点

从左到右地连接C_1对应的分句节点

C_1中出现了x_2 not

那么在第二组中用顺序的两个节点

从右到做地连接C_1对应的分句节点

以此类推

如图所示

下面来证明Φ是适定的

当且仅当G存在一个有向哈密尔顿圈

先证必要性

若Φ有一个真值分配x^*

那么如下方式

可以得到G中的哈密尔顿圈

若 x^*_i=1的话

那么令第i行从左到右访问

如果 x^*_i=0的话

那么令第i行从右向左访问

对于每个分句C_j

它至少有一个文字

在以上的赋值中取值为1

设为第i个变量

那么在访问第i行的时候

顺路加上C_j对应的节点

这样我们得到了一个有向哈密尔顿圈

再证充分性

若G有一个有向哈密尔顿圈Γ

若Γ进入分句Cj节点

它必须立刻访问同一行的对应节点离开

不然就会出现堵塞

Γ中C_j之前之后的节点处于同一行

且它们有相同的边相连

令边为e

我们把C_j删去

增加边e

这样在新图中

得到了一个有向的哈密尔顿圈Γ'

令x^*_i=1

当且仅当Γ'在第i行从左到右访问

因为Γ访问了每个分句节点C_j

如果在第i行访问了C_j

对应的赋值一定使得C_j得到满足

因此我们得到了Γ的一组真值分配

旅行商问题（TSP）

是一个经典的组合优化问题

它的判定问题为

给定n个城市和两两之间的距离函数d(u, v)

是否存在长度不超过D的环游

我们建立由哈密尔顿圈问题

到TSP问题的规约

回顾哈密尔顿圈问题

给定一个无向图G=(V, E)

是否存在一个简单圈

包含V中的每个点恰好一次

给定哈密尔顿圈问题的实例G=(V, E)

我们构建TSP问题的实例

包含n个城市

距离函数为

当(u, v)属于E

令d(u, v)=1

当(u, v)不属于E

令d(u, v)=2

显然 TSP的实例有长度不超过n的环游

当且仅当图G有哈密尔顿圈

另外我们还注意到

在以上构造的TSP实例满足三角不等式

因此满足三角不等式的TSP问题

也是NP完全的

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

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

Sequencing Problems在线视频