文章目录
0.前言
老早以前就看到这玩意儿了，但是没当回事。
然后今天遇到了这样的题……被摁得死死的。
私以为，胡伯涛将这个问题讲得很严谨。这里就直接将他的东西拷下来吧！
可以去看看
别人的博客
，也是可以的。毕竟我只是拾人牙慧而已。
1.分数规划
先给出
分数规划(fractional programming)
的一般形式：
对于解空间
S
S
S
、
连续的实值函数
a
(
x
)
,
b
(
x
)
a({\bf x}),b({\bf x})
a
(
x
)
,
b
(
x
)
，满足
∀
x
∈
S
,
b
(
x
)
>
0
\forall{\bf x}\in S,b({\bf x})>0
∀
x
∈
S
,
b
(
x
)
>
0
，求
min
x
∈
S
f
(
x
)
=
a
(
x
)
b
(
x
)
\min_{
{\bf x}\in S}f({\bf x})=\frac{a(\bf x)}{b(\bf x)}
x
∈
S
min
f
(
x
)
=
b
(
x
)
a
(
x
)
解决分数规划问题的一般方法是分析其对偶问题，但更加实用的方法是对其进行
参数搜索(parametric search)
，即对答案进行猜测，再验证该猜测值的最优性，将优化问题转化为判定性问题或其他的优化问题。由于分数规划模型的特殊性，使得能够构造另外一个由猜测值
λ
\lambda
λ
作为自变量的相关问题，且该问题的解满足一定的单调性，或其他的可以减小参数搜索范围的性质
①
，从而逼近答案。
① 比如
Dinkelbach
\text{Dinkelbach}
Dinkelbach
算法，每次直接把上次子问题的解向量代入原问题的表达式，算出下一个迭代式的猜测值。详见参考文献
[Dink67],[MSS92]
\text{[Dink67],[MSS92]}
[Dink67],[MSS92]
。
假设
λ
0
=
f
(
x
0
)
\lambda_0=f({\bf x_0})
λ
0
=
f
(
x
0
)
是最优解，根据定义有
λ
0
=
f
(
x
0
)
=
a
(
x
0
)
b
(
x
0
)
⇒
λ
0
⋅
b
(
x
0
)
=
a
(
x
0
)
⇒
a
(
x
0
)
−
λ
0
⋅
b
(
x
0
)
=
0
\begin{aligned} &\lambda_0=f({\bf x_0})=\frac{a(\bf x_0)}{b(\bf x_0)}\\ \Rightarrow\;\;&\lambda_0\cdot b({\bf x_0})=a(\bf x_0)\\ \Rightarrow\;\;&a({\bf x_0})-\lambda_0\cdot b({\bf x_0})=0 \end{aligned}
⇒
⇒
λ
0
=
f
(
x
0
)
=
b
(
x
0
)
a
(
x
0
)
λ
0
⋅
b
(
x
0
)
=
a
(
x
0
)
a
(
x
0
)
−
λ
0
⋅
b
(
x
0
)
=
0
由上面的形式构造一个新函数
g
(
λ
)
=
min
x
∈
S
[
a
(
x
)
−
λ
⋅
b
(
x
)
]
g(\lambda)=\min_{
{\bf x}\in S}[a({\bf x})-\lambda\cdot b(\bf x)]
g
(
λ
)
=
x
∈
S
min
[
a
(
x
)
−
λ
⋅
b
(
x
)
]
这个新函数是一个非分式的规划。先来挖掘函数
g
(
λ
)
g(\lambda)
g
(
λ
)
本身的性质。
1.1.单调性
g
(
λ
)
g(\lambda)
g
(
λ
)
是一个严格递减函数，即，
∀
λ
1
,
λ
2
∈
R
,
λ
1
<
λ
2
⇔
g
(
λ
1
)
>
g
(
λ
2
)
\forall \lambda_1,\lambda_2\in\R,\lambda_1<\lambda_2\;\Leftrightarrow\; g(\lambda_1)>g(\lambda_2)
∀
λ
1
,
λ
2
∈
R
,
λ
1
<
λ
2
⇔
g
(
λ
1
)
>
g
(
λ
2
)
。
只需要注意到，在
g
(
λ
1
)
g(\lambda_1)
g
(
λ
1
)
中原有的
x
\bf x
x
代入
g
(
λ
2
)
g(\lambda_2)
g
(
λ
2
)
会得到更小的结果即可。
1.2.
Dinkelbach
\text{Dinkelbach}
Dinkelbach
定理
② 出自参考文献
[Dink67]
\text{[Dink67]}
[Dink67]
。
若
λ
0
\lambda_0
λ
0
为原问题的答案，则
λ
=
λ
0
⇔
g
(
λ
)
=
0
\lambda=\lambda_0\;\Leftrightarrow\; g(\lambda)=0
λ
=
λ
0
⇔
g
(
λ
)
=
0
。
1.2.1.必要性
先证明
λ
=
λ
0
⇒
g
(
λ
)
=
0
\lambda=\lambda_0\;\Rightarrow\;g(\lambda)=0
λ
=
λ
0
⇒
g
(
λ
)
=
0
。
设
λ
0
=
f
(
x
0
)
\lambda_0=f({\bf x_0})
λ
0
=
f
(
x
0
)
，根据定义有
∀
x
∈
S
,
λ
0
=
a
(
x
0
)
b
(
x
0
)
≤
a
(
x
)
b
(
x
)
⇒
a
(
x
)
−
λ
0
⋅
b
(
x
)
≥
0
\begin{aligned} \forall {\bf x}\in S,\lambda_0=\frac{a(\bf x_0)}{b(\bf x_0)}&\le\frac{a(\bf x)}{b(\bf x)}\\ \Rightarrow\;\; a({\bf x})-\lambda_0\cdot b({\bf x})&\ge 0 \end{aligned}
∀
x
∈
S
,
λ
0
=
b
(
x
0
)
a
(
x
0
)
⇒
a
(
x
)
−
λ
0
⋅
b
(
x
)
≤
b
(
x
)
a
(
x
)
≥
0
而
x
0
\bf x_0
x
0
恰好取到这个下界
0
0
0
，所以最小值就是
0
0
0
，证毕。
1.2.2.充分性
再证明
g
(
λ
)
=
0
⇒
λ
=
λ
0
g(\lambda)=0\;\Rightarrow\;\lambda=\lambda_0
g
(
λ
)
=
0
⇒
λ
=
λ
0
。
反证法。反设存在一个解
λ
′
=
f
(
x
′
)
\lambda’=f(\bf x’)
λ
′
=
f
(
x
′
)
是更优的解，根据定义有
λ
′
=
a
(
x
′
)
b
(
x
′
)
<
λ
⇒
a
(
x
′
)
−
λ
⋅
b
(
x
′
)
<
0
\begin{aligned} \lambda’=\frac{a(\bf x’)}{b(\bf x’)}&<\lambda\\ \Rightarrow\;\;a({\bf x’})-\lambda\cdot b({\bf x’})&<0 \end{aligned}
λ
′
=
b
(
x
′
)
a
(
x
′
)
⇒
a
(
x
′
)
−
λ
⋅
b
(
x
′
)
<
λ
<
0
那么，将
x
′
\bf x’
x
′
代入，可以发现
g
(
λ
)
g(\lambda)
g
(
λ
)
一定是小于零的，与题设矛盾。
1.3.二分查找
仍然设
λ
0
\lambda_0
λ
0
为答案，则
{
g
(
λ
)
=
0
⇔
λ
=
λ
0
g
(
λ
)
<
0
⇔
λ
>
λ
0
g
(
λ
)
>
0
⇔
λ
<
λ
0
\begin{cases} g(\lambda)=0\;\Leftrightarrow\;\lambda=\lambda_0\\ g(\lambda)<0\;\Leftrightarrow\;\lambda>\lambda_0\\ g(\lambda)>0\;\Leftrightarrow\;\lambda<\lambda_0 \end{cases}
⎩
⎪
⎨
⎪
⎧
g
(
λ
)
=
0
⇔
λ
=
λ
0
g
(
λ
)
<
0
⇔
λ
>
λ
0
g
(
λ
)
>
0
⇔
λ
<
λ
0
此时便可以进行二分查找了。
2.零一分数规划
分数规划的一个特例是
0-1 分数规划(0-1 fractional programming)
③
，就是其解向量
x
\bf x
x
满足
∀
i
,
x
i
∈
{
0
,
1
}
\forall i,x_i\in\{0,1\}
∀
i
,
x
i
∈
{
0
,
1
}
（这就是所谓的 0-1）。形式化定义如下：
③ 0-1 分数规划的相关知识，在参考文献
[MSS92]
\text{[MSS92]}
[MSS92]
中有详细介绍。
min
x
∈
S
f
(
x
)
=
∑
i
a
i
x
i
∑
i
b
i
x
i
=
a
⋅
x
b
⋅
x
\min_{
{\bf x}\in S} f({\bf x})=\frac{\sum_{i}a_ix_i}{\sum_{i}b_ix_i}=\frac{\bf a\cdot x}{\bf b\cdot x}
x
∈
S
min
f
(
x
)
=
∑
i
b
i
x
i
∑
i
a
i
x
i
=
b
⋅
x
a
⋅
x
同样地，必须要满足
∀
x
∈
S
,
b
⋅
x
>
0
\forall {\bf x}\in S,{\bf b\cdot x}>0
∀
x
∈
S
,
b
⋅
x
>
0
，且有比较特殊的
S
⊆
{
0
,
1
}
n
S\subseteq\{0,1\}^n
S
⊆
{
0
,
1
}
n
。
它的应用范围很广，经典例题是
最优比率生成树(the optimum ratio spanning tree)
④
。
④ 详见参考文献
[LiuH04]
\text{[LiuH04]}
[LiuH04]
，303-304 页。
3.应用
3.1.网络战争(Network Wars)
⑤ 题目来源：Zhejiang University Online Judge – Andrew Stankevich’s Contest #8 – 2676 Network Wars
题目描述
给出一个带权无向图
G
=
(
V
,
E
)
G=(V,E)
G
=
(
V
,
E
)
，每条边
e
e
e
有一个权
w
e
w_e
w
e
。求将点
s
s
s
和点
t
t
t
分开的一个边割集
C
C
C
，使得该割集的平均边权最小，即最小化：
∑
e
∈
C
w
e
∣
C
∣
\frac{\sum_{e\in C}w_e}{|C|}
∣
C
∣
∑
e
∈
C
w
e
题目解答
先尝试着用更一般的形式重新叙述本问题。设向量
w
\bf w
w
表示边的权值，令向量
c
=
(
1
,
1
,
…
,
1
)
{\bf c} = (1,1,\dots,1)
c
=
(
1
,
1
,
…
,
1
)
表示选边的代价，于是原问题等价为：
min
x
∈
S
⊆
{
0
,
1
}
∣
E
∣
f
(
x
)
=
w
⋅
x
c
⋅
x
\min_{
{\bf x}\in S\subseteq\{0,1\}^{|E|}} f({\bf x})=\frac{\bf w\cdot x}{\bf c\cdot x}
x
∈
S
⊆
{
0
,
1
}
∣
E
∣
min
f
(
x
)
=
c
⋅
x
w
⋅
x
这是一个 0-1 分数规划的形式，构造一个新函数
g
(
λ
)
=
min
x
∈
S
[
(
w
−
λ
c
)
⋅
x
]
g(\lambda)=\min_{
{\bf x}\in S}[({\bf w}-\lambda{\bf c})\cdot{\bf x}]
g
(
λ
)
=
x
∈
S
min
[
(
w
−
λ
c
)
⋅
x
]
即对每条边
∀
e
∈
E
\forall e\in E
∀
e
∈
E
，进行重赋权：
w
e
′
=
w
e
−
λ
⋅
c
e
=
w
e
−
λ
w_e’=w_e-\lambda\cdot c_e=w_e-\lambda
w
e
′
=
w
e
−
λ
⋅
c
e
=
w
e
−
λ
。
g
(
λ
)
g(\lambda)
g
(
λ
)
就是在这个重新赋权的图上，求一个最小容量的
s
−
t
s-t
s
−
t
边割集。请注意一些细节：若
w
e
′
<
0
w_e'<0
w
e
′
<
0
，又由于目标函数是加和取最小的操作，则该边必然是在边割集内。对于剩下的所有边，直接利用最小割模型求出
s
−
t
s-t
s
−
t
割即可。
3.2.奥术神杖
请参考
这篇博客
，这里就不将其复制了。
3.3.
H
i
k
i
n
g
\tt Hiking
H
i
k
i
n
g
题目描述
传送门 to luogu
：任取单增序列
1
≤
x
1
<
x
2
<
⋯
<
x
k
≤
n
1\le x_1<x_2<\cdots<x_k\le n
1
≤
x
1
<
x
2
<
⋯
<
x
k
≤
n
，其权值为
∑
i
=
1
k
−
1
∣
a
x
i
+
1
−
a
x
i
−
l
∣
\sum_{i=1}^{k-1}\sqrt{|a_{x_{i+1}}-a_{x_i}-l|}
∑
i
=
1
k
−
1
∣
a
x
i
+
1
−
a
x
i
−
l
∣
与
∑
i
=
1
k
b
x
i
\sum_{i=1}^{k}b_{x_i}
∑
i
=
1
k
b
x
i
的比值。求其最小值。
l
,
n
,
a
,
b
l,n,a,b
l
,
n
,
a
,
b
事先给出。
题目解答
这道题好像不能完全转化为
f
(
x
)
f({\bf x})
f
(
x
)
的形式。但是学习不能学死！想想二分到底有什么用。无非是希望得到比这个值更优的解。因为
a
b
<
k
⇔
a
−
k
b
<
0
{a\over b}<k\Leftrightarrow a-kb<0
b
a
<
k
⇔
a
−
k
b
<
0
，所以将选择一个点的权值定义为：“根号”减去
k
b
x
i
kb_{x_i}
k
b
x
i
。然后求其最小。
题解代码
#include <cstdio>
#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
typedef long long int_;
inline int readint(){
int a = 0; char c = getchar(), f = 1;
for(; c<'0'||c>'9'; c=getchar())
if(c == '-') f = -f;
for(; '0'<=c&&c<='9'; c=getchar())
a = (a<<3)+(a<<1)+(c^48);
return a*f;
}
inline void writeint(int x){
if(x > 9) writeint(x/10);
putchar((x%10)^48);
}
int qkpow(int_ bas,int q,int M){
int ans = 1;
for(; q; q>>=1,bas=bas*bas%M)
if(q&1) ans = ans*bas%M;
return ans;
}
const int MaxN = 1005;
const double infty = pow(2,100);
int x[MaxN], b[MaxN], n, l;
double gen[1000005]; // gen[x] = sqrt(x)
double dp[MaxN]; // 第 x 必选时
int pre[MaxN]; // 便于输出方案
double check(double k){
for(int i=1; i<=n; ++i){
dp[i] = infty;
for(int j=0; j<i; ++j){
int d = x[i]-x[j]-l;
if(d < 0) d = -d;
double val = dp[j]+gen[d];
if(dp[i] > val+1e-6){
dp[i] = val;
pre[i] = j;
}
}
dp[i] -= k*b[i];
}
return dp[n];
}
inline void print(int x){
if(!x) return ;
print(pre[x]);
printf("%d ",x);
}
int main(){
x[0] = 0, n = readint();
l = readint();
for(int i=1; i<=n; ++i){
x[i] = readint();
b[i] = readint();
}
for(int i=0; i<=1000000; ++i)
gen[i] = sqrt(i);
double L = 0, R = 1000;
while(L+1e-9 < R)
if(check((L+R)/2) < -1e-8)
R = (L+R)/2;
else L = (L+R)/2;
print(n);
return 0;
}
4.参考文献
本文主要摘自胡伯涛(Amber)《最小割模型在信息学竞赛中的应用(Applications of Minimum Cut Model in Informatics)》1.6节、2.2节。
-
[MSS92]\text{[MSS92]}
[MSS92]
T. Matsui and Y. Saruwatari and M. Shigeno. An Analysis of Dinkelbach’s Algorithm for 0-1 Fractional Programming Problems. Technical Report METR92-14, Department of Mathematical Engineering and Information Physics, Unversity of Tokyo,1992 -
[Dink67]\text{[Dink67]}
[Dink67]
Werner Dinkelbach. On Nonlinear Fractional Programming. Management Science, Vol. 13, No. 7, Series A, Sciences. (Mar., 1967), pp. 492-498. -
[LiuH04]\text{[LiuH04]}
[LiuH04]
刘汝佳，黄亮《算法艺术与信息学竞赛》，清华大学出版社，2004