我最近偶然发现了这个算法,并且很难自己解释它.该算法解决了O(n 4)中的赋值问题(显然可以改进为O(n 3)),但我不明白为什么.
直观地,我可以看到算法倾向于找到优秀的解决方案,但我看不到证据!到目前为止,我所看到的所有证据都包含我不熟悉的符号.我的问题是:任何人都可以严格解释它吗？
我已经理解,问题可以转移到值矩阵,其中每行和每列中只需要选择一个值.可能的最小值(来自所选元素)以及产生该值的选择是算法计算的值.显然,找到选择也找到了最小值.
我正在努力的部分,符号方式,就在这里.设置部分中的第三段开头"让我们调用一个函数"......