最佳化問題 - 维基百科,自由的百科全书
数学、工程学、计算机科学和经济学領域中,最佳化问题,或称优化问题(英語:Optimization problem)是指从所有可行解中找到最优良的解的问题。
最佳化问题和决定性问题(Decision problem)、功能性问题(Function problem)不同,最佳化问题是:从问题的多个解中,求出最佳解。像背包问题(考虑不同价格和重量的物品,以及可承载一定重量的背包,如何选择物品,使背包中的物品的总价最高)即属于最佳化问题。
连续优化问题
[编辑]若,则问题就是无约束优化问题。按照惯例,标准形定义了最小化问题。最大化问题可通过将目标函数取逆得到。
组合优化问题
[编辑]组合优化问题A是四元组,其中
我们的目标是为某可行值x找到最优解,即可行解y,且满足
对每个组合优化问题,有相应的决策问题:对某特定测度,是否存在可行解。例如,若有包含顶点u、v的图G,优化问题可能是“找到u到v使用最少边的路径”,答案可能是4;相应的决策问题是“是否有u到v的路径使用了少于10的边数”,可以用简单的“是否”回答。
近似算法领域中,算法是为问题找到近似最优解。因此,通常的决策的定义是不充分的,因为其只指定了可行解。虽然可以引入合适的决策问题,但描述为优化问题更自然。[2]
另见
[编辑]参考文献
[编辑]- ^ Boyd, Stephen P.; Vandenberghe, Lieven. Convex Optimization (pdf). Cambridge University Press. 2004: 129. ISBN 978-0-521-83378-3.
- ^ Ausiello, Giorgio; et al, Complexity and Approximation Corrected, Springer, 2003, ISBN 978-3-540-65431-5
外部链接
[编辑]- How Traffic Shaping Optimizes Network Bandwidth. IPC. 2016-07-12 [2017-02-13].
|
|