2.1哈密尔顿圈

朱道元的邮路安排问题也涉及到路径，运量。所以有必要学习。TSP问题涉及到的是最短圈问题，跟路径变量联系到一起了。
里面第一个基础问题时哈密尔顿圈。
那么怎么对哈密尔顿圈建模？
目标：最短圈
约束：给个点都走过。
变量：01路段路径变量

Paste_Image.png

下面校对

1. 很符合TSP的定义（旅行商问题）
2. TSP问题是一个NPC/NP-hard问题。
3. 假设有一个旅行商人要拜访N个城市，他必须选择所要走的路径，路径的限制是每个城市只能拜访一次，而且最后要回到原来出发的城市。路径的选择目标是要求得的路径路程为所有路径之中的最小值。一个目标，一个约束
4. 哈密顿通路（回路）与哈密顿图 （Hamilton图） 通过图G的每个结点一次，且仅一次的通路（回路），就是哈密顿通路（回路）. 存在哈密顿回路的图就是哈密顿图·
5. 旅行商问题(TSP)
6. 数学规划模型
   5.1 汉密尔顿圈的约束及决策变量
   约束要防止子圈的形成。

Paste_Image.png

目标函数很简单
约束条件怎么定义
我是从边的条数上约束的，不对。
从节点上约束。每走一步，边的条数上上都要约束。
建模上还是有点嫩。