组合优化问题举例

Seawind2012

4 J0 o9 S; a: s# u( y3 Y, [3 M8 i) ]TSP旅行售货员问题
) o3 q: L; ~6 d" s- [  n2 [0 C- `) U  y
   从某个城市出发，经过n个指定的城市，每个城市只能且必须经过一次，最后回到出发城市，如何安排旅行商的行走路线以使总路程最短？
; w: o2 v7 d7 g: `; G, ]
约束机器排序问题
" Y9 r) _1 C9 Z% R2 J
     n个加工量为di(i=1,2,… n)的产品在一台机器上加工，机器在第t个时段的工作能力为ct,完成所有产品加工的最少时段数。

, a1 C- b/ M9 B: q指派问题
7 s- k! a  ?9 R+ h' g% z$ d
- I/ Z1 s% X* j    一家公司经理准备安排N名员工去完成N项任务，每人一项。由于各员工的特点不同，不同的员工去完成同一项任务时获得的回报是不同的。如何分配工作方案可以获得最大收益？
  Q6 q3 R$ @; r! _* z# v, G2 f
( n" T) P. M# O3 v2 Z8 u0-1背包问题
+ v/ D+ u" ~1 P+ J7 O3 R
   设有一个容积为b的背包，n个体积分别为ai(i=1,2,… n),价值分别为ci (i=1,2,… n)的物品，如何以最大的价值装包？
' `: U6 s2 P- ]
装箱问题
" V: @2 P  e& p4 Y% p6 W( Q
( M% o5 c* G: C+ R7 P$ K% @   如何用个数最少的尺寸为1的箱子装进n个尺寸不超过1的物品？
( v% B- r+ F3 {# Q" F; p- M
SAT问题
* u% j% N. u' y9 ~
( M: P! |" p0 `$ n7 u& G& I) _     称判定一个公式是否存在一个模型的问题为可满足性问题(以后简称为SAT问题)。如果一个公式存在模型，则称该公式是可满足的，否则称为不可满足的。

$ ^8 G, K; A6 E$ O( y% l' j皇后问题
# c$ a: v# l) |9 r3 o# p7 g9 o* ^0 U
' D7 z+ c0 U6 h1 j    在n×n的国际象棋棋盘上，摆放n个皇后，使得n个皇后之间不能相互“捕捉”？

arial

重要的基础

wuxiedanran

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

龙龙鲸鱼寜

谢谢诶楼主分享
4 Q6 b9 k5 J! A' {2 ^3 r