组合优化问题举例

Seawind2012

TSP旅行售货员问题

& a; K% [! s( `3 u0 p0 G9 y   从某个城市出发，经过n个指定的城市，每个城市只能且必须经过一次，最后回到出发城市，如何安排旅行商的行走路线以使总路程最短？
1 M4 F6 `% l5 N1 A& ]
: K" ]# ]) _6 W: A2 h& X4 W- `: R2 D: N约束机器排序问题
* C/ N* c" T! \7 n, k
, O! A( A; T- q) [     n个加工量为di(i=1,2,… n)的产品在一台机器上加工，机器在第t个时段的工作能力为ct,完成所有产品加工的最少时段数。

& V# v) U  B: x5 \3 K- P指派问题
& q0 a& B9 F, A: l; e
" w- U  A( F! e4 C    一家公司经理准备安排N名员工去完成N项任务，每人一项。由于各员工的特点不同，不同的员工去完成同一项任务时获得的回报是不同的。如何分配工作方案可以获得最大收益？

0-1背包问题
2 Z1 y) D/ T3 ]: G7 S
   设有一个容积为b的背包，n个体积分别为ai(i=1,2,… n),价值分别为ci (i=1,2,… n)的物品，如何以最大的价值装包？
9 p  y( @+ q+ o& ]
1 W, P8 L& E$ g. m, f/ s  A9 O: ^装箱问题
0 D/ k  n- P0 J8 l, c1 M
( g6 F" ~+ Q$ N  {1 i   如何用个数最少的尺寸为1的箱子装进n个尺寸不超过1的物品？

SAT问题

# A: _, S: Q: A     称判定一个公式是否存在一个模型的问题为可满足性问题(以后简称为SAT问题)。如果一个公式存在模型，则称该公式是可满足的，否则称为不可满足的。

皇后问题
! y8 Q! z7 w: f! x: e
3 t5 r; x, t5 T2 @    在n×n的国际象棋棋盘上，摆放n个皇后，使得n个皇后之间不能相互“捕捉”？

arial

重要的基础

wuxiedanran

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

龙龙鲸鱼寜

谢谢诶楼主分享