最佳化問題
![本頁使用了標題或全文手工轉換](http://images.weserv.nl/?url=//upload.wikimedia.org/wikipedia/commons/thumb/c/cd/Zh_conversion_icon_m.svg/35px-Zh_conversion_icon_m.svg.png)
數學、工程學、計算機科學和經濟學領域中,最佳化問題(英語: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].
|
|