组合优化问题举例

Seawind2012

TSP旅行售货员问题

  H( A3 X, `6 u/ E- h8 ~   从某个城市出发，经过n个指定的城市，每个城市只能且必须经过一次，最后回到出发城市，如何安排旅行商的行走路线以使总路程最短？
0 i6 q2 x' J2 t1 ^5 g
约束机器排序问题
3 s- V" @' G: k  G& f
     n个加工量为di(i=1,2,… n)的产品在一台机器上加工，机器在第t个时段的工作能力为ct,完成所有产品加工的最少时段数。

* F+ x! Y( E& \0 M指派问题
8 T) b" R! Y, V/ O4 h
" ^" q1 m; h- S- w1 h    一家公司经理准备安排N名员工去完成N项任务，每人一项。由于各员工的特点不同，不同的员工去完成同一项任务时获得的回报是不同的。如何分配工作方案可以获得最大收益？
& `+ y# L9 u' k3 o4 l
0-1背包问题

   设有一个容积为b的背包，n个体积分别为ai(i=1,2,… n),价值分别为ci (i=1,2,… n)的物品，如何以最大的价值装包？

装箱问题
8 R% t$ ?6 f( Z- h% x/ b
   如何用个数最少的尺寸为1的箱子装进n个尺寸不超过1的物品？
& X9 z3 b4 o! p4 ~' [! I
5 r7 q7 J+ \/ W9 s- JSAT问题
' I4 d( [0 e/ V/ V$ f( B3 n
$ L6 H, i) d2 v, q' H     称判定一个公式是否存在一个模型的问题为可满足性问题(以后简称为SAT问题)。如果一个公式存在模型，则称该公式是可满足的，否则称为不可满足的。
" v8 |" t  p9 ^5 Y
- ]7 f+ E% t6 s9 a皇后问题
$ R8 {$ z: p3 ]# s$ W; I
    在n×n的国际象棋棋盘上，摆放n个皇后，使得n个皇后之间不能相互“捕捉”？

arial

重要的基础

wuxiedanran

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

龙龙鲸鱼寜

谢谢诶楼主分享