优化问题，几乎可以涵盖方方面面，例如：如何配比使得化学配方效果最好、成本最优，如何组合用料使得用料最少，如何安排行车路线使得距离最短（TSP问题）、如何装载使得空间利用率最高（FTP问题、背包问题）等等。优化问题普遍来说都是NP难题，关于NP难题的数学定义这里不做赘述，只需知道NP难题在数据规模比较大时难以在有限时间内求解。
优化问题的官方定义为在某些约束条件下，决定某些可选择的变量应该取何值，使所选定的目标函数达到最优的问题。如果你觉得这话不好理解，可以参考我的解释：在有限制、有约束的情况下，从解的值域（也就是此问题所有可能取到的值）中，通过一定的方法，尽可能的搜索出最大值（或最小值）。解的值域通过解的评价函数取得，稍后会有对评价函数的解释，见例2。几乎所有的优化问题都可以套入这句话中，下面结合几个实例来参考。
例1：了解优化问题的基本思路
首先想象一个篮子，篮子里有打乱的十个数字1-10，我们现在的任务是从篮子中，搜索得到这十个数中除10之外最大的一个数值。计算机如何取？是不是直接把十个数字直接放入CPU中，一一比对就能轻易取得？对的，这不难想，这种方法叫做暴力求解。现在把我的这句话套进来。在有限制、有约束的情况下（除10之外），从解的值域中（1-10），通过一定的方法（暴力求解），尽可能的搜索出最大值（9）。
例2：了解评价函数在优化问题中的作用
现在，想象篮子里有十张卷子，卷子是打乱的，并且卷子尚无打分，从中找出除了小明同学之外的最高分。如何找到呢？没错，指定一套评分标准，对试卷进行一一评价，再进一步比对找到最高分。这套评分标准就是评价函数，通过评分标准可以获得卷子分数（0-100分区间的任意值），0-100就是值域。例1之所以不引入评价函数是因为有直观的数值，仅仅是举例用。
我们依然使用暴力求解，套入进来：在有限制、有约束的情况下（除小明同学之外，小明同学对不起），从解的值域中（0-100），通过一定的方法（暴力求解），尽可能的搜索出最大值（最高分97）。评价函数是对解的结构进行评价，计算出一个数值，有了数值之后，才能进行比对，优化，找到更好的答案。那它与目标函数有什么区别呢？可以理解目标函数是在经过评价函数评分之后的一堆数值中寻求最大最小值的函数。先有评价函数，后有目标函数。先有一群人的分数，后才能找到优秀的第一名同学。
然而，现实中的问题一定是复杂的，我们不能总是通过暴力求解来求解答案，假如现在篮子里共有一亿张试卷，单纯暴力求解，那搜寻得到最高分的过程一定是漫长的，并且计算机不一定能计算完。可是，这难不倒聪明的人类，见例3。
例3：了解邻域、启发式搜索思想
假设试卷共有十道选择题，观察篮子里的试卷发现，卷子的答案结构之间存在一定的规律。比如甲的答案AAAAAAAAAA，与乙的答案BAAAAAAAAAA之间，经过评分之后得到的分数之间只有一分差距，与之相比丙的答案BBBBBBBBBB，得到的分数一定与其相差甚远。这种情况称之为乙在甲的邻域中，以此类推，甲的邻域还有丁的答案AAAAAAAAAB等。凡是与甲的答案结构只有一个选择题之差的答案类型，我们都可以称之为甲的邻域。我们可以顺着这个方向进行搜寻，不再暴力遍历所有的试卷，而是一个邻域一个邻域的搜索，只评阅部分试卷，选出较为优秀同学，这种方法叫做启发式搜索。仅仅是甲的邻域，也会有很多试卷，我们从中随机选出一些，找出当中的最高分戊，再从戊的邻域中随机选出一些试卷，找出比戊分数更高的试卷，不断迭代这一过程，所搜索到试卷的分数就会越来越高，不断逼近最高分。
套入到我们的理解中，在有限制、有约束的情况下（除小明同学之外），从解的值域中（0100），通过一定的方法（启发式搜索），尽可能的搜索出最大值（最高分95）。为什么这里写95呢，例2中我们明确知道有一最高分97，经过暴力求解一定可以找到，但是例3中，试卷太多了，无法做到把每一张试卷拿出来评分比对，只能使用启发式搜索查找局部的最高分，并且十分可搜索到97也跟你启发式搜索算法的设计，参数的选择有很大关联。所以才会在黄字中标出尽可能，而不是直接找到最高分。
这里列举一些常见的启发式搜索算法，感兴趣可以自行了解：A*算法、贪心算法、爬山法、大邻域搜索算法、蚁群算法、禁忌表搜索算法等。
例4：了解TSP问题、插入算子
TSP问题属于优化问题的入门问题，来看定义：TSP问题又称旅行商问题，是指给定平面上N个点及每点的坐标，求一条路径，遍历所有的点并回到起点，使这条路径长度最小。
TSP问题是一个组合优化问题（组合优化问题是优化问题的一个分支）。该问题可以被证明具有NPC计算复杂性，也就是第一段说的难以在数据规模比较大时被求解出来。
这种问题的求解方法也是启发式搜索算法，现举一个五个数据的例子，空间中有ABCDE五座城市，旅行商从A城市出发，为BCDE城市送货，最终回到A点，如何组合送货顺序使得旅行商的旅行距离最短。也许你首先还是会想到暴力组合，可以，稍加思考就能得到计算机只需排列4!次就能求解答案，但是如果给48个城市送货呢？给100个城市送货呢？那么需要排列100！次，用计算器计算100！的数值就会知道这是一个天文数字，那么实际的计算时间开销一定十分大。解决方法就是上文提到的启发式搜索，我们只寻求局部最优解，不寻求全局最优解，那么就有可能找到一个比较合适的答案。将BCDE初步组合起来，寻找它的邻域，这里使用插入算子作为搜索邻域的方法。
搜索邻域的方法：在例3中，搜索邻域的方法是改变某一个答案（这是我们自定义的，是为了直观理解），例4中搜索邻域的方法是插入算子（这是常用的一种找寻组合优化问题邻域的方法）。
新名词，插入算子：随机选取一个字母，将其插入到随机位置。如我随机抽到了B，将其随机插入到位置3，那么旅行顺序BCDE就变为旅行顺序CDBE，凡是使用一次（注意看是使用一次）插入算子之后得到的新的旅行顺序都可以称之为在BCDE的邻域中（是BCDE邻域，邻域理解见例3）。之后就是从邻域中根据评价函数（这里的评价值就是组合了BCDE顺序之后旅行商走过的距离大小）搜索出一个旅行顺序，再从新的旅行顺序中寻求新的解，最终得到一个合适的局部最优解，就是旅行商最终要选择的旅行顺序。
看到这里，优化问题的基本逻辑就清楚明了了，你可以自行将TSP问题组合成以下形式：在有限制、有约束的情况下（），从解的值域中（），通过一定的方法（），尽可能的搜索出最大值（）。
欢迎批评指正，点赞~~
标签：问题,一文,弄懂,试卷,邻域,最高分,彻彻底底,搜索,优化 From： https://www.cnblogs.com/awangkuo/p/17739807.html