N***l
发帖数: 52 | |
A*******r
发帖数: 768 | 2 展开讲讲，这个东西没听过哈
洋名叫啥？
有啥用处
【在 N***l 的大作中提到】
: 有兴趣一起讨论讨论么。
|
N***l
发帖数: 52 | 3 就是魔方啊，toys R us就有卖的那种魔方玩具。
任意给定一个魔方状态，用最小步数回复原状。
这个没有理论难点，因为是有限群操作，但是计算上
至今没有定论，去年有人用计算机把上限降到26步。
但是普遍乐观认为是20步。
简单计算从原状出发，魔方共有大概4.3*10^19种
状态，所以现有计算资源无法满足。
【在 A*******r 的大作中提到】
: 展开讲讲，这个东西没听过哈
: 洋名叫啥？
: 有啥用处
|
A*******r
发帖数: 768 | 4 怪不得
小时候就没弄明白过魔方是怎么玩的
【在 N***l 的大作中提到】
: 就是魔方啊，toys R us就有卖的那种魔方玩具。
: 任意给定一个魔方状态，用最小步数回复原状。
: 这个没有理论难点，因为是有限群操作，但是计算上
: 至今没有定论，去年有人用计算机把上限降到26步。
: 但是普遍乐观认为是20步。
: 简单计算从原状出发，魔方共有大概4.3*10^19种
: 状态，所以现有计算资源无法满足。
|
N***l
发帖数: 52 | 5 似乎魔方爱好者可以手动把几乎任何状态的魔方回复原状.
但是不能保证最优.
我关心的问题是任给一个魔方状态,如何找到最少步数恢复原状.
怪不得
小时候就没弄明白过魔方是怎么玩的
【在 A*******r 的大作中提到】
: 怪不得
: 小时候就没弄明白过魔方是怎么玩的
|
A*******r
发帖数: 768 | 6 很难很变态
第一反应就是动态规划
【在 N***l 的大作中提到】
: 似乎魔方爱好者可以手动把几乎任何状态的魔方回复原状.
: 但是不能保证最优.
: 我关心的问题是任给一个魔方状态,如何找到最少步数恢复原状.
:
: 怪不得
: 小时候就没弄明白过魔方是怎么玩的
|
N***l
发帖数: 52 | 7 传统的算法是这样建模的
魔方共54个小面,其中六个中心面永远不动
所以所有魔方的状态构成一个48阶排列群的子群G
G由6个生成元(每一面的90度旋转所代表的排列)生成.
从单位元(元始状态)出发,可以生成该群G的Caley graph
所以问题就变成任给一个G中的元素,寻找caley graph中
到达单位元的最短路径.
实际难点是,最初若干步新增节点跟层数几乎成指数关系,
Brute force算法到10层就不能再继续了,已经至少存了
好几个terabyte的数据了.
【在 A*******r 的大作中提到】
: 很难很变态
: 第一反应就是动态规划
|
A*******r
发帖数: 768 | 8 简单粗暴型方法的典范哈
看起来挺好，实际上行不通
不过这个以我的观点看来
对图论的要求太高了，需要挖很多细节出来
如果找不到更好的建模方法的话
【在 N***l 的大作中提到】
: 传统的算法是这样建模的
: 魔方共54个小面,其中六个中心面永远不动
: 所以所有魔方的状态构成一个48阶排列群的子群G
: G由6个生成元(每一面的90度旋转所代表的排列)生成.
: 从单位元(元始状态)出发,可以生成该群G的Caley graph
: 所以问题就变成任给一个G中的元素,寻找caley graph中
: 到达单位元的最短路径.
: 实际难点是,最初若干步新增节点跟层数几乎成指数关系,
: Brute force算法到10层就不能再继续了,已经至少存了
: 好几个terabyte的数据了.
|
A*******r
发帖数: 768 | 9 理论上这是个求一个图的半径的问题
可以在多项式时间内解决
实际上，由于点的个数太多
需要一些特殊的东西来把维数降下来
这个就很考细功夫了
【在 N***l 的大作中提到】
: 传统的算法是这样建模的
: 魔方共54个小面,其中六个中心面永远不动
: 所以所有魔方的状态构成一个48阶排列群的子群G
: G由6个生成元(每一面的90度旋转所代表的排列)生成.
: 从单位元(元始状态)出发,可以生成该群G的Caley graph
: 所以问题就变成任给一个G中的元素,寻找caley graph中
: 到达单位元的最短路径.
: 实际难点是,最初若干步新增节点跟层数几乎成指数关系,
: Brute force算法到10层就不能再继续了,已经至少存了
: 好几个terabyte的数据了.
|
d**a
发帖数: 71 | 10 我原来记过一套法则，肯定不长的，
回到原状态；现在忘了，而且不是理论上的
【在 N***l 的大作中提到】
: 似乎魔方爱好者可以手动把几乎任何状态的魔方回复原状.
: 但是不能保证最优.
: 我关心的问题是任给一个魔方状态,如何找到最少步数恢复原状.
:
: 怪不得
: 小时候就没弄明白过魔方是怎么玩的
|
