组合优化问题举例

Seawind2012

TSP旅行售货员问题
- l+ x9 \+ j  ?% x$ T. N
   从某个城市出发，经过n个指定的城市，每个城市只能且必须经过一次，最后回到出发城市，如何安排旅行商的行走路线以使总路程最短？
( `' a# o. l" A+ d  B
+ C" V  D8 P- _* p) c约束机器排序问题
/ i, F% O( S$ s
' v  @  |7 U& ?     n个加工量为di(i=1,2,… n)的产品在一台机器上加工，机器在第t个时段的工作能力为ct,完成所有产品加工的最少时段数。
# D8 K0 ~! X  a( O8 m! n2 W1 V! V
指派问题
$ `$ [9 d8 K2 R; D1 V8 Z
    一家公司经理准备安排N名员工去完成N项任务，每人一项。由于各员工的特点不同，不同的员工去完成同一项任务时获得的回报是不同的。如何分配工作方案可以获得最大收益？
' H1 m: G+ ?: f& \. ~0 l7 }
0-1背包问题

   设有一个容积为b的背包，n个体积分别为ai(i=1,2,… n),价值分别为ci (i=1,2,… n)的物品，如何以最大的价值装包？

4 g4 u$ K8 _4 w: p: J装箱问题
" [" m6 J; h" l( k
& [8 o4 b0 z0 I5 \6 J4 C   如何用个数最少的尺寸为1的箱子装进n个尺寸不超过1的物品？
+ q) p8 ~- {! _  M8 X5 f
7 G4 f5 f/ n; z! ~% J; X  Y* mSAT问题

3 Z; S. K% Z3 E( T     称判定一个公式是否存在一个模型的问题为可满足性问题(以后简称为SAT问题)。如果一个公式存在模型，则称该公式是可满足的，否则称为不可满足的。
4 l5 Q. A# I" P$ _  a, d
$ f6 [3 a8 V1 Y皇后问题
3 h9 c, Z5 h, p: N, g, l) v
    在n×n的国际象棋棋盘上，摆放n个皇后，使得n个皇后之间不能相互“捕捉”？

arial

重要的基础

wuxiedanran

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

龙龙鲸鱼寜

谢谢诶楼主分享
9 D- J. e! a7 _1 g( x7 G; T