组合优化问题举例

Seawind2012

# v( i, G( _& |; |8 S# m* wTSP旅行售货员问题
1 c  d* [& t& a) t5 ^* F5 ]
   从某个城市出发，经过n个指定的城市，每个城市只能且必须经过一次，最后回到出发城市，如何安排旅行商的行走路线以使总路程最短？

5 ]1 A: z6 H" s( o% q1 ^1 z约束机器排序问题
* P: K. M5 ]/ z; R4 o; H
5 o" l4 i& ?$ k# f  @     n个加工量为di(i=1,2,… n)的产品在一台机器上加工，机器在第t个时段的工作能力为ct,完成所有产品加工的最少时段数。
: x) p8 I0 H( D2 k8 i
: a4 J1 E) c7 |' I7 G  a指派问题
; m# w3 t' q+ _  v6 c
& i) m! C  w( l8 y9 S    一家公司经理准备安排N名员工去完成N项任务，每人一项。由于各员工的特点不同，不同的员工去完成同一项任务时获得的回报是不同的。如何分配工作方案可以获得最大收益？
0 d$ M! s9 o5 ~$ h# Y& \1 x7 @5 ]
1 p1 r& r: W- C0 T8 [" r0-1背包问题

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

装箱问题

# S1 I0 R5 L. I' Q   如何用个数最少的尺寸为1的箱子装进n个尺寸不超过1的物品？
& U/ G5 J! w8 y  _
6 x, y7 e/ Z+ t' i% j. uSAT问题

& G! ?, z9 ^: ?8 ?     称判定一个公式是否存在一个模型的问题为可满足性问题(以后简称为SAT问题)。如果一个公式存在模型，则称该公式是可满足的，否则称为不可满足的。

皇后问题

+ K9 u0 i  @5 n; \8 @9 `    在n×n的国际象棋棋盘上，摆放n个皇后，使得n个皇后之间不能相互“捕捉”？

arial

重要的基础

wuxiedanran

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

龙龙鲸鱼寜

谢谢诶楼主分享