组合优化问题举例

Seawind2012

TSP旅行售货员问题
; s2 ~/ n9 o, G8 c' x
   从某个城市出发，经过n个指定的城市，每个城市只能且必须经过一次，最后回到出发城市，如何安排旅行商的行走路线以使总路程最短？

约束机器排序问题
5 _4 \6 j9 {( H2 B' }: b5 ?
2 A+ P* l5 E' o2 E4 F- ^% C     n个加工量为di(i=1,2,… n)的产品在一台机器上加工，机器在第t个时段的工作能力为ct,完成所有产品加工的最少时段数。
/ i; ]- l& Z$ ?% V  M" L
  E3 G) w$ R1 o$ y9 y, E% s% w指派问题

% [9 K. F% a5 `3 c+ s4 b    一家公司经理准备安排N名员工去完成N项任务，每人一项。由于各员工的特点不同，不同的员工去完成同一项任务时获得的回报是不同的。如何分配工作方案可以获得最大收益？
2 K3 `& O/ N9 x+ [- s( E$ q+ y
0-1背包问题
, A' ^* G5 P8 [$ F: A! G2 T9 I( x
, \7 w  B% L: h2 K: f0 l: r8 S   设有一个容积为b的背包，n个体积分别为ai(i=1,2,… n),价值分别为ci (i=1,2,… n)的物品，如何以最大的价值装包？
$ Y+ u8 ^, y3 @4 l
装箱问题
7 n' e1 s# a( b: ?1 y0 v
   如何用个数最少的尺寸为1的箱子装进n个尺寸不超过1的物品？
8 H6 `) F0 P; @! G" R/ y/ f
1 g* f# h& H( P; y! U: k* L4 BSAT问题
4 Q  R5 }1 y! h# Z
+ h, s( x7 N- A4 C: ^! B* ]     称判定一个公式是否存在一个模型的问题为可满足性问题(以后简称为SAT问题)。如果一个公式存在模型，则称该公式是可满足的，否则称为不可满足的。
: U) U8 I5 Y% v/ ?+ W7 M! G( }
! z, ]& Z6 o% x, d皇后问题

5 d- o; H" L8 V( \1 S3 ]/ q    在n×n的国际象棋棋盘上，摆放n个皇后，使得n个皇后之间不能相互“捕捉”？

龙龙鲸鱼寜

谢谢诶楼主分享

wuxiedanran

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

arial

重要的基础