Chinaunix首页 | 论坛 | 博客
  • 博客访问: 5175480
  • 博文数量: 1696
  • 博客积分: 10870
  • 博客等级: 上将
  • 技术积分: 18357
  • 用 户 组: 普通用户
  • 注册时间: 2007-03-30 15:16
文章分类
文章存档

2017年(1)

2016年(1)

2015年(1)

2013年(1)

2012年(43)

2011年(17)

2010年(828)

2009年(568)

2008年(185)

2007年(51)

分类:

2010-06-08 02:38:55

魔方今天香港中文大学的Prof. Cai给我们上graph algorithm。第一节课上教我们玩魔方,先给每人发了一个。我喜欢这样的教学方法 :)

魔方的解法,在网上已经有了,基本上的思路都是几个定式,玩的时候记住这些定式即可。课上Cai给我们演示了一个他自创的定式,很可惜,我目前为止只学会弄出一面来。

OK,这篇文章的主要目的是讲魔方里的数学,对魔方的群结构研究网上也已经有很多,这里不谈了。魔方总共有(8! × 38−1) × (12! × 212−1)/2 = 43252003274489856000=4.3× 1019个不同的状态。每个状态看作图上的一个点,则解魔方问题可以视作求一个超大图上的路径问题。这个图是如此之大,使得看上去求最短路这么简单的问题都变得非常困难,事实上,用计算机也不可能直接算。

虽然这个图是如此之大,而且边很少(每个顶点只引出12条边),但这个图的直径却非常小。可以证明,任何一种魔方的状态,都可以在26步之内复原。(见)

这样的图与以前提到过的洗牌模型里面的图非常相似,结构简单,定点巨多,但混合速度却特别快(从一点会以非常快的速度达到其它点),做算法的很喜欢这种图。

阅读(590) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~