与标题说的差不多。
这是在分支和边界问题中完成的，特别是在旅行中的销售人员。
我了解矩阵约简的工作原理，但我真的不明白为什么需要这样做。
谢谢。
从技术上讲，您不需要需要，但是它使算法的其余部分更简单，更有效。
分支定界算法是用于优化问题的一种backtracking search，在这种情况下，您不必在回溯之前就探索每个子树的全部。当我们知道某些子树无法提供比目前最好的解决方案更好的解决方案时，可以拒绝这些子树。
对部分解决方案的任何完成要花费多少下限是很有用的。例如，如果我们有一条从节点A→B→C的路径，那么我们知道该路径必须离开节点C，并且在将来的某些时候它必须离开节点D，E和F（不一定按此顺序） ）。如果我们知道离开C，D，E和F的最低成本，则可以将其添加到不完整路径的成本中，以获得从A→B→C开始的完整路径的最低可能成本。高于我们最佳解决方案的成本，那么我们可以拒绝局部解决方案A→B→C，而无需探索它的任何其他分支。
如果我们首先应用矩阵约简，那么离开每个节点的最小成本将为零，因此我们无需在当前成本上添加任何东西即可计算该下限。拒绝A→B→C的规则很简单，就是该部分解决方案的成本是否高于目前最佳的完整解决方案的成本。这简化了代码，还节省了进行这些添加所需的时间。