1

我正在研究一个近似匹配问题，其中我在未知图 (A) 和部分图 (B) 中有一组路径，其中 B 是增量生成和增长的。

问题是将路径中的边与图 B 匹配，同时保留路径和图上边的顺序。在我的问题中，图节点是无关紧要的，并且边缘具有执行匹配的非唯一标签。此外，要匹配的路径可以在匹配图 B 时添加/删除任意边。如果我对当前的解决方案不满意，我可以查询一个预言机，这给了我一个更完整（更大）的图（即我的意思是增长）但我想最小化查询，因为图表可能是无限的。

4

1 回答 1

0

我试图从分配和图同构中查找标准解决方案，但没有找到任何类似的东西。所以，这是我想出的一个解决方案：

  1. 我正在使用分支定界算法将路径中的每条边匹配到图中的每条边（MXN 表）。对于每个可能的分配，我都在跟踪哪些其他分配可能包含在特定分配中
  2. 边界条件（和可行性）由图中边缘的相同顺序定义，因为它在路径中。此外，不能映射两条路径，以免它们相互违反顺序。
  3. 如果我们对这个解决方案不满意，我们可以查询 oracle，获取更大的图并重复 1 和 2。否则，该技术会输出可能的边映射。

我不确定我的解决方案是否仍然属于分支定界算法，因为它不再遵循标准的分支定界树结构。此外，如果有人能指出优化或更好的方法来做到这一点，那就太好了。

注意：在每次迭代中，N 都会发生变化，并且表格会水平增长。最大的低效率是在第 2 步，为了安全起见，需要在每个阶段重新计算（例如，在图中添加的循环会使以前的解决方案无效）

于 2015-03-29T19:57:15.083 回答