集(图)分区对之间转换次数的算法

Question

假设我有一个分成组的集合(或图)。我有兴趣找到两个分区之间的转换次数，其中转换涉及从一个分区中取出一个元素并将其移动到另一个分区(或单例分区本身)

例如分区之间有一个转换

1 2 | 3 和 1 | 2 | 3

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

我认为最小转换次数是 2。

所以我的问题是，是否存在给定一对分区和一个集合的算法，可以返回它们之间的转换状态数？

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

谢谢

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

Answer 1

我会稍微扩展一下您的方法，主要是构建图表并进行图表搜索。图的顶点将是集合的有效划分，而边将是过渡。您实际上可以同时构建和搜索，并且只构建搜索所需的图形部分。

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

这显然代价高昂，但您可以通过使用最佳优先搜索和随手生成图表来节省时间和空间。