北京网站建设116net,南宁网站建设公司哪个好,代理注册公司服务,政务网站的建设算法导论【在线算法】The Ski-Rental Problem问题描述在线算法证明The Lost Cow Problem问题描述在线算法类似问题—寻宝藏The Secretary Problem问题描述在线算法The Best Possible kThe Ski-Rental Problem
问题描述
假设你正在上滑雪课。每节课结束后#xff0c;你决定你决定取决于你喜欢的程度、你的骨骼状况和天气是继续滑雪还是完全停止滑雪。你可以选择以1美元一次的价格租用滑雪板也可以以B美元的价格购买滑雪板。你是买还是租如果你事先知道你一生中会滑雪多少次那么选择租还是买就很简单了。如果你要滑雪超过BBB次那就在开始前购买否则就一直租。该算法的代价为min(T,B)min(T,B)min(T,B)。这种对未来了如指掌的策略被称为离线策略。
在线算法
实际上你不知道你会滑雪多少次。你该怎么办在线策略是取一个数字k这样在租用k−1次后您将购买滑雪板就在第k次滑雪之前。如果我们取kBkBkB那么可以保证我们支付不会超过离线策略成本两倍的费用例如假设B7美元那么在6次租金之后你就买了。总付款6713$
证明
最坏情况下kBkBkB我们选择在滑雪次数Tk−1Tk-1Tk−1次后再也不滑雪那么在线算法的总费用为B−1B2B−1B-1B2B-1B−1B2B−1而离线算法取得的最优解为min(T,B)Bmin(T,B)Bmin(T,B)B此时竞争比为2B−1B2−1B\cfrac{2B-1}{B}2-\cfrac{1}{B}B2B−12−B1则我们说这个策略是(2−1B)(2-\cfrac{1}{B})(2−B1)竞争的
The Lost Cow Problem
问题描述
Old McDonald失去了他最喜欢的奶牛。最后一次看到它朝着通向两条无限道路的路口行进。没有一位目击者能说出奶牛是选择了左边还是右边的路线。
在线算法
在线算法是9-competitive的换句话说在找到奶牛之前可能经过的距离最多是最佳离线算法知道奶牛在哪里距离的9倍最坏的情况是他发现奶牛的距离比他上次在这一侧搜索的距离稍远因此OPT2jεOPT2jεOPT2jε其中jjj迭代次数εεε是某个小距离。然后伪代码如下 类似问题—寻宝藏 mmm条路编号为1,2,3...m1,2,3...m1,2,3...m从第一条路开始寻找初始寻找距离为d1d1d1如果在这个距离内找到了宝藏则结束寻找没找到则寻找距离翻倍切换至寻找下一条路径路径编号对mmm取模保证每次寻找的路径都是合法的直到找到宝藏。
Treasure(m)
d 1;current side 1
while true doWalk distance d on current sideif find treasure thenexitelsed 2dcurrent side (current side1)%mreturn to starting point该算法的竞争比为O(m)O(m)O(m)
证明
最坏的情况是发现宝藏的距离比上次在这条路上搜索的距离稍远一点点因此最优解为OPT2jεOPT2^j εOPT2jε其中jjj迭代次数εεε是某个小距离。则
CostOPT2jε2jCostONm(124...2j1)2jεm⋅2j22jε(4m1)⋅2jε(4m1)⋅CostOPT\begin{aligned} Cost OPT 2^j ε2^j\\ \ \ \ \ \ \ Cost ON m(124...2^{j1})2^j ε\\ m · 2^{j2} 2^j ε (4m1)· 2^j ε (4m1) · Cost OPT \end{aligned} CostOPT CostON2jε2jm(124...2j1)2jεm⋅2j22jε(4m1)⋅2jε(4m1)⋅CostOPT
所以竞争比为O(4m1)O(m)O(4m1)O(m)O(4m1)O(m)
The Secretary Problem
问题描述
我们有n位候选人可能是求职者或可能的婚姻伴侣。我们的目标是选择最好的候选人。假设候选人可以从最好到最坏完全排序没有任何联系。候选人以随机顺序依次到达。我们只能在候选人到达时确定他们的相对排名。我们不能观察绝对等级。每次面试后我们必须立即接受或拒绝申请人。候选人一旦被拒绝就不能被召回。一旦候选人被录取我们就停止面试。
在线算法
已知候选人数n在线策略在遇到第i位候选人后我们能够给出分数score(i)。选择一个正整数kn面试并拒绝前k位候选人。继续面试剩下的n-k位并接受第一位得分高于前k位候选人的候选人。如果最高分在第一批面试的k人里那么我们必须接受第n位即最后一位申请人伪代码
The Best Possible k
结论如果我们在knek\cfrac{n}{e}ken的情况下实施我们的策略我们将以至少1e\cfrac{1}{e}e1的概率成功雇佣我们最合格的申请人
