组合优化问题举例

Seawind2012

TSP旅行售货员问题

" {4 z- a, F: S  E   从某个城市出发，经过n个指定的城市，每个城市只能且必须经过一次，最后回到出发城市，如何安排旅行商的行走路线以使总路程最短？
3 ?: q  a7 p8 M! K0 H
8 Y0 u8 }7 @: K1 f- z' B3 E约束机器排序问题

     n个加工量为di(i=1,2,… n)的产品在一台机器上加工，机器在第t个时段的工作能力为ct,完成所有产品加工的最少时段数。
) v) S' K7 G6 A5 V- _2 K$ }
* q! v" l( G3 [$ i1 e指派问题
: A! t$ @9 T$ n% w
    一家公司经理准备安排N名员工去完成N项任务，每人一项。由于各员工的特点不同，不同的员工去完成同一项任务时获得的回报是不同的。如何分配工作方案可以获得最大收益？

# {9 [2 f' |6 E- R% y0-1背包问题

, c* N2 k/ c! E* q   设有一个容积为b的背包，n个体积分别为ai(i=1,2,… n),价值分别为ci (i=1,2,… n)的物品，如何以最大的价值装包？
* M9 F7 n' D$ y+ @2 D5 B
. y% v# U+ f& q. a  R: E" ]: K3 h装箱问题
9 K4 O. H4 B" E4 O# T2 ]1 q- O
   如何用个数最少的尺寸为1的箱子装进n个尺寸不超过1的物品？
" p1 z7 ^( h( b5 {; K7 V- g
SAT问题
! C& F' H& U8 H/ y8 u  }) F/ \
- Y8 b& t2 t: ]5 R3 _1 B     称判定一个公式是否存在一个模型的问题为可满足性问题(以后简称为SAT问题)。如果一个公式存在模型，则称该公式是可满足的，否则称为不可满足的。

1 B* l" d' U, m) o+ w" _皇后问题

    在n×n的国际象棋棋盘上，摆放n个皇后，使得n个皇后之间不能相互“捕捉”？

arial

重要的基础

wuxiedanran

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

龙龙鲸鱼寜

谢谢诶楼主分享