13,339
次編輯
變更
组合爆炸
,创建页面，内容为“指随着优化问题规模的不断增大，决策变量取值的不同组合量、可行解数量以及寻找最优解时需要考虑的组合量也会迅速大幅…”
指随着优化问题规模的不断增大，决策变量取值的不同组合量、可行解数量以及寻找最优解时需要考虑的组合量也会迅速大幅度增加，且往往是以指数形式增加，最终导致无法从中找到最优解。
当解决问题所需计算的数量级过于巨大时所造成的障碍。例如在设计下棋软件时就遇到组合爆炸的困扰，每一手棋常要计算和分析几千种可能的步法。解决这类问题人比电脑似乎更胜一筹，因为人凭籍着说不太清楚的“直觉”思考把可能的步法限制在力所能及的范围内。这就是优秀的棋艺选手能打败最好的下棋程序的原因所在。<ref>[[靳志宏著. 物流调度与协调(M). 北京：中国物资出版社, 2008.12.]]</ref>
旅行商问题，简称TSP问题，又称[[货郎担问题]]、[[邮递员]]问题，是英国数学家[[克克曼]]（T.P. Kirkman）于19世纪初提出的一个数学问题，是指旅行商要从某个城市出发，旅行n个城市然后回到出发城市，要求各个城市经历且仅经历一次，并要求所走的路程最短。
用最原始的方法解决TSP问题可以找出所有可能的回路，从中选取路径长度最短的回路，对每对路径来说，不同的只是路径的方向，因此，可以将所有可能的旅行路线减半，对于具有n个顶点的TSP问题，可能的解有(n-1)!/2个。这是一个非常大的数，随着n的增长，TSP问题的可能解也在迅速地增长，从而产生所谓的组合爆炸。例如：
10城市的TSP问题有大约180 000个可能解。
20城市的TSP问题有大约60 000 000 000 000 000个可能解。
TSP问题属于组合优化问题，即寻找一个组合对象（一个排列或一个组合），这个对象能够满足特定的约束条件并使得某个目标函数取得极值：价值最大或成本最小。
无论从理论的观点还是实践的观点，组合优化问题都是计算领域中最难的问题，其原因是：
（1）随着问题规模的增大，组合对象的数量增长极快，即使是中等大小的实例，其组合对象的数量也会达到不可思议的数量级，产生组合爆炸；
（2）还没有一种已知算法能在可接受的时间内，精确地求解绝大多数这类问题。<ref>[[胡明，王红梅编著. 计算机学科概论(M). 北京：清华大学出版社, 2008.07.]]</ref>
组合优化：
一个组合优化问题π由三个基本要素（D,F,f）组成。其中：
（1）D表示决策变量的定义域，其每个决策变量的有限个取值的不同组合形式构成了组合优化问题的不同实例，所有这些实例构成了实例集合S(I)。
（2）对于每一个实例I，存在一个有穷的可行解集合F(I)。
（3）对于每一个实例I和每一个可行解σ∈F(I)，其目标函数都可以被赋予一个实数值f(I,σ)。如果组合优化问题π为求极（大）小值问题，则实例I的最优解σ1是这样一个可行解，即对于∀σ∈F(I)，都满足f(I,σ)≥f（I,σ)[对于极大值问题则为f(1,σ1)≤f(1,σ)]。
对于一个组合优化问题π，给定任意一个实例I，如果能设计一个解法程序P使其总能够找到该问题的一个可行解σ∈F(I)，则称P为π的近似算法；进一步，如果总能够找到该问题的一个最优解，则称P为π的精确算法。
组合优化问题的最大特点是决策变量取值是离散的、有限的；可行解集合同样也是有限的。因此，从理论上讲，只要将这些有限的点逐一判断是否满足约束条件和比较目标函数值的大小，该问题的精确解算法一定存在并可以找到。但是，由于现实优化问题的规模都比较大、约束条件较为复杂等原因，在可以容忍的有限时间及费用范围内，通过精确算法寻找最优解十分困难，不得已退而求其次，需要采用近似算法求其局部最优解。 <ref>[[靳志宏著. 物流调度与协调(M). 北京：中国物资出版社, 2008.12.]]</ref>
人工智能由相互有差异但都令人感兴趣的几个方面组成，其中多数AI应用的基础是问题求解。所有问题基本分为两类。第一类通过某种确保成功的决定过程（即计算过程）解决。解决第一类问题的方法常常易于转换成计算机能执行的算法。然而，没有几个现实问题是适合计算解决方案的。事实上，许多问题（即第二类问题）是非计算性的。解决第二类问题的办法是搜索，即人工智能关心的问题求解方法。
人工智能迫求的目标之一，是建立一个通用问题求解器。通用问题求解器是一种程序，其中没有特定领域的专门知识，但又能够产生对各种问题的解。
早期研究AI的主要目的是研究优秀的搜索方法。其原因有二：需要和愿望。把AI技术应用到现实问题的最大障碍就是多数情况下的规模和复杂性，因此我们需要高效率的搜索技术。此外，研究人员一直认为搜索是问题求解的关健，而问题求解又是智能的关键成分。<ref>[[（美）赫伯特·希尔特（Herbert Schildt）著；王子恢，戴健鹏等译. C语言大全 第4版(M）. 北京：电子工业出版社, 2001.09.]]</ref>
==参考文献==
{{Reflist}}
当解决问题所需计算的数量级过于巨大时所造成的障碍。例如在设计下棋软件时就遇到组合爆炸的困扰，每一手棋常要计算和分析几千种可能的步法。解决这类问题人比电脑似乎更胜一筹，因为人凭籍着说不太清楚的“直觉”思考把可能的步法限制在力所能及的范围内。这就是优秀的棋艺选手能打败最好的下棋程序的原因所在。<ref>[[靳志宏著. 物流调度与协调(M). 北京：中国物资出版社, 2008.12.]]</ref>
旅行商问题，简称TSP问题，又称[[货郎担问题]]、[[邮递员]]问题，是英国数学家[[克克曼]]（T.P. Kirkman）于19世纪初提出的一个数学问题，是指旅行商要从某个城市出发，旅行n个城市然后回到出发城市，要求各个城市经历且仅经历一次，并要求所走的路程最短。
用最原始的方法解决TSP问题可以找出所有可能的回路，从中选取路径长度最短的回路，对每对路径来说，不同的只是路径的方向，因此，可以将所有可能的旅行路线减半，对于具有n个顶点的TSP问题，可能的解有(n-1)!/2个。这是一个非常大的数，随着n的增长，TSP问题的可能解也在迅速地增长，从而产生所谓的组合爆炸。例如：
10城市的TSP问题有大约180 000个可能解。
20城市的TSP问题有大约60 000 000 000 000 000个可能解。
TSP问题属于组合优化问题，即寻找一个组合对象（一个排列或一个组合），这个对象能够满足特定的约束条件并使得某个目标函数取得极值：价值最大或成本最小。
无论从理论的观点还是实践的观点，组合优化问题都是计算领域中最难的问题，其原因是：
（1）随着问题规模的增大，组合对象的数量增长极快，即使是中等大小的实例，其组合对象的数量也会达到不可思议的数量级，产生组合爆炸；
（2）还没有一种已知算法能在可接受的时间内，精确地求解绝大多数这类问题。<ref>[[胡明，王红梅编著. 计算机学科概论(M). 北京：清华大学出版社, 2008.07.]]</ref>
组合优化：
一个组合优化问题π由三个基本要素（D,F,f）组成。其中：
（1）D表示决策变量的定义域，其每个决策变量的有限个取值的不同组合形式构成了组合优化问题的不同实例，所有这些实例构成了实例集合S(I)。
（2）对于每一个实例I，存在一个有穷的可行解集合F(I)。
（3）对于每一个实例I和每一个可行解σ∈F(I)，其目标函数都可以被赋予一个实数值f(I,σ)。如果组合优化问题π为求极（大）小值问题，则实例I的最优解σ1是这样一个可行解，即对于∀σ∈F(I)，都满足f(I,σ)≥f（I,σ)[对于极大值问题则为f(1,σ1)≤f(1,σ)]。
对于一个组合优化问题π，给定任意一个实例I，如果能设计一个解法程序P使其总能够找到该问题的一个可行解σ∈F(I)，则称P为π的近似算法；进一步，如果总能够找到该问题的一个最优解，则称P为π的精确算法。
组合优化问题的最大特点是决策变量取值是离散的、有限的；可行解集合同样也是有限的。因此，从理论上讲，只要将这些有限的点逐一判断是否满足约束条件和比较目标函数值的大小，该问题的精确解算法一定存在并可以找到。但是，由于现实优化问题的规模都比较大、约束条件较为复杂等原因，在可以容忍的有限时间及费用范围内，通过精确算法寻找最优解十分困难，不得已退而求其次，需要采用近似算法求其局部最优解。 <ref>[[靳志宏著. 物流调度与协调(M). 北京：中国物资出版社, 2008.12.]]</ref>
人工智能由相互有差异但都令人感兴趣的几个方面组成，其中多数AI应用的基础是问题求解。所有问题基本分为两类。第一类通过某种确保成功的决定过程（即计算过程）解决。解决第一类问题的方法常常易于转换成计算机能执行的算法。然而，没有几个现实问题是适合计算解决方案的。事实上，许多问题（即第二类问题）是非计算性的。解决第二类问题的办法是搜索，即人工智能关心的问题求解方法。
人工智能迫求的目标之一，是建立一个通用问题求解器。通用问题求解器是一种程序，其中没有特定领域的专门知识，但又能够产生对各种问题的解。
早期研究AI的主要目的是研究优秀的搜索方法。其原因有二：需要和愿望。把AI技术应用到现实问题的最大障碍就是多数情况下的规模和复杂性，因此我们需要高效率的搜索技术。此外，研究人员一直认为搜索是问题求解的关健，而问题求解又是智能的关键成分。<ref>[[（美）赫伯特·希尔特（Herbert Schildt）著；王子恢，戴健鹏等译. C语言大全 第4版(M）. 北京：电子工业出版社, 2001.09.]]</ref>
==参考文献==
{{Reflist}}