利用改进匈牙利算法求解旅行商问题

摘要： 针对传统的匈牙利算法在求解旅行商问题(travelling salesman problem, TSP)时会导致多回路闭合的问题，提出了破环机制，设计了破环匈牙利算法。通过采用分配问题的描述方法对旅行商问题进行建模，并建立二者之间的转换关系，论证了TSP可行解的充分必要条件是对应分配问题的可行解与辅助边结合后仅包含一个环路，对6个标准旅行商进行测试和对比分析，验证算法的有效性。... （共8页）