在线优化

在线优化是优化理论的一个领域，在计算机科学和运筹学中比较流行，它处理对未来没有或不完全了解的优化问题（在线）。这类问题被称为在线问题，并被视为与假设有完整信息的经典优化问题（离线）相对立。对在线优化的研究可以区分为基于逐件输入的多个决策的在线问题和那些只做一次决策的问题。一般来说，在线算法的输出与相应的离线算法的解决方案进行比较，后者必然总是最优的，并且事先知道整个输入（竞争分析）。在许多情况下，目前的决策（例如资源分配）必须在对未来不完全了解的情况下做出，或者对未来的分布假设并不可靠。在这种情况下，可以使用在线优化，这与其他方法如稳健优化、随机优化和马尔科夫决策过程不同。

这个问题的目标是使到达一个加权图中的目标的成本最小化，其中一些边是不可靠的。

这个问题的最坏情况是，所有不可靠的边都失败了，这个问题就变成了通常的最短路径问题。在竞争分析的帮助下，可以对该问题进行另一种分析。对于这种分析方法，离线算法事先知道哪些边会失败，目标是使在线和离线算法的性能之间的比率最小。