Approximation¶
约 264 个字 预计阅读时间 1 分钟
对于一维装箱问题,除非\(P=NP\),否则不可能存在近似比小于\(\frac 32\)的算法.
在线算法(online):
- \(Next \ Fit\):只要装不下了,就新开一个箱子,如果最优解用\(M\)个箱子,那么nf最多用\(2M-1\)个箱子;
- \(First \ Fit\):按箱子打开的顺序从早到晚检查,将物品放入第一个能放下的箱子中;
- \(Best\ Fit\):将物品放入剩余空间最小的箱子中,最大化利用箱子空间;
- \(Worst \ Fit\):将物品放入剩余空间最大的箱子中.
离线算法(offline):
- FFD:如果最优解用M个箱子,那么FFD最多用\(\frac{11M}{9}+\frac 69\)个箱子
\(Next \ Fit\)近似比是2
FF和BF近似比都是1.7
\(0-1\)背包问题,近似比是2.但是如果已知最优解中价值最大的前\(k\)个,那么可以设计出近似比为\(\frac{k+1}{k}\)的算法
\(k-center\)问题近似比是2.
- PTAS:是\(n\)的多项式,但不是\(\epsilon\)的多项式
- FPTAS:是\(n\)和\(\epsilon\)的多项式