algorithm - 计算合成平方根的高效算法

Question

假设我们有一个有限的字母表，例如 X = [1,2,3,..., n]和一张 map f使用 X 中的键和值也在 X 中(从 X 到 X 的数学函数)。

定义:功能平方根，或复合平方根，或半迭代，是另一个 map g使用 X 中的键和 X 中的值这样 g[g[x]]==f[x]对于所有 x在 X .

示例 1:如果 f = {'A':'A', 'B':'A', 'C':'A'}然后 g = {'A':'A', 'B':'A', 'C':'B'}可以是 f 的函数平方根.函数平方根不是唯一的。 map f也是它自己的函数平方根。

示例 2: map f = ['A':'B', 'B':'A']没有函数平方根。事实上，如果我们定义 g['A'] = 'A' , 然后 'A'将是 g 的不动点因此它必须是 f 的不动点.如果我们定义 g['A'] = 'B' , 那么我们需要定义 g['B'] = 'B'和 'B'必须是 f 的固定点.因此，有时函数平方根并不存在。

我有时会手动计算这个，但现在我想我真的没有一个有效的策略来计算它。

问题:[设计一个高效算法来]计算给定输入映射的函数平方根。

我认为首先解决输入保证具有函数平方根的情况是公平的。

算法的存在性: 生成所有 map 总有蛮力解法g来自 X至 X并将每个与自身组合以检查它们是否等于 f .

---

到目前为止我看到的一些观察可以减少某些输入的问题:

1. 每个固定点，一个key x这样 f[x] == x , 允许定义 g[x] = x .
2. 每个键 y映射到一个固定点，f[y] == x和 f[x] == x , 允许定义 g[y] = x .
3. 除了满足第(2)点条件的键外，没有其他键应该被g映射。到固定点 f .
4. 存在高效算法的情况:如果f是单射的(没有两个键被发送到相同的值)然后 f是 X 的排列在这种情况下，可以根据其 cycle decomposition of the permutation 计算平方根。 .找到循环分解可以一次性完成，并从中求平方根 also .

对于双射，可以线性计算(看起来)平方根这一事实让我希望可能有一些有效的方法来计算一般情况。如果我的定义正确，问题是 NP，因为给定的 g可以验证 g是 f 的复合平方根在线性时间内。对我来说，它闻起来不像 NP 完全，但我在证明从一个问题到另一个问题的这些减少方面经验很少。

---

从下面的方式也可以看出问题。输入图f可以看作是有限自动机的有向图，其中每个状态的出度为 1。计算复合平方根就是找到一个具有相同状态集的自动机，当在一次。

Answer 1

问题可以分解为两个问题。

如果你取 f、f^2、f^3 范围的交集，...你会得到得到一个有限集合 Y，f 作为一个排列操作。正如您在观察 4 中指出的那样，我们可以找到排列的所有平方根。可能有很多这样的，但我们知道在寻找它们的过程中我们可以做出哪些选择。我们要么将相同长度的循环与一些旋转配对，要么重新排序奇数长度的循环。如果我们不能这样做，就没有平方根，并且可以通过做出这两种选择的方式来列举所有求平方根的方式。

第二个问题是临时值，它形成以 Y 结尾的链。锁链很容易找到，我们知道它们的尽头在哪里。如果 g 是 f 的平方根，则长度为 2k 或 2k-1 的链为g 必须是一对长度为 k 的 f 链，k 或 k- 1 这样第一个的结尾是 g(x) 其中 x 是第二个的结尾。这是一个非常强大的条件，因为要么这些链都以奇数长度的相同循环结束，而可能较短的链几乎在 p 的一半结束，要么这些链都以不同的循环结束相同的长度，并且来自一个偶数长度的循环。

因此，我建议按以下方式解决问题。

首先将 X 变成一个图形，其中有一个从 x 到 f(x) 的定向箭头。找到所有循环和链。所有循环的并集为Y，首先验证f在Y中有一个平方根。之后，健全性检查链是否可以匹配。如果不是，则没有平方根。

如果您通过了几次完整性检查，请尝试以递归方式实际将链匹配到包含它们的图形部分的工作平方根。如果这成功了，那么你就可以很容易地匹配其余的循环并且你有一个平方根。如果失败，则没有平方根。

在大多数情况下，您会发现很快就没有平方根了。可能较慢的方法是递归地匹配链。希望不会有太多这样的决定，而且它们很容易做出，但指数回溯并非先验地不可能找到。