为什么我们称之为"放松"的优势？

Question

在Dijkstra的最短路径算法和其他算法中,检查边缘以查看它是否提供更好的节点路径被称为放松边缘.为什么叫做放松？

Answer 1

通常在数学上,放松正在做出改变以减少约束.当Dijkstra算法检查边缘时,它会从池中移除边缘,从而减少约束的数量.

这不是一个非常有用的术语,但想想你会说它有多酷.

想想一个有很多边缘的顶点.当你开始时,你知道解决方案必须包括第一条边,第二条边等的重量.实际上,对于边a,b,c,d和e,您开始说"最短路径必须包括a,b,c,d,e".然后你消除e,现在你知道必须包括"a,b,c,d".每个步骤都是*松弛*,因为在每个步骤中您都会删除当前解决方案所施加的条件. (2认同)