h**x
发帖数: 34 | 1 麻烦想了解一下诸位在实际工作（比如，金融，生物，工程计算，等领域）中有需要解
决某 NP-complete 问题的吗？
如果有，能否说明一下具体是哪个 NPC problem，以及 problem size 有多大。
谢谢！ | G*****9
发帖数: 3225 | 2 我来抛砖。但我只懂得工程领域的东东。生物和金融的不懂。
问题1：VRP。假设你提供物流服务，所在城市的任何一个用户，都可以提前一天给出订
单，购买药品、食品、图书、家具或是whatever。每个用户都给出自己的在第二天的
deadline。假设你只有各类型卡车200辆，每天如何调度这200辆卡车满足客户要求？每
天的订单量大约在接近8,000左右。
问题2：Health Care。有一家医院，有500病人住院，他们对护士的需求依据自身病症
决定，不通的时间甚至可能有不同的需求。医院有护士。每个护士的技能不通，愿意工
作的时间段不通。比如有些人不愿意加夜班，有些人周末不工作。每个护士连续工作的
时间有限制等等。要求做一个排班的算法，在满足所有护士和病人的需求的同时，最小
化所需支付给护士的工资。注：护士不够用可以从别的医院调——费用嘛，更贵。
问题3：资金链与Pipeline。药品研制在美国是一件高风险、高回报的行业。一个药品
的研发，往往从几个实验阶段到最后的FDA审批，需要几个步骤。每一个步骤，公司都
需要考虑投资。Generally speaking, 投得多可以增加成功率，但也有可能增加资金的
风险。而一个药厂需要面对的是10多个药品，甚至更多的研发。如何分配资金？注意，
每一个药品的每一个研发阶段都可能会有失败的风险。当然同时公司自己的商业情报分
析也给出了一些其他的information，比如可以购买一些市场里刚刚出现的化合物，来
缩短某一种药品的研发周期。如何分析回报与风险之间的关系，算是一个比较麻烦的问
题。
倒是知道有用优化算法分析分子式的，发表在Science上。金融嘛，华尔街应该不需要
对付NPC的算法。商业银行里面，我朋友说有，但是大家不care解算效果。用最通俗的
启发式算法来处理就够了——最好是那种文科生都可以掌握的、并且还能解释几句的算
法。 |
|
