“循环变换”的度量化 —— 由《智捉精灵》算法想到的

铯_猪哥恐鸣

魔方问题不是被认为是NPC问题，而是被证明为NPC问题。
参考文献：Demaine, Erik D., Sarah Eisenstat, and Mikhail Rudoy. "Solving the Rubik's Cube Optimally is NP-complete." arXiv preprint arXiv:1706.06708 (2017).

魔方问题与智捉精灵问题其最本质的区别在于，魔方的最少步求解过程并不存在子问题重叠的特性。

铯_猪哥恐鸣

重叠子问题（Overlapping Subproblems）：即子问题之间是不独立的，一个子问题在下一阶段决策中可能被多次使用到。

智捉精灵每一步的最优解都会作为后续决策的子问题被重复用到。
最少步数求解魔方则不存在这类子问题。
注意，必须是“最少步数求解”，如果是形如二阶段算法之类计算非最优解，那么这是一个已经解决的问题。

铯_猪哥恐鸣

我觉得楼主你不妨试着从三阶魔方的<U, R2, F2, D, L2, B2>子群出发，或者<U2, R2, F2, D2, L2, B2>子群出发，看看能有什么新思路。

第一个子群的大小应该现在的计算机差不多够完整的装下，你可以试着按照你的思路写一个最少步求解器，并和现在已有的求解器做个对比。

铯_猪哥恐鸣

对于魔方的循环变换球面网来说，我们可以先找到 N 个均匀分布的可度量“参照点”，然后分别测出这 N 个“参照点”到待求状态的方位，从而锁定待求状态到初始状态的最少步。

为了避免无意义讨论，我试着去理解你的各种表述方式和符号。我试着在吧里搜索了一下，发现你提到的几个名词都没有准确定义。我根据你的表述做了一些猜测，并提出了一系列疑问。

1. 【循环变换球面网】是一个图，其中点代表状态，边代表状态之间通过1步转动可以互相转换，对吗？
2. 【参照点】是否是指特定的某个状态？还是别的概念？
3. 假设我们已经找到了N个参照点，那么对于某个待求解的状态，【参照点到待求状态的方位】这个概念是什么意思？在欧氏空间中【方位】是个可以精确定义的概念，但循环变换球面网所在的空间不一定是欧氏空间，【方位】可能不存在。
4. 如何根据【参照点到待求状态的方位】确定待求解状态的最少步？

5. 你提到了3维循环变换球面网的示意图，你想表达的是你将状态集合映射到了3维欧氏空间中的一些点，对吗？还是说你不关心最后具体映射到了3维欧氏空间还是别的空间，只希望表示状态之间的转换关系？

铯_猪哥恐鸣

超高维空间的话，你说的是N维欧式空间吗？
还是说你在实际用的时候根本不关心是几维空间，只关心各个状态和状态之间的转换关系？

铯_猪哥恐鸣

不不不，“循环变换球面网”是你提出来的东西，你没有给出精确的定义，只是举了几个例子。你的语境中，“空间”，“维”，“网”，“球面”，可能都和传统意义下的这几个词有着不同的含义。我实在无法通过这几个例子理解你到底要定义一个什么概念。

铯_猪哥恐鸣

ggglgq 发表于 2018-4-20 08:52
这不是个问题，因为“魔方的循环变换球面网”是一个不以人们对意志为转移的“客观存在”，随着 ...

这真的是个问题。
循环变换球面网是不是客观存在，对不起我不知道，除了你之外我没看到有别人承认它的存在性。不是任何一个概念都客观存在的，比如“大于零的最小实数”这个东西就是不存在的。
我只能从你的描述中看到Cayley graph的概念。如果循环变换球面网就是Cayley graph，那我们之后的讨论全都针对后者就好了，也不用管什么空间了。如果不是，那希望你能指出它们之间的区别，而不是随便提了个轻易看不懂的名词。

你也说了，重要的是能不能解决问题。好，现在请你告诉我，为什么我要相信你定义的概念能解决问题？我看不出它除了哗众取众之外的作用，除非你证明给我看。
请记住，现在的情况是，你要说服别人在你定义的概念上花时间进一步探索。如果你说服不了，对不起我的时间很宝贵，比起虚无缥缈的概念，我更愿意花时间在其他更有前景的方向。

铯_猪哥恐鸣

好的，再见。

我为我在这个帖子上花费的时间表示遗憾，下不为例。