组合优化问题举例

Seawind2012

$ }! @2 h5 Q# z( c8 G8 L+ a  BTSP旅行售货员问题
$ x. b0 B( @0 h/ q" j4 [: L& a
   从某个城市出发，经过n个指定的城市，每个城市只能且必须经过一次，最后回到出发城市，如何安排旅行商的行走路线以使总路程最短？
( S6 Y) f: j7 N, h  `9 P1 P
约束机器排序问题

# G  D$ g5 t/ H) D     n个加工量为di(i=1,2,… n)的产品在一台机器上加工，机器在第t个时段的工作能力为ct,完成所有产品加工的最少时段数。

0 |/ \  e  K5 V指派问题
$ y0 @$ s# u8 r" o+ d! c8 k
" s; g+ c) @6 b% Z- K    一家公司经理准备安排N名员工去完成N项任务，每人一项。由于各员工的特点不同，不同的员工去完成同一项任务时获得的回报是不同的。如何分配工作方案可以获得最大收益？
9 W: A* m; k" [% s  y
( k( l0 i- E; M7 T  V6 Z0-1背包问题
' C9 ^! J0 b' n: _& ^
" U% G* |0 n" o$ C% _   设有一个容积为b的背包，n个体积分别为ai(i=1,2,… n),价值分别为ci (i=1,2,… n)的物品，如何以最大的价值装包？

9 f# `! I5 J+ `装箱问题

   如何用个数最少的尺寸为1的箱子装进n个尺寸不超过1的物品？
( @) p4 T1 W) {3 N: a+ q& c+ R1 u8 B
SAT问题
- e+ ~3 w* ?1 t6 u+ F' A& f
     称判定一个公式是否存在一个模型的问题为可满足性问题(以后简称为SAT问题)。如果一个公式存在模型，则称该公式是可满足的，否则称为不可满足的。
: j- |9 Y! V$ K9 H
( F! \. D2 G& m4 W皇后问题
4 L/ K) z* F% g! |5 p9 u7 p# b# }
# Z4 H% [' N$ \* A6 C/ s    在n×n的国际象棋棋盘上，摆放n个皇后，使得n个皇后之间不能相互“捕捉”？

arial

重要的基础

wuxiedanran

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

龙龙鲸鱼寜

谢谢诶楼主分享
: h; R+ U0 ^8 S. t4 j) ], O