关于所有置换组合谜题是否存在实用求解算法的技术问询
关于所有置换组合谜题是否存在实用求解算法的技术问询
先给你把这类置换谜题的基础逻辑讲明白:假设我们有一组置换集合 $R$,它生成了一个置换群 $G \subset S_n$。对应这个 $R$ 的「谜题问题」定义很清晰——给定群中的某个元素 $g \in G$(用标准置换符号表示),我们需要找到一个由 $R$ 中元素组成的序列(业内叫“词”),让这个序列的乘积恰好等于 $g$。
目前有个暴力算法能解决所有这类谜题,但实用性极差:它的思路是按词的长度从小到大,不断用 $R$ 里的元素相乘来生成 $G$ 的所有元素,然后逐个比对找目标 $g$。可一旦 $G$ 的规模变大,这个方法要么慢到离谱(时间复杂度大概是 $|G|$ 量级),要么就得在算法里打包巨量预计算好的数据,完全不适合实际使用。
(原内容此处有截断,后续关于 $m \times ...$ 的相关论述未完整提供)
备注:内容来源于stack exchange,提问作者Karl




