作者sophialiege (需要更廣泛的閱讀)
看板ACMCLUB
標題Re: 真是太亂了 @"@
時間Tue Sep 14 00:06:56 2004
※ 引述《smartboy (小光光)》之銘言：
: ※ 引述《sophialiege (爬回來了)》之銘言：
: : 方案二
: : 用N-space的Convex Hull來解,不過很怕求點上precision的問題產生
: 給一堆不等式, 要怎麼用 convex hull 來解?
: (先討論二維的就好)
利用Convex Hull處理交點,決定出最後的區域
再利用此區域和每條直線所貢獻的交點,或直線,或更高維
假如他是有用的,那麼他的交?務必會在解的區域裡出現
: 類似這個問題同時問 chhsiao 的旋轉法:
: 要怎麼做二維的題目?
: 二維的線性規劃我記得有簡單的作法, 不過忘是怎樣了 XD
: 這題我想到的是, 若會 simplex algorithm 的話
: 令 input 是 f_i(x)<=c_i, 1<=i<=n
: 則
: for i=1 to n
: 用 simplex 求 {
: maximize f_i(x)
: subject to f_j(x)<=c_j, 1<=j<=n
: }
: 解出 x_0, 若 f_i(x_0)<c_i 則 equation f_i 可以丟掉
: 不過不會 simplex algorithm 的問題比較大...:P
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.112.250.175