今天香港中文大学的Prof. Cai给我们上 graph algorithm.第一节课上教我们玩魔方,先给每人发了一个.魔方的解法,在网上已经有无数了,基本上的思路都是几个定式,玩的时候记住这些定式即可.课上 Cai 给我们演示了一个他自创的定式,很可惜,我目前为止只学会弄出一面来.
OK ,这篇文章的主要目的是讲魔方里的数学,对魔方的群结构研究网上也已经有很多,这里不谈了.魔方总共有(8! × 3^8−1^) × (12! × 2^12−1^)/2 = 43252003274489856000=4.3× 10^19^ 个不同的状态.每个状态看作图上的一个点,则解魔方问题可以视作求一个超大图上的路径问题.这个图是如此之大,使得看上去求最短路这么简单的问题都变得非常困难,事实上,用计算机也不可能直接算.
虽然这个图是如此之大,而且边很少(每个顶点只引出 12 条边),但这个图的直径却非常小.可以证明,任何一种魔方的状态,都可以在 26 步之内复原.(见Optimal solutions for Rubik's Cube)
这样的图与以前提到过的洗牌模型里面的图非常相似,结构简单,定点巨多,但混合速度却特别快(从一点会以非常快的速度达到其它点),做算法的很喜欢这种图.
一个看上去简单实际上 OPEN 的图论题 相似度: 0.120
一个简单图的三染色算法问题 相似度: 0.069
完美洗牌问题线性算法的两篇论文 相似度: 0.055
2007 年,我们讨论过一个算法问题, perfect shuffle ,据称是个微软面试题:
不知道最初来源于哪里,这个数字我最早是从李笑来那里看到的,我看完之后随便搜了几个数字,觉得结果也大同小异,心想为何笑来突然关注这个数字.后来才发现网上被传得到处都是,包括我的老同学也参与了,最后发现其根源是下面这条"新闻"
2019 年罗马尼亚数学大师赛第三题 相似度: 0.051
这次中国队在罗马尼亚数学大师赛败北,引起巨大的舆论论战,甚至上了人民日报的评论.以前从来没出现过这种情况.作为吃瓜群众,觉得特别有意思.
图片搜索的原理 相似度: 0.050
Google 新推出了图片搜索,可直接上传图片(或者用图片链接)搜索网络上的相似图片,例子.估计还没多少人意识到,这玩意儿是人肉搜索的大杀器,以后大家还是少上传私人照片到公开网络.