2

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

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

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

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

4

1 回答 1

0

我建议使用约束可满足性工具包来解决这个问题。我会坚持使用布尔可满足性框架，但您可以查看其他选项，例如SMT、整数编程。

让我们引入一组布尔变量来表示图中的每个顶点：

v_0, v_1, ..., v_N

接下来，让我们引入一组布尔变量来表示每个可能的边（显然是 N^2）：

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

检查此链接以获取详细信息。

当且仅当对应的顶点/边出现在图中时，布尔变量 X 为True 。在您的情况下，我们正在谈论边缘。

此时，您可以尝试将您的边缘选择算法作为一组布尔约束引入：

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

您可以依靠伪布尔编码来引入此类约束。

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

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

我看到一些缺点：

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

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

编辑：

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

于 2017-04-17T06:49:18.120 回答