组合优化问题举例

Seawind2012

1 N0 t& D9 V# N( k# |TSP旅行售货员问题

5 J' M! G+ d+ c& F+ A6 {* {2 ]   从某个城市出发，经过n个指定的城市，每个城市只能且必须经过一次，最后回到出发城市，如何安排旅行商的行走路线以使总路程最短？

- t1 @$ X, x; R2 P6 x: o7 H约束机器排序问题

2 |, H! F9 u3 @( B+ X7 e- t     n个加工量为di(i=1,2,… n)的产品在一台机器上加工，机器在第t个时段的工作能力为ct,完成所有产品加工的最少时段数。
* G  `6 b6 g  ~5 M- j. p
指派问题

    一家公司经理准备安排N名员工去完成N项任务，每人一项。由于各员工的特点不同，不同的员工去完成同一项任务时获得的回报是不同的。如何分配工作方案可以获得最大收益？
: L" F5 O: _; y  W* I
0-1背包问题
/ q) c- t( I; A( r2 }0 U: o
7 F# L3 P! A  J   设有一个容积为b的背包，n个体积分别为ai(i=1,2,… n),价值分别为ci (i=1,2,… n)的物品，如何以最大的价值装包？
! w0 y: j* M: f- X8 m9 @. A* x3 O
2 F; u' a" z* H% @5 I* K装箱问题

5 Q" x2 g0 Z- b+ ^   如何用个数最少的尺寸为1的箱子装进n个尺寸不超过1的物品？

SAT问题

8 K# j- A- J' z+ S2 s8 Y0 O: i; j     称判定一个公式是否存在一个模型的问题为可满足性问题(以后简称为SAT问题)。如果一个公式存在模型，则称该公式是可满足的，否则称为不可满足的。

: h" k/ D* R" ~5 j# n! @, b4 K皇后问题

+ \( K: x# f3 F& {! V    在n×n的国际象棋棋盘上，摆放n个皇后，使得n个皇后之间不能相互“捕捉”？

arial

重要的基础

wuxiedanran

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

龙龙鲸鱼寜

谢谢诶楼主分享