旅行售货员问题的分支限界法

01问题与模型

旅行售货员问题定义与数学模型问题通俗描述数学模型形式化旅行售货员问题描述了一位售货员从驻地出发，需要遍访所有城市恰好一次后返回起点，目标是找到总路程最短的回路。这是经典的组合优化问题，广泛应用于物流、交通等领域。从图论角度形式化TSP问题：给定带权有向图G=(V,E)，寻找一条哈密顿回路，使得边权之和最小。解空间是所有顶点的排列，对应排列树搜索结构，为后续分支限界法提供基础。

暴力枚举的复杂度暴力枚举所有城市排列需要O(n!)时间，当城市数量n≥20时，计算量已不可承受。排列树中每条根到叶的路径对应一个完整的回路，内部结点代表部分路径。剪枝的必要性仅