在执行的
n
n
n个操作中，有至多
⌈
l
g
n
⌉
⌈lg n⌉
⌈lgn⌉个操作的次序是
2
2
2的幂，这些操作的次序（即代价）如下
1
,
2
,
4
,
8
,
⋅
⋅
⋅
,
2
⌈
l
g
n
⌉
1, 2, 4, 8, · · · , 2 ⌈lg n⌉
1,2,4,8,⋅⋅⋅,2⌈lgn⌉
n
n
n个操作的总代价为
T
=
∑
k
=
0
⌈
l
g
n
⌉
2
k
+
(
n
−
⌈
l
g
n
⌉
)
×
1
=
2
⌈
l
g
n
⌉
+
1
−
1
+
(
n
−
⌈
l
g
n
⌉
)
≤
2
lg
n
+
2
+
n
−
l
g
n
=
3
l
g
n
+
n
\begin{aligned} T&=\sum^{⌈lg n⌉}_{k=0}2^k + (n − ⌈lg n⌉) × 1\\ &=2^{⌈lg n⌉+1} − 1 + (n − ⌈lg n⌉)\\ &≤2^{\lg n+2} + n − lg n\\ &=3 lg n + n \end{aligned}
T=k=0∑⌈lgn⌉2k+(n−⌈lgn⌉)×1=2⌈lgn⌉+1−1+(n−⌈lgn⌉)≤2lgn+2+n−lgn=3lgn+n
因此每个操作的摊还代价是
O
(
3
lg
n
+
n
n
)
=
O
(
1
)
O ( \cfrac{3 \lg n + n }n ) = O(1)
O(n3lgn+n)=O(1)的。
当操作次序是
2
2
2的幂时，为其赋
4
4
4的摊还代价，否则为其赋
2
2
2的摊还代价，则每一个不为
2
2
2 的幂的操作均会提供
1
1
1的信用以支付差额，对于一 个
n
n
n个操作组成的操作序列，有
4
×
⌈
lg
n
⌉
+
2
×
(
n
−
⌈
lg
n
⌉
)
=
2
×
⌈
lg
n
⌉
+
2
n
≤
3
lg
n
+
n
≤
∑
k
=
0
⌈
l
g
n
⌉
2
k
+
(
n
−
⌈
lg
n
⌉
)
×
1
\begin{aligned} &4×⌈\lg n⌉+2×(n−⌈\lg n⌉) \\ &=2×⌈\lg n⌉+2n\\ &≤3\lg n+n\\ &≤\sum^{⌈lg n⌉}_{k=0}2^k+(n−⌈\lg n⌉)×1 \end{aligned}
4×⌈lgn⌉+2×(n−⌈lgn⌉)=2×⌈lgn⌉+2n≤3lgn+n≤k=0∑⌈lgn⌉2k+(n−⌈lgn⌉)×1
每个操作的摊还代价都是常数，因此摊还代价都为
O
(
1
)
O(1)
O(1)。
定义势函数
Φ
P
h
i
(
D
i
)
=
{
0
,
i
=
0
1
,
i
=
1
lg
i
+
1
,
i
=
2
⌊
lg
i
⌋
⌊
lg
i
⌋
+
k
,
i
=
2
⌊
lg
i
⌋
+
k
ΦPhi(D_i) =\left\{ \begin{aligned} & 0, \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ i = 0\\ &1, \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ i = 1\\ & \lg i + 1, \ \ \ \ \ \ \ \ \ \ \ \ \ \ i = 2^{⌊\lg i⌋}\\ & ⌊\lg i⌋ + k, \ \ \ \ \ \ \ \ \ \ i = 2^{⌊\lg i⌋} + k \end{aligned} \right.
ΦPhi(Di)=⎩⎪⎪⎪⎪⎨⎪⎪⎪⎪⎧0, i=01, i=1lgi+1, i=2⌊lgi⌋⌊lgi⌋+k, i=2⌊lgi⌋+k
则对任意的
i
，
Φ
(
D
i
)
≥
0
i，Φ(D_i) ≥ 0
i，Φ(Di)≥0，且
Φ
(
D
i
)
−
Φ
(
D
i
−
1
)
=
{
1
−
i
,
i
=
2
⌊
lg
i
⌋
1
,
i
=
2
⌊
lg
i
⌋
+
k
Φ(D_i) − Φ(D_{i−1}) =\left\{ \begin{aligned} & 1-i, \ \ \ \ \ \ \ \ i = 2^{⌊\lg i⌋}\\ & 1, \ \ \ \ \ \ \ \ \ \ \ \ \ \ i = 2^{⌊\lg i⌋} + k \end{aligned} \right.
Φ(Di)−Φ(Di−1)={1−i, i=2⌊lgi⌋1, i=2⌊lgi⌋+k
所以：
∑
i
=
1
n
c
^
=
∑
i
=
1
n
1
=
n
\sum^n_{i=1}\hat{c}=\sum^n_{i=1}1=n
i=1∑nc^=i=1∑n1=n
因此每个操作的摊还代价是
O
(
1
)
O(1)
O(1)。
使用两个栈实现队列，将两个栈记为左右栈。
ENQUEUE
\text{ENQUEUE}
ENQUEUE：直接对左栈进行
push
\text{push}
push将元素入队
DEQUEUE
\text{DEQUEUE}
DEQUEUE：如果右栈非空，对右栈进行
pop
\text{pop}
pop。如果右栈为空，做一个迭代：把左栈元素
pop
\text{pop}
pop出来，
push
\text{push}
push进右栈，直到左栈为空，再执行
DEQUEUE
\text{DEQUEUE}
DEQUEUE。
FIND-MIN
\text{FIND-MIN}
FIND-MIN：在左右栈基础上再加一个辅助栈，用于记录最小值。每次有元素入左栈时，判断辅助栈为空或辅助栈的栈顶元素比入栈元素更大，则将该元素压入辅助栈中，否则将辅助栈的栈顶元素重复压入辅助栈。左栈需要弹出元素时，辅助栈需要同步弹出栈顶元素。取最小值时，直接将栈顶元素弹出，返回值即最小值。
摊还分析：
设
C
i
C_i
Ci为第
i
i
i个操作的代价（假定每个操作的代价为
1
1
1）设每次操作的势能
D(i)=2*
\text{D(i)=2*}
D(i)=2*左栈元素个数，设左栈元素个数为
k
k
k。
ENQUEUE：Ci+D(i)-D(i-1)=1+2*(k+1-k)=3
\text{ENQUEUE：Ci+D(i)-D(i-1)=1+2*(k+1-k)=3}
ENQUEUE：Ci+D(i)-D(i-1)=1+2*(k+1-k)=3，
k
+
1
k+1
k+1表示入队后的元素，所以入队摊还时间复杂度为
O
(
1
)
O(1)
O(1)
DEQUEUE
\text{DEQUEUE}
DEQUEUE：
如果右栈非空,左栈有 k k k个元素： Ci+D(i)-D(i-1)=1+2(k-k)=1 \text{Ci+D(i)-D(i-1)=1+2(k-k)=1} Ci+D(i)-D(i-1)=1+2(k-k)=1
如果右栈为空,左栈有 k k k个元素： Ci+D(i)-D(i-1)=2k+1+2(0-k)=1 \text{Ci+D(i)-D(i-1)=2k+1+2(0-k)=1} Ci+D(i)-D(i-1)=2k+1+2(0-k)=1，其中 2 k 2k 2k为左栈弹出元素数+右栈压入元素数， 1 1 1表示出队一个元素，所以出队摊还时间复杂度为 O ( 1 ) O(1) O(1)
FIND-MIN \text{FIND-MIN}FIND-MIN： 使用聚合法分析，取最小值实际上是对单个辅助栈的操作，考虑整个栈的
n nn个操作，一个对象压入栈后，至多弹出一次，则对该栈的
n nn个
PUSH、POP、MULTIPOP \text{PUSH、POP、MULTIPOP}PUSH、POP、MULTIPOP的操作序列，代价至多是
O ( n ) O(n)O(n)，一个操作的平均时间为
O ( n ) / n = 1 O(n)/n=1O(n)/n=1，所以摊还复杂度为
O ( 1 ) O(1)O(1)。
每次迭代添加包含未覆盖元素最多的集合, 直到满足全覆盖条件，时间复杂度为多项式时间
Θ
(
k
lg
n
)
\Theta(k\lg n)
Θ(klgn)
假设全集
S
S
S包含
n
n
n个元素，最优覆盖包含
k
k
k个子集合。那么我们使用的贪心算法最多会选择
k
ln
n
+
1
k\ln n+1
klnn+1个子集。
证明：
u j u_j uj：在贪心算法第 j j j次迭代还没有被覆盖的元素个数O P T OPT OPT：最优解k k k个最优集合必定可覆盖住该 u j u_j uj个元素，故最优集合中至少有一个集合包含至少 u j k \cfrac{u_j}k kuj个元素- 使用贪心算法后，我们可以递推得到 u j + 1 ≤ u j − u j k = u j ( 1 − 1 k ) ≤ u j − 1 ( 1 − 1 k ) ( 1 − 1 k ) ≤ … ≤ u 0 ( 1 − 1 k ) j + 1 = n ( 1 − 1 k ) j + 1 u_{j+1}\le u_j-\frac{u_j}k = u_j(1-\frac{1}k)\le u_{j-1}(1-\frac{1}k)(1-\frac{1}k)\le…\le u_0(1-\frac{1}k)^{j+1}=n(1-\frac{1}k)^{j+1} uj+1≤uj−kuj=uj(1−k1)≤uj−1(1−k1)(1−k1)≤…≤u0(1−k1)j+1=n(1−k1)j+1 所以 u j + 1 ≤ n ( 1 − 1 k ) j + 1 u_{j+1}\le n(1-\frac{1}k)^{j+1} uj+1≤n(1−k1)j+1
lim x → + ∞ ( 1 + x n ) n = e x \displaystyle\lim_{x \rightarrow + \infty}(1 + \frac{x}{n})^n = e^x x→+∞lim(1+nx)n=ex，即存在这样一个式子 1 − x < = e − x 1-x <= e^{-x} 1−x<=e−x对所有的 x x x都成立 所以 u j ≤ u 0 ( 1 − 1 k ) j < u 0 ( e − 1 k ) j = n e − j k ( 1 − 1 k ) j = ( ( 1 − 1 k ) k ) j k ≤ e − j k n ⋅ e − j k ≤ 1 ⇔ e − j k ≤ n − 1 ⇔ − j k ≤ − ln n ⇔ j ≥ k ln n \begin{aligned} &u_j \le u_0(1-\frac{1}k)^j < u_0(e^{-{\frac{1}k}})^j = ne^{-{\frac{j}k}}\\ &(1-\frac{1}k)^j=((1-\frac{1}k)^k)^\frac{j}k\le e^{-\frac{j}k}\\ &n·e^{-\frac{j}k}\le 1\Leftrightarrow e^{-\frac{j}k}\le n^{-1}\Leftrightarrow -\frac{j}k \le-\ln n\Leftrightarrow j\ge k\ln n \end{aligned} uj≤u0(1−k1)j<u0(e−k1)j=ne−kj(1−k1)j=((1−k1)k)kj≤e−kjn⋅e−kj≤1⇔e−kj≤n−1⇔−kj≤−lnn⇔j≥klnn 当 j = k ln n j=k\ln n j=klnn，结果等于 1 1 1，也就是说没有其他的元素剩下了，此时 ( 1 − 1 k ) k ln n ≤ e − ln n (1-\frac{1}k)^{k\ln n}\le e^{-\ln n} (1−k1)klnn≤e−lnn， O P T ≥ k ≥ O P T ⋅ ( 1 − ( 1 − 1 k ) k ) ≥ 1 − 1 e OPT\ge k\ge OPT·(1-(1-\frac{1}k)^k)\ge 1-\frac{1}e OPT≥k≥OPT⋅(1−(1−k1)k)≥1−e1，所以近似比为 1 − ( 1 − 1 k ) k ≥ 1 − 1 e 1-(1-\frac{1}k)^k\ge 1-\frac{1}e 1−(1−k1)k≥1−e1，则对于一个含有 k ln n + 1 k\ln n+1 klnn+1个子集的集合覆盖， k ln n + 1 ∈ Θ ( k ⋅ ln n ) = Θ ( k lg n ) k\ln n+1∈\Theta(k·\ln n)=\Theta(k\lg n) klnn+1∈Θ(k⋅lnn)=Θ(klgn)。
当我们选择一个集合之后，删除已经被覆盖的元素。然后我们选择每个单位成本最小的集合直到覆盖所有元素。本质上每次选择覆盖未覆盖元素最多的集合。
C
C
C：代表到目前为止涵盖的元素集
cost effectiveness , or α
\text{cost effectiveness , or α}
cost effectiveness , or α：每个新覆盖节点的平均成本
伪代码：
Greedy Method:
Initial C
While C != U:
Find the set Si whose cost effectiveness is the smallest
then Set C = C∪Si
Let α= wi/|Si-C|
For each e∈Si-C : Set price(e)= α
end While
Output Selected sets
我们每次选取的都是
w
i
S
i
−
C
\cfrac{w_i}{S_i-C}
Si−Cwi最小的集合
S
i
S_i
Si，即每次新添的集合
S
i
S_i
Si的新增覆盖率相对于
cost
\text{cost}
cost值都是最大的，从而实现局部最优。
选择的集合按照先后顺序为
S
1
,
S
2
,
…
,
S
m
S_1 , S _2 , … , S _m
S1,S2,…,Sm
n
i
n _i
ni 是选择
S
i
S_i
Si时，其覆盖的新元素个数。
元素被覆盖的顺序
e
1
,
e
2
,
…
,
e
n
e_1,e_2,…,e _n
e1,e2,…,en 。
设
S
j
S_j
Sj第一次覆盖新元素
e
k
e_k
ek 。
C
1
,
.
.
.
C_1,...
C1,...是最优覆盖中的部分集合，覆盖了
e
k
,
…
,
e
n
，
n
i
′
e_ k , … , e _n，n _i'
ek,…,en，ni′ 是其覆盖的对应元素个数。不仅仅是
e
k
,
…
,
e
n
e_ k ,…,e_ n
ek,…,en 中的元素。
∑ i n i ′ ≥ n − k + 1 , ∑ i c o s t ( C i ) ≤ O P T \sum_i n_i'\ge n-k+1, \sum_i cost(C_i)\leq OPT ∑ini′≥n−k+1,∑icost(Ci)≤OPT，因为 C i , . . . C_ i , . . . Ci,...也可能覆盖了其他元素，是从最优覆盖中选择的部分集合。C 1 , . . . . C_1 ,.... C1,....没有与 S 1 , . . . S j − 1 S_1,...S_{j-1} S1,...Sj−1重复的。假设某个 C i C_i Ci 在 S 1 , . . . S j − 1 S_1,...S_{j-1} S1,...Sj−1中，则 e k e_k ek之后的元素会被某个 S i ( i ∈ [ 1 , j − 1 ] ) S_i(i\in[1,j-1]) Si(i∈[1,j−1])覆盖，矛盾。∑ i c o s t ( C i ) ∑ i n i ′ ≤ O P T n − k + 1 ⟹ \cfrac{\sum_i cost(C_i) }{\sum_i n_i'}≤ \cfrac{O P T}{n − k + 1}\Longrightarrow ∑ini′∑icost(Ci)≤n−k+1OPT⟹存在某个 c o s t ( C i ) n i ′ ≤ O P T n − k + 1 \cfrac{cost(C_i)}{n_i′}≤ \cfrac{O P T}{n − k + 1} ni′cost(Ci)≤n−k+1OPT。- 由贪心算法选出的 c o s t ( S j ) n j ≤ c o s t ( C i ) n i ′ \cfrac{cost(S_j)}{n_j}≤ \cfrac{cost(C_i)}{n_i′} njcost(Sj)≤ni′cost(Ci)。
- 对于每个 k k k都存在满足 3 3 3和 4 4 4的 C i C_i Ci
- 每个点被覆盖的代价 c o s t ( e k ) ≤ c o s t o p t ( S ) n − k + 1 cost(e_k)\le \frac {cost_{opt}(S)}{n-k+1} cost(ek)≤n−k+1costopt(S)，所以在整个贪心过程中的总代价为 ∑ c o s t ( e k ) ≤ ( 1 + 1 2 + 1 3 + ⋅ ⋅ ⋅ 1 n ) ⋅ c o s t o p t = H n ⋅ c o s t o p t \sum cost(e_k)\le(1+\frac12+\frac13+···\frac1n)·cost_{opt} =H_n·cost_{opt} ∑cost(ek)≤(1+21+31+⋅⋅⋅n1)⋅costopt=Hn⋅costopt
∑ k c o s t ( e k ) ≤ ∑ k c o s t ( C i ) n i ′ ≤ ∑ k O P T n − k + 1 ∼ ln n ⋅ O P T \sum_kcost(e_k)\leq \sum_k\cfrac{cost(C_i)}{n_i′} \leq \sum_k\cfrac{O P T}{n − k + 1}∼\ln n·OPT ∑kcost(ek)≤∑kni′cost(Ci)≤∑kn−k+1OPT∼lnn⋅OPT.
所以近似比为
ln
n
\ln n
lnn
本文转载自: https://blog.csdn.net/weixin_56462041/article/details/128020362
版权归原作者 之墨_ 所有， 如有侵权，请联系我们删除。
版权归原作者 之墨_ 所有， 如有侵权，请联系我们删除。