组合优化问题举例

Seawind2012

7 G2 ~$ _; A- S& d$ H+ b' aTSP旅行售货员问题

   从某个城市出发，经过n个指定的城市，每个城市只能且必须经过一次，最后回到出发城市，如何安排旅行商的行走路线以使总路程最短？

; k# Q- x  y# l3 V4 q* r约束机器排序问题

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

# C3 Z8 L& U% O& C) a7 K指派问题

    一家公司经理准备安排N名员工去完成N项任务，每人一项。由于各员工的特点不同，不同的员工去完成同一项任务时获得的回报是不同的。如何分配工作方案可以获得最大收益？

" u. t5 I3 s# r3 n5 M5 A) y- p0-1背包问题
) M& U. D+ K: F; m
( n, _6 \. [7 @, `1 U   设有一个容积为b的背包，n个体积分别为ai(i=1,2,… n),价值分别为ci (i=1,2,… n)的物品，如何以最大的价值装包？

! }  I3 m. c$ N3 T( h装箱问题
" Y! P# {8 m5 `
   如何用个数最少的尺寸为1的箱子装进n个尺寸不超过1的物品？
7 N! v9 M9 z% U, F1 J! f0 I
SAT问题

. G  M( b5 _3 c: ~$ i     称判定一个公式是否存在一个模型的问题为可满足性问题(以后简称为SAT问题)。如果一个公式存在模型，则称该公式是可满足的，否则称为不可满足的。

皇后问题
% {& D# ?5 m( i5 Q0 V1 l6 L
! u$ ]" q8 ]- V' D+ w& `    在n×n的国际象棋棋盘上，摆放n个皇后，使得n个皇后之间不能相互“捕捉”？

龙龙鲸鱼寜

谢谢诶楼主分享
2 L+ m, C8 M4 {# E6 g

wuxiedanran

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

arial

重要的基础