由于组合优化问题的解空间十分庞大，使用精确求解方法无法在确定多项式时间内求得它的最优解。为了解决大规模组合优化问题，人们一直在探索不同的搜索策略，希望能够提高搜索效率，但是求取最优解十分困难，实际应用中常常以近似解代替最优解。已有方法主要采用启发式策略避免陷入局部极值，没有充分利用问题的相关信息，无法避免大量的重复搜索。为了缩小搜索范围，减少重复搜索量，在较短时间内得到质量更高的近似解甚至精确解，论文提出了基于状态转移的组合优化方法，并使用这种方法求解具体问题。主要工作如下： 论文提出了基于状态转移的组合优化方法，利用问题的领域知识，对问题进行分类，对不同类别的问题寻求不同的近似方法，并且在迭代求解过程中，逐步改进近似解，利用问题的上界(下界)、近似解以及其他相关信息降低问题的维数，最后用精确求解方法求解余下的子问题。论文提出了利用当前最优解与上界(下界)相比较的降维方法，以它为基础还提出了利用元素间关系降维的方法、基于特征值的降维方法、把问题分解成多个子问题的降维方法、基于推理的降维方法和基于评价函数的降维方法。论文提出了一些基本的改进近似解的方法，与定界算法一起用于简化问题。论文结合动态规划方法、定界算法和启发式规则提出了组合优化问题的精确求解方法，用于快速求解余下的子问题。 利用基于状态转移的组合优化方法研究了四个组合优化问题的求解方法，包括同顺序三机床加工调度问题、0／1背包问题、旅行推销员问题和坦克战中武器-目标分配问题。 针对同顺序三机床加工调度问题，提出了一种下界算法用于选择问题的第一个加工工件，提出了一种评价函数用于求解时选择后续工件。改变第一个加工工件或者评价函数中的参数可能得到更好的解。实验结果表明：使用这种方法求得的解对应的总加工时间非常接近问题的下界，绝大部分是问题的最优解。论文还提出了一种较好的近似方法求解一般的同顺序加工调度问题。最后综合动态规划方法、下界算法和近似方法提出了一种精确求解同顺序加工调度问题的启发式双侧广度优先搜索方法。实验结果表明：当加工工序数目较少时，利用这种精确求解方法求解需要搜索的次数很少。 针对0／1背包问题，物品的重量与价值不相关或者线性相关时已有相应的快速精确求解方法；但物品的重量与价值非线性相关时该问题尚无快速精确求解方法。基于此，论文提出了这种情况下0／1背包问题的上界算法、降维方法简化问题，改进近似解，最后利用精确求解方法求解余下的子问题，实现了0／1背包问题的快速求解。 针对旅行推销员问题，提出了一种在最小1-树的基础上迭代求解的下界算法和近似求解方法，这种下界算法不仅可以得到问题的下界，还可以得到结构较好的最小1-树，在这种结构较好的最小1-树的基础上可以产生质量较好的近似解。论文构造了边对权值用于更加有效地简化问题，提出了简化旅行推销员问题的四种降维方法。最后综合近似方法、下界算法、降维方法和精确求解方法构成基于状态转移的组合优化方法用于求取问题的精确解。 针对坦克战中的武器-目标分配问题，研究时把它分解成三个子问题：确定对不同毁损程度的目标攻击的武器数量、具体目标选择和弹药选择。分别建立了各个子问题的模型，国防科学技术大学研究生院学位论文提出了坦克战中确定对不同毁损程度的目标攻击的武器数量的算法、目标选择方法和弹药选择方法，提出了目标选择问题的上界算法。坦克战中武器一目标问题求解方法可以有效地提高坦克部队的战斗力。 实验结果表明:基于状态转移的组合优化方法是一种有效的组合优化问题求解方法。利用基于状态转移的组合优化方法快速精确求解组合优化问题的关键是获取较好的定界算法和问题的近似求解方法。文中提出的降维方法，从一定程度上弥补了近似求解方法、定界算法存在的不足。 关键词:状态转移，组合优化，非多项式确定问题，降维方法，定界算法，启发式，旅行推销员问题，0/1背包问题，同顺序加工调度问题，武器一目标分配问题第11页