和上篇一样,考前写写伪代码,考完了补上具体的解释和代码。
状态{矩阵,结果集,下界}
全局结果集列表,全局上界初始为Infinite
建立一个heap,存储状态,出堆规则为拥有最小的下界。
利用reduced cost matrix 来把矩阵进行化简,把化简消耗作为下界,将初始状态加入heap
当heap不为空时
{
从heap中弹出一个状态,赋值给两个临时状态。
若该状态的下界大于等于全局上界,则return
遍历所有弧,选择删除则引起下界上升最大的弧
若使用该弧
{
更新下界
若已经遍历所有城市并回到了起点且小于等于全局上界,记录该状态,更新全局上界
否则 将该弧所对应的整行和整列赋值为Infinite,将当前的弧的反向弧赋值为Infinite,在结果集中记录该弧,将状态加入heap
}
否则 在matrix中将该弧赋值为Infinite,更新下界,将状态加入heap
}