组合优化问题举例

Seawind2012

0 D, M2 f0 I9 O& wTSP旅行售货员问题

2 z  ^  v7 W" Y( H   从某个城市出发，经过n个指定的城市，每个城市只能且必须经过一次，最后回到出发城市，如何安排旅行商的行走路线以使总路程最短？

% d9 b1 E6 `- |9 |. C; u约束机器排序问题

$ l3 T0 ]8 f. h9 z2 c     n个加工量为di(i=1,2,… n)的产品在一台机器上加工，机器在第t个时段的工作能力为ct,完成所有产品加工的最少时段数。

9 W0 t8 U6 [' R% v3 U! @指派问题

    一家公司经理准备安排N名员工去完成N项任务，每人一项。由于各员工的特点不同，不同的员工去完成同一项任务时获得的回报是不同的。如何分配工作方案可以获得最大收益？
* y7 A4 l3 Z* u( ^
1 G4 q" S+ X# R- u6 l! h% M% ^0-1背包问题

   设有一个容积为b的背包，n个体积分别为ai(i=1,2,… n),价值分别为ci (i=1,2,… n)的物品，如何以最大的价值装包？
* _$ Z/ r7 s, F% W$ d. j; m2 {
' L, M7 ^: s" G' z2 s% z1 |装箱问题

# c* Y6 U0 y; F# G0 n, _# f   如何用个数最少的尺寸为1的箱子装进n个尺寸不超过1的物品？
  n( A3 P  W8 ]0 x$ H7 J4 r7 v
! U/ m; O# E7 |: y) m9 ]SAT问题
; V) B% g3 P6 W0 O% O
' e4 J& }1 C8 U' }( v9 E4 Q4 b1 A     称判定一个公式是否存在一个模型的问题为可满足性问题(以后简称为SAT问题)。如果一个公式存在模型，则称该公式是可满足的，否则称为不可满足的。
+ {2 f: H" Q: o: b
皇后问题

& U( {3 U! ~: ]& M7 F    在n×n的国际象棋棋盘上，摆放n个皇后，使得n个皇后之间不能相互“捕捉”？

arial

重要的基础

wuxiedanran

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

龙龙鲸鱼寜

谢谢诶楼主分享
) [0 ?3 X( H8 U' X; \% u