组合优化问题举例

Seawind2012

TSP旅行售货员问题
8 p) ^, d( I, ]) d) K% s! [: x" `
   从某个城市出发，经过n个指定的城市，每个城市只能且必须经过一次，最后回到出发城市，如何安排旅行商的行走路线以使总路程最短？
/ G, P! e5 e1 _( q6 L0 H9 H
约束机器排序问题
9 O- K. F* z0 J! E
     n个加工量为di(i=1,2,… n)的产品在一台机器上加工，机器在第t个时段的工作能力为ct,完成所有产品加工的最少时段数。

8 G, Z" n. a$ M指派问题
/ \0 [3 L8 g* v" y; g) |: s' C0 W
    一家公司经理准备安排N名员工去完成N项任务，每人一项。由于各员工的特点不同，不同的员工去完成同一项任务时获得的回报是不同的。如何分配工作方案可以获得最大收益？

0-1背包问题
' v) R& u9 M8 z! t) {' r2 ]* l9 }
- X' d! H% F# h   设有一个容积为b的背包，n个体积分别为ai(i=1,2,… n),价值分别为ci (i=1,2,… n)的物品，如何以最大的价值装包？

装箱问题

; k+ g7 g& a5 y5 c   如何用个数最少的尺寸为1的箱子装进n个尺寸不超过1的物品？
  g, r7 s( p8 q5 S2 Y: u: J7 f$ G
/ |7 E6 E2 M2 j# \- ~2 ]5 ?) @: qSAT问题
7 I+ L  A2 [6 A: Q, B2 b7 b; d
6 `( c% a% _* l2 t     称判定一个公式是否存在一个模型的问题为可满足性问题(以后简称为SAT问题)。如果一个公式存在模型，则称该公式是可满足的，否则称为不可满足的。
9 N8 m4 c" N3 N
皇后问题

* n; H$ a' T3 I0 L, r    在n×n的国际象棋棋盘上，摆放n个皇后，使得n个皇后之间不能相互“捕捉”？

arial

重要的基础

wuxiedanran

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

龙龙鲸鱼寜

谢谢诶楼主分享
2 Z6 Q7 H, W1 p