2

假设我有一个集合（或图表），它被分成几组。我有兴趣找到两个分区之间的转换数量，其中转换涉及从一个分区中取出一个元素并将其移动到另一个分区（或单独的单例分区）

例如，分区之间有一个转换

1 2 | 3和 1 | 2 | 3

但在1 2 3 4和之间1 2 | 3 | 4

我相信最小的转换次数是 2。

所以我的问题是有没有给定一对分区和一组的算法，可以返回它们之间的转换状态数？

还有一个更复杂的情况是，这个集合实际上代表一个图，我希望每个分区（和转换分区）都被连接（即，如果 1 和 2 之间不存在被 3 阻塞的直接/直接连接，则 1 2 | 3 将无效单个分区），但除非您对这个主题真正开明，否则您很可能会忽略它。

谢谢

作为一个注释，我确实有一个我自己想到的方法，它基本上是找到分区 A 的所有邻居（即可以在一个转换中找到的所有分区）并对分区 B 执行相同的操作，如果这些是这些之间的一些重叠两组邻居然后他们是一个过渡。然而，这种方法很快就会变得非常昂贵。

4

1 回答 1

1

我会稍微扩展你的方法，基本上构建一个图表并进行图表搜索。图的顶点将是集合的有效分区，而边将是转换。您实际上可以同时构建和搜索，并且只构建搜索所需的图形部分。

为此，我将使用 A*（或其他最佳优先搜索），并在每一步生成当前分区的所有邻居。棘手的部分是确定 A* 搜索的最佳启发式方法。您可以通过假设所有转换都会导致连接的分区来估计转换的数量（基本上，忽略您的约束）。

这显然很昂贵，但您可以通过使用最佳优先搜索并在执行过程中生成图表来节省时间和空间。

于 2010-08-22T04:58:59.720 回答