组合优化问题举例

Seawind2012

4 [- F$ L1 A1 t% ~. O% FTSP旅行售货员问题
/ r3 |3 i) Q7 V; j0 y
0 e0 P. r9 {( y  g- N; k   从某个城市出发，经过n个指定的城市，每个城市只能且必须经过一次，最后回到出发城市，如何安排旅行商的行走路线以使总路程最短？
& d/ R. R- D  j' \% W5 z* s5 k/ u
& I- u4 P+ V9 N5 d! Z1 A; I# ~约束机器排序问题
+ _& b, ?8 B* Q
2 s0 x% m' w* Q/ p     n个加工量为di(i=1,2,… n)的产品在一台机器上加工，机器在第t个时段的工作能力为ct,完成所有产品加工的最少时段数。

4 S* O+ Y* o8 a& Z. _4 k+ W- y指派问题

    一家公司经理准备安排N名员工去完成N项任务，每人一项。由于各员工的特点不同，不同的员工去完成同一项任务时获得的回报是不同的。如何分配工作方案可以获得最大收益？

/ T( {" `4 n  _0-1背包问题
' Z+ ?4 p, @7 j* w' c4 G/ N& @
   设有一个容积为b的背包，n个体积分别为ai(i=1,2,… n),价值分别为ci (i=1,2,… n)的物品，如何以最大的价值装包？

装箱问题

   如何用个数最少的尺寸为1的箱子装进n个尺寸不超过1的物品？
9 t) v8 |+ `6 q3 X; A% r( x1 v! L
+ C8 r7 s5 V4 rSAT问题
( z* t/ D4 J6 e1 q" E. u! N2 B
     称判定一个公式是否存在一个模型的问题为可满足性问题(以后简称为SAT问题)。如果一个公式存在模型，则称该公式是可满足的，否则称为不可满足的。

" p1 b2 ]4 a# r" _皇后问题

8 v; z5 c" q9 N' y7 ~/ }+ x& `! m0 j    在n×n的国际象棋棋盘上，摆放n个皇后，使得n个皇后之间不能相互“捕捉”？

龙龙鲸鱼寜

谢谢诶楼主分享

wuxiedanran

还是洗洗，回家睡觉吧……

arial

重要的基础