假设我有一个集合(或图表),它被分成几组。我有兴趣找到两个分区之间的转换数量,其中转换涉及从一个分区中取出一个元素并将其移动到另一个分区(或单独的单例分区)
例如,分区之间有一个转换
1 2 | 3
和 1 | 2 | 3
但在1 2 3 4
和之间1 2 | 3 | 4
我相信最小的转换次数是 2。
所以我的问题是有没有给定一对分区和一组的算法,可以返回它们之间的转换状态数?
还有一个更复杂的情况是,这个集合实际上代表一个图,我希望每个分区(和转换分区)都被连接(即,如果 1 和 2 之间不存在被 3 阻塞的直接/直接连接,则 1 2 | 3 将无效单个分区),但除非您对这个主题真正开明,否则您很可能会忽略它。
谢谢
作为一个注释,我确实有一个我自己想到的方法,它基本上是找到分区 A 的所有邻居(即可以在一个转换中找到的所有分区)并对分区 B 执行相同的操作,如果这些是这些之间的一些重叠两组邻居然后他们是一个过渡。然而,这种方法很快就会变得非常昂贵。