作者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