几乎按照定义，动态编程是在隐式 dag 上找到最短/最长路径。每个 DP 算法都是这样做的。
全息算法可以粗略地描述为在隐式平面图中计算完美匹配的东西。
所以，我的问题是：是否还有其他算法家族在隐式图上使用众所周知的算法来实现相当大的加速？
问问题
404 次
2 回答
3
贪心算法总是给出最优解的优化问题具有拟阵结构。拟阵是一个集合系统，因此它比图（这是一个集合系统，其中子集（称为边）都恰好有 2 个元素）更通用，但您可能仍然对它感兴趣。
全息算法看起来很有趣，我以前没有听说过它们——一定会看看！
于 2010-04-22T03:18:00.517 回答
3
想到的另一个想法是多面体优化。基本上，线性规划是解决涉及线性不等式和连续变量的优化问题的有效方法，但将变量限制为整数通常会导致 NP-hard 优化问题。这是不幸的，因为各种各样的问题都可以表示为整数规划问题。
通常的方法是详尽地列举所有可行的解决方案并选择最佳解决方案，可能使用分支和绑定来修剪搜索空间中无法优化的部分。这有时可以很好地工作，但较新的多面体方法通常要好得多。
我最了解的方法是切割平面法，其中解决了问题的线性松弛（使用例如单纯形算法）；如果解决方案恰好是整数，我们也有问题的整数限制的答案。如果不是，则寻找一个平面，将找到的非整数解与整数解的可行域分开。然后将该平面作为约束添加到问题中，并再次使用线性规划解决新问题。这一直持续到产生一个完整的解决方案。
显然这样的平面必须存在；此外，存在一种通用算法来找到它们（尽管它的性能通常很弱）。研究人员投入了大量时间来寻找更好的算法来解决特定问题类型的“分离问题”。最著名的例子是旅行推销员问题，其中计算上可行的问题规模的增加简直是惊人的。
切割平面方法通过限制同时考虑的约束数量来实现更好的性能；另一种方法是列生成，其中同时优化的变量数量是有限的。
不确定这是否真的符合您对隐式图算法的标准，但我认为这肯定是一种引人入胜的非显而易见的方法！
于 2010-04-22T08:07:18.273 回答