隐式图上令人惊叹的算法系列
几乎根据定义，动态规划就是在隐式 dag 上找到最短/最长路径。 每个 DP 算法就是这样做的。
全息算法可以粗略地描述为计算隐式平面图中完美匹配的算法。
所以，我的问题是：是否有其他算法系列使用众所周知的算法而不是隐式图来实现相当大的加速？
Dynamic programming is, almost by definition, to find a shortest/longest path on an implicit dag.
Every DP algorithm just does this.
An Holographic algorithm can be loosely described as something that counts perfect matchings in implicit planar graphs.
So, my question is: are there any other families of algorithms that use well-known algorithms over implicit graphs to achieve a considerable speedup?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
贪心算法总是给出最优解的优化问题具有 matroid 结构。拟阵是一个集合系统，因此它比图（图是一个集合系统，其中子集（称为边）都恰好有 2 个元素）更通用，但您可能仍然对它感兴趣。
全息算法看起来非常有趣，我以前从未听说过它们——一定会看看！
Optimisation problems for which a greedy algorithm always gives an optimal solution have matroid structure. A matroid is a set system, so it's more general than a graph (which is a set system in which the subsets (called edges) all have exactly 2 elements) but it might still be of interest to you.
Holographic algorithms look very interesting and I haven't heard of them before -- will definitely take a look!
我想到的另一个想法是多面体优化。基本上，线性规划是解决涉及线性不等式和连续变量的优化问题的有效方法，但是将变量限制为整数通常会导致 NP 难优化问题。这是不幸的，因为各种各样的问题都可以表示为整数规划问题。
通常的方法是详尽地枚举所有可行的解决方案并选择最佳的，可能使用分支和绑定 修剪搜索空间中不能达到最优的部分。有时这可以很好地发挥作用，但较新的多面体方法通常要好得多。
我理解最好的方法是切割平面方法，其中线性问题的松弛得到解决（例如使用单纯形算法）；如果解恰好是整数，那么我们也得到了问题的整数限制的答案。如果不是，则寻找一个平面，将找到的非整数解与整数解的可行区域分开。然后将该平面作为约束添加到问题中，并再次使用线性规划求解新问题。这一直持续到产生完整的解决方案。
显然，这样一个平面必定存在；此外，还存在一个用于查找它们的通用算法（尽管它是性能通常很弱）。研究人员投入了大量时间来寻找更好的算法来解决特定问题类型的“分离问题”。最著名的例子是旅行商问题，其中计算上可行的问题规模增加简直是令人震惊。
切割平面方法通过限制同时考虑的约束数量来实现更好的性能；另一种方法是列生成，其中同时优化的变量数量受到限制。
不确定这是否真的符合您的隐式图算法标准，但我认为这肯定是一种令人着迷的非显而易见的方法！
Another idea that comes to mind is polyhedral optimisation. Basically, linear programming is an efficient way to solve optimisation problems involving linear inequalities and continuous variables, but restricting the variables to the integers leads to an NP-hard optimisation problem in general. That's unfortunate because a huge variety of problems can be expressed as integer programming problems.
The usual approach has been to exhaustively enumerate all feasible solutions and select the best, possibly using branch and bound to prune parts of the search space which cannot be optimal. That can sometimes work quite well, but the newer polyhedral approach is often dramatically better.
The method that I understand the best is the cutting-plane method, in which a linear relaxation of the problem is solved (using e.g. the simplex algorithm); if the solution happens to be integral, we have the answer for the integer restriction of the problem too. If it's not, then a plane is sought which separates the found non-integral solution from the feasible region of integer solutions. This plane is then added to the problem as a constraint, and the new problem is solved using linear programming again. This continues until an integral solution is produced.
Clearly such a plane must exist; further, a general-purpose algorithm exists for finding them (although it's performance is usually very weak). Researchers have devoted a lot of time to finding better algorithms for solving this "separation problem" for specific problem types. The most famous example is the Travelling Salesman Problem, where the increase in computationally feasible problem size is nothing less than staggering.
The cutting planes approach achieves better performance by limiting the number of constraints simultaneously under consideration; an alternative approach is column generation, in which the number of variables simultaneously being optimised is limited.
Not sure if this really fits your criteria of an implicit graph algorithm, but it's certainly a fascinating non-obvious approach I think!