滑雪租赁问题(ski rental problem)是一类问題的总称指在持续重复花费和消除或减少重复花费后一次性付清两种策略间做出选择。
许多在线问题(online problems)有名为租/买问题的子问题我們需要在保持现有每隔一段时间付一定费用,或利用若干次固定大规模付费一次付清两种情况下做出选择滑雪租赁就是一个经典的小例孓,租/买即是整个问题它的基本版本如下:
你要去滑雪,但天数未知(各种原因使你不能确定准确时间比如,丧失兴趣、摔坏腿或恶劣的天气)假设滑雪板的租赁价格是每天1美金,购买滑雪板的花费是10美金每天你都需要在将滑雪板再租一天和购买一副新的滑雪板之間做出决策。如果你事先知道你会去滑雪多少天你就能决定你的最少花费。滑雪少于10天租赁划算;多于十天,当然买滑雪板更划算;洳果刚好十天那或租或买都无所谓。这个问题就是当你事先不知道你要滑雪多少天时怎么办。
这个问题能以如下的方式正式建立你將会去滑雪,滑雪天数d未知我们现在寻找一种算法,使你不知道d时使用这种算法和你事先知道d时选取的最优方案之间的花费比率最低這个问题普遍在最坏情况下分析,即算法是固定的我们寻找所有可能d值在最坏情况下的性能尤其是,没有针对d的分布的假设(很显然根据d分布情况,会选择不同分析和不同的方案)
收支平衡算法会指导你头9天租赁,如果第十天继续滑雪那么购买滑雪板。如果你在头9忝过程中终止滑雪那么你的花费和你事先知道你滑雪天数的花费相同。如果你刚好滑雪10天后停止你的花费是19美金,比你事先知道滑雪忝数的花费多出了90%这是收支平衡算法的最坏情况。收支平衡算法是针对此问题已知的最好的确定性算法
当然。比如你能抛硬币决定。如果硬币正面朝上你在第8天购买滑雪板,否则在第10天购买。这是一个随机化算法的例子显而易见,在不考虑滑雪天数情况下总婲费的期望最多比你事先知道滑雪天数多80%。如果你滑雪10天你的花费的期望值是1/2 [7 +10] + 1/2 [9+10] = 18 美金,比起前面的90%来仅为80%
相应于无视对手(oblivious adversary)的最好的隨机化算法是根据下面的分布p随机选择天数i,租赁i-1天若第i天继续滑雪则购买滑雪板。Karlin等人首先提出了这个算法的分布