组合优化问题举例

Seawind2012

TSP旅行售货员问题
. o- P% L9 F, q1 t0 {
   从某个城市出发，经过n个指定的城市，每个城市只能且必须经过一次，最后回到出发城市，如何安排旅行商的行走路线以使总路程最短？
8 r, x( X4 r0 }, }
; x# E8 N, L% r; x: I+ ~& T约束机器排序问题
4 R% h' \5 s! E+ o8 Y( Q+ R
  K/ {: J8 [9 x7 @3 ]/ t     n个加工量为di(i=1,2,… n)的产品在一台机器上加工，机器在第t个时段的工作能力为ct,完成所有产品加工的最少时段数。
( X2 j2 e3 P6 z+ d* D
6 l! W" M/ s, ~5 S9 t6 S3 R指派问题
8 x( _6 q9 ~( x
1 P' E- R2 C6 f1 M' M$ q/ c: B    一家公司经理准备安排N名员工去完成N项任务，每人一项。由于各员工的特点不同，不同的员工去完成同一项任务时获得的回报是不同的。如何分配工作方案可以获得最大收益？

0-1背包问题

   设有一个容积为b的背包，n个体积分别为ai(i=1,2,… n),价值分别为ci (i=1,2,… n)的物品，如何以最大的价值装包？
& I( k3 i+ y; X% r( ^0 g0 g+ _
装箱问题

1 X: Y; J$ F* G& _3 R   如何用个数最少的尺寸为1的箱子装进n个尺寸不超过1的物品？

SAT问题

2 `8 l6 H( m# ]( h8 u  l# W0 q     称判定一个公式是否存在一个模型的问题为可满足性问题(以后简称为SAT问题)。如果一个公式存在模型，则称该公式是可满足的，否则称为不可满足的。

# Q$ B8 [  p' v  k7 ^, V皇后问题

5 A7 [' Z3 O2 N5 q' c2 T  i5 K3 [    在n×n的国际象棋棋盘上，摆放n个皇后，使得n个皇后之间不能相互“捕捉”？

arial

重要的基础

wuxiedanran

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

龙龙鲸鱼寜

谢谢诶楼主分享
( X6 ?. S  ?2 e( k' t+ }8 f3 w7 A