组合优化的问题分类

Question

如题所述

Answer 1

典型的组合优化问题有：
旅行商问题（Traveling Salesman Problem－TSP）；
加工调度问题（Scheduling Problem，如Flow-Shop，Job-Shop）；
0-1背包问题（Knapsack Problem）；
装箱问题（Bin Packing Problem）；
图着色问题（Graph Coloring Problem）；
聚类问题（Clustering Problem）等。
这些问题描述非常简单，并且有很强的工程代表性，但最优化求解很困难，其主要原因是求解这些问题的算法需要极长的运行时间与极大的存储空间，以致根本不可能在现有计算机上实现，即所谓的“组合爆炸”。正是这些问题的代表性和复杂性激起了人们对组合优化理论与算法的研究兴趣。