组合优化问题举例

Seawind2012

) G" g( G2 S1 R7 a) [1 uTSP旅行售货员问题
& t$ P& f, K, ~9 N
0 b) e, l( V0 d( ^  i6 f   从某个城市出发，经过n个指定的城市，每个城市只能且必须经过一次，最后回到出发城市，如何安排旅行商的行走路线以使总路程最短？
3 _7 `+ M  j8 B8 v
0 R' n4 R. O) A# T. z6 E约束机器排序问题
/ }- \. ?7 k2 I- X8 K' H' U; p
* s, f: L  E& b  G5 U9 A3 m5 C     n个加工量为di(i=1,2,… n)的产品在一台机器上加工，机器在第t个时段的工作能力为ct,完成所有产品加工的最少时段数。

指派问题
) N1 ^7 @" J4 L) u0 l% C  J& h
    一家公司经理准备安排N名员工去完成N项任务，每人一项。由于各员工的特点不同，不同的员工去完成同一项任务时获得的回报是不同的。如何分配工作方案可以获得最大收益？

. O6 p4 a. M6 Y- Y0-1背包问题
% ^. |6 n( w% s  R  {
8 @7 e- U, P: {/ [4 Z   设有一个容积为b的背包，n个体积分别为ai(i=1,2,… n),价值分别为ci (i=1,2,… n)的物品，如何以最大的价值装包？
, c$ d) ~- O, [. c$ k6 c1 _/ j3 `
装箱问题

% j5 _/ g; R! F! C   如何用个数最少的尺寸为1的箱子装进n个尺寸不超过1的物品？

SAT问题

' m% h: d& Z6 K# D0 k1 u# p0 m( f8 y     称判定一个公式是否存在一个模型的问题为可满足性问题(以后简称为SAT问题)。如果一个公式存在模型，则称该公式是可满足的，否则称为不可满足的。
  O" r2 ^- p" @7 B' i6 c0 ^5 `
. J* Q  ~4 ^# m' m, S' p  r! T皇后问题

6 x. r3 T- z: Y. J    在n×n的国际象棋棋盘上，摆放n个皇后，使得n个皇后之间不能相互“捕捉”？

arial

重要的基础

wuxiedanran

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

龙龙鲸鱼寜

谢谢诶楼主分享