运筹学_在线算法(中科院胡晓东).pdfVIP

运筹学基础 胡晓东 应用数学研究所 中国科学院数学与系统科学研究院 北京2734信箱，北京100190 电子邮件: xdhu@amss.ac.cn, 电话: 6263-9192, 办公室: 904 Institute of Applied Mathematics 5. 组合优化-算法设计技巧 精确算法 分而治之(有哪些信誉好的足球投注网站、排大小序、旅行商) 动态规划 (最短路、三角剖分、背包) 分支定界(整数线性规划、旅行商、工件排序) 近似算法或启发式算法 贪婪策略(最小生成树、最大可满足、背包、 顶点覆盖、独立集、旅行商) 局部有哪些信誉好的足球投注网站(最大匹配、旅行商、最大割) 序贯法(工件排序、装箱、顶点着色) 整数规划法(顶点覆盖、最大可满足、最大割) 随机方法(最小割、最大可满足、顶点覆盖) 在线算法(页面调度、k-服务器、工件排序、装箱) xdhu 2 5.9 经典例子 到目前为止，当我们考虑如何设计求解一个优化问题的算 法的时候，都是假设这个优化问题中的每一个（变）量或者参 数都已经知道了。然而，在我们处理实际问题时，常常会发现 有些问题的（变）量或者参数的具体数值，事先并不知道，但 是我们还是需要即时（online ）做出决定或者选择。 我们考虑一个经典的例子：假如这个冬天你决定去滑雪。 那么去之前，你面临两种选择： 每次去滑雪时，花1$ 钱去租一套滑雪用具。 花T$ 钱去买一副滑雪用具，这样整个冬天你就可一直用它。 显然，如果你知道能会花L 次，那么当L T 时，你就每次去 租；否则L ≥T，你就买一套。 xdhu 3 5.9 经典例子 （续一） 然而，你不太确定你能滑多少次。 是买？ 是租？ 一个可能的（在线）方法是： 首先，滑k 次且租k 次； 然后，在去滑第k+1 次时，再买。 xdhu 4 5.9 经典例子 （续二） 然而，我们怎么选定这个k 呢？更一般的讲，我们如何 评价在线算法的优劣呢？很自然地想法是估计一下你能滑几 次，或者给出滑n 次的概率分布，然后，再算一下在线算法所 产生的费用的期望值。然而，一般来讲，这个估计值或者概率 分布是非常难确定的。不过，我们可以将在线算法所产生的费 用与离线算法 （假设所有信息都知道）所产生的费用进行比较 和分析，这样的方法被称为竞争分析。 设A 是一个在线算法，S 是在线(最小化) 问题的一个变量 输入序列，用cA (S) 记算法A 应对S 所产生的费用，用cOPT (S) 记最优离线算法应对（一次给定的）S 所产生的费用。若对于 任意的S ，都有 cA (S) ≤αcOPT (S) 则称在线算法A 是一个α-竞争算法。 5 5.9 经典例子 （续三） 让我们再回过头来用竞争分析的方法来考虑如何处理滑雪 时遇到的租－买用具问题。最简单的方法是：第一天就买滑 雪用具（即k = 0 ），花费T$。注意，如果（事先知道）只滑 了1 次，即L = 1 ，那么最优的策略是租，花费1$。竞争比是 T ，这不是一个常数！ 一个稍微复杂一点的方法是：前T －1 天租，然后再买。 如果L T ，那么即使事先知道此信息，最优策略也是租。 如果L ≥T ，那么在线算法的费用是(2T －1)$；