建模方法（二）-组合优化问题的定义

组合最优化是通过对数学方法的研究去寻找处理离散事件的最优编排、分组、次序或筛选等问题的优化方法。实际上就是从有限个离散状态中选取最好的状态。模型如下：



从模型可看出组合优化问题是一个规划问题（在一定条件下，求解目标函数的最大值最小值，这类问题叫做数学规划，它是运筹学里的重要内容）。解决这类优化问题的方法有
各种规划(线性、非线性、目标、整数、随机、模糊)、遗传算法、退火算法、神经网络、搜索算法、拉格朗日松弛算法
等。就像我们在算法分析与设计课程中学习到的回溯法，分支定界法都可以用于解决这类优化问题。

先来说说最优化问题，它一般分为两大类：一类是具有连续型的变量，另一类是具有离散型的变量，后一类被称为组合最优化，组合优化问题有时又称为
离散优化(Discrete Optimization)问题。像简单的背包问题，TSP旅行商问题都是组合优化问题。

组合最优化的特点就是定义域集合为有限点集。由直观可知，只要将定义域D中的有限个点逐一判别是否满足约束，并比较目标函数的大小，就可以得到该问题的最优解，这就是
枚举法
。对于某些优化问题可以通过枚举法得到最优解，这在问题规模较小时是十分有效的，考虑的点也是非常全面的。每一个组合最优化问题都可以通过枚举的方法求得最优解，然而枚举是以时间为代价的，有的枚举时间还可以接受，有的则不可能接受。

应用方面，比如将连续优化问题通过设定步长转换为离散优化问题，就可以使用组合优化问题的方法求解了。

• « 上一篇：读书笔记17：Adversarial Attacks on Neural Networks for Graph Data
• » 下一篇：Flutter初体验