基于分支限界法的旅行商问题(TSP)二

时间:2021-11-10 05:41:20

和上篇一样,考前写写伪代码,考完了补上具体的解释和代码。

状态{矩阵,结果集,下界}

全局结果集列表,全局上界初始为Infinite

建立一个heap,存储状态,出堆规则为拥有最小的下界。

利用reduced cost matrix 来把矩阵进行化简,把化简消耗作为下界,将初始状态加入heap

当heap不为空时

{

  从heap中弹出一个状态,赋值给两个临时状态。

  若该状态的下界大于等于全局上界,则return

  遍历所有弧,选择删除则引起下界上升最大的弧

  若使用该弧

  {

    更新下界

    若已经遍历所有城市并回到了起点且小于等于全局上界,记录该状态,更新全局上界

    否则 将该弧所对应的整行和整列赋值为Infinite,将当前的弧的反向弧赋值为Infinite,在结果集中记录该弧,将状态加入heap

  }

  否则 在matrix中将该弧赋值为Infinite,更新下界,将状态加入heap

}