多主体优化系统和旅行推销员问题

快捷方式: 差异，相似，杰卡德相似系数，参考。

多主体优化系统和旅行推销员问题之间的区别

多主体优化系统 vs. 旅行推销员问题

多主体优化系统 (multiagent optimization system, MAOS) 是一种基于混合多主体系统和群集智能的优化系统。它已经被用来求解数值优化和组合优化问题，如旅行商问题、图着色问题、背包问题等。. 旅行推销员问题（最短路径问题）（Travelling salesman problem, TSP）是这样一个问题：给定一系列城市和每对城市之间的距离，求解访问每一座城市一次并回到起始城市的最短回路。它是组合优化中的一个NP困难问题，在运筹学和理论计算机科学中非常重要。 TSP是与的一种特殊情况。 在计算复杂性理论中，TSP的做决定版本（其中，给定长度 L，任务是决定图中是否有路径比 L 还要短）属于NP完全问题。因此随着城市数量的增多，任何TSP算法最坏情况下的运行时间都有可能随着城市数量的增多超多项式（可能是）级别增长。 问题在1930年首次被形式化，并且是在最优化中研究最深入的问题之一。许多优化方法都用它作为一个基准。尽管问题在计算上很困难，但已经有了大量的启发式和精确方法，因此可以完全求解城市数量上万的实例，并且甚至能在误差1%范围内估计上百万个城市的问题。 甚至纯粹形式的TSP都有若干应用，如企划、物流、芯片制造。稍作修改，就是DNA测序等许多领域的一个子问题。在这些应用中，“城市”的概念用来表示客户、焊接点或DNA片段，而“距离”的概念表示旅行时间或成本或DNA片段之间的相似性度量。TSP还用在天文学中，观察很多源的天文学家希望减少在源之间转动望远镜的时间。许多应用（如资源或时间窗口有限）中，可能会加入额外的约束。.

组合优化

组合最优化，在应用数学和理论计算机科学的领域中，组合优化是在一个有限的对象集中找出最优对象的一类课题。在很多组合优化的问题中，穷举搜索/枚举法是不可行的。组合优化的问题的特征是可行解的集是离散或者可以简化到离散的，并且目标是找到最优解。常见的例子有旅行商问题和最小生成樹。二维的例子，比如服装厂做衣服，衣服分成很多块，这些块需要从布料上切下来。怎么切，剩下的废布料最少？三维的例子，如集装优化。 组合优化的难处，主要是加进来拓扑分析，不同的拓扑形态下，不同部分的约束关系便不同，算法也就要调整。如果给定一个拓扑形态，组合优化往往就退化成一个整数优化的问题了。 Category:應用數學.

多主体优化系统和组合优化 · 旅行推销员问题和组合优化 · 查看更多 »