algorithm - 构建包含哈密顿路径的图

Question

背景 我正在研究一个优化问题，并设法将问题简化为检查图形是否包含哈密顿路径。减少后的问题如下:

问题 我们得到了一系列边(例如:e[1,5], e[3,4], ..., e[2,3])。我们需要从这个序列的开始找到边的数量，以便使用这些边形成的图包含哈密顿路径。我们还需要返回路径。

我的算法 这个问题可以从一个没有边的图开始解决。我们一条一条地插入边，并在每次迭代中检查图形是否包含哈密顿路径。通过使用哈密顿路径存在的必要条件，可以使这种方法更快一些。尽管如此，该算法仍然效率很低。

大问题有没有办法以更有效的方式解决这个问题(也许通过使用在早期迭代中完成的计算来加速后期迭代)？

Answer 1

我建议使用 constraint satisfiability toolkit解决这个问题。我会坚持 Boolean satisfiability框架，但您可以查看其他选项，例如SMT , integer programming .

让我们介绍一组代表图中每个顶点的 bool 变量:

v_0, v_1, ..., v_N

接下来，让我们引入一组 bool 变量来表示每条可能的边(显然是 N^2):

e_0, e_1, ..., e_{N^2}

检查 this link了解详情。

当且仅当相应的顶点/边存在于图中时， bool 变量 X 为 True。在您的情况下，我们正在谈论边缘。

此时，您可以尝试将边选择算法引入为一组 bool 约束:

1. 如果顶点 v_i 的度数为 D，则边 E 必须存在
2. 如果存在 v_i 和 v_j 之间的边，则边 E 必须不存在
3. 等等

您可以信赖pseudo-boolean encodings引入这样的约束。

如果对输入变量进行这样的赋值，结果 bool 公式返回 True(满足)，那么您可以将此赋值解释为包含哈密顿路径和它是由给定的一组规则(约束)构建的。您可以使用 SAT 求解器(例如 Glucose 来查找此类作业。

我使用类似的方法来解决具有 10^5 个变量和 10^6 个约束的实际问题。这可能会非常耗费时间和内存，但它比蛮力方法要好得多，而且更灵活:您可以轻松添加/删除额外的约束，而无需修改代码。

我看到了一些缺点:

1. 对于您的情况，此方法的可扩展性可能不高。结果在很大程度上取决于问题本身，因此很难预测
2. 将图形构建过程编码为一组 bool 约束是一项非常重要的任务。
3. 本质上，SAT 求解器返回随机 分配。如果您想查看其他解决方案/图表，则必须为您的问题添加新的约束条件。

我的算法可能并不完美，但如果您不确切知道如何构建结果(因此没有明确的算法可以做到这一点，除了蛮力)约束可满足性工具包是非常有效的方法。

编辑:

如果一个图是加权的，你仍然可以使用 SAT 来解决这个问题，但它会更难:权重应该在给定的范围内并且应该是离散的。不过，您可以考虑 mixed integer programming