随机占线问题 第一步：基本概念与问题背景 随机占线问题研究决策者在信息不完全的情况下，面对按随机顺序到达的请求序列，需即时决定是否接受当前请求（占用资源），且无法回溯更改已拒绝的请求。其核心特征是"占线"性：决策者必须在未知未来请求信息时做出不可逆选择。典型例子包括： 租房问题 ：房东需在连续多天内决定是否接受当前租客报价，拒绝后该报价失效。 秘书问题 ：从随机顺序面试的候选人中选择最佳者，拒绝后无法召回。 资源分配 ：服务器需实时接受或拒绝随机到达的任务请求。 目标通常是最大化期望收益或最小化竞争比（占线算法与已知全信息最优解的比值）。 第二步：关键模型与竞争比分析 以经典 秘书问题 为例说明分析框架： 问题设定 ：n个候选人按随机顺序面试，每次面试后需立即决定录用（终止过程）或拒绝（不可召回）。目标是最大化选中最佳候选人的概率。 阈值策略 ：最优策略为"观察-选择"阶段法：拒绝前r个候选人作为观察期，之后遇到优于前r个的最佳候选人时立即录用。 竞争比计算 ：通过概率推导可得当r ≈ n/e时，成功概率趋近1/e ≈ 36.8%。这表明即使完全未知未来，仅通过阈值规则即可保证至少获得离线最优解（已知全序列选最佳者）的1/e期望收益。 第三步：扩展模型与随机优化技巧 基础模型可扩展至更复杂场景： 多目标权重 ：候选人带有权重（如能力评分），目标最大化期望权重和。需结合动态规划或蒙特卡洛树搜索求解阈值函数。 约束资源 ：如带宽分配中总容量有限，需在线接受请求且不超容量。常用贪心算法结合对偶价格调整竞争比。 随机过程建模 ：将请求到达建模为泊松过程或马尔可夫链，利用停时理论（如最优停止定理）推导阈值策略的闭合解。 第四步：与随机规划的联系与区别 随机占线问题虽属随机优化范畴，但与随机规划的区别显著： 信息结构 ：随机规划通常假设概率分布已知，可预先计算策略；占线问题强调序列到达的完全在线性。 策略形式 ：随机规划可能得到全序列策略，而占线策略必须是因果的（仅依赖当前及历史信息）。 应用场景 ：占线问题更适用于实时系统（如在线广告投放）、快速决策场景（如急诊分诊），而随机规划适用于周期较长的资源规划（如电力调度）。