overhang 堆积木 - 能伸出桌面多远？

zhiqiangApril 13, 2007 科学精华区

来自University of Warwick的Mike Paterson星期二在Yao的理论计算机课堂上给了一个非常有趣的小讲座。

n个长度为1的砖块，叠起来能伸出桌面多远？（只考虑方块各平面都与桌面平行的情况）。

下面这种放法，很多人高中学物理的时候都见过吧？它用N个砖块伸出了大约1/2ln(N)。

上面这种叠放方法称为Harmonic Stacks，但它是最优的吗？下面这个例子可以看出，在3个砖块，我们就已经能做的更好了。

上面这个能继续往上堆么？很不幸

下面这个也不行

如果在上面再压很多砖块就可以了

下面是一种叠放方法，可以做到大约O(lnN).

20070412203214750

但它也不是最优的，下面是20个和30个方块的最优叠放方法，它比上面的要好

20070412203239218

下面是砖块数目比较少的时候的最优叠放方法。

20070412203140218

不过说了这么多，上面的方法都只能做到ln(N)的量级，而下面这个方法可以用N个砖块，往前伸出 N^(1/3)的长度。

而且，Mike Paterson及其合作者证明了，这种方法在量级上已经是最优的了！

查看更多关于Funny, TCS, 理论计算机笔记的内容。

20条留言 -> 跳到留言表格

At 2007.04.13 14:15, ricky said:

太强了，这个都能研究这么透彻。

[Reply]
At 2007.04.13 17:22, Chaney said:

貌似你发了两边
最新文章

* overhang 堆积木 - 能伸出桌面多远？
* overhang 堆积木 - 能伸出桌面多远？
我的rss reader也收到了两个通知。

[Reply]
- At 2007.04.13 21:26, zhiqiang said:
  
  嗯，不小心发了两次
  
  [Reply]
At 2007.04.13 19:36, kyant said:

其实从图形上看，我们一般人会想到最后一个是比较稳固的摆法，而且记得小时候玩积木就是这样，只是当时没有这么的积木供我们玩。遗憾。

[Reply]
- At 2008.02.21 17:44, guang said:
  
  其实不然。这个问题的内部约束条件，导致了非常奇异的积木布局，根本就不是直观能够想到的。直观想到的东西，可能就满足不了那个稳定
  或者最优条件。可以看看他的论文。
  
  那个最优化的证明，更是用了很深的数学知识。不是很容易就能想到的。他说第一个问题（找出最优方法）就花了差不多一年时间，而证明
  其最优，可能又是一年。
  
  做这些老树根题目，真的需要定心。
  
  [Reply]
At 2007.04.13 21:52, y0ungs said:

太强了，我想知道他是怎么弄完这个庞大的研究的。
一种一种情况计算的么？

[Reply]
At 2007.04.14 01:42, 前~博客 said:

佩服佩服
收藏了感觉自己的创造力已经枯竭了

[Reply]
At 2007.04.14 09:27, 常乐 said:

还曾经费尽脑汁的解出过1/2ln(N)这个结果怎么就没有想想这是不是最优呢……
呵呵

[Reply]
At 2007.04.14 19:06, 桑葚 said:

最后一个不稳定啊，风一吹就倒了哈

[Reply]
At 2007.04.14 23:57, qingchuan said:

最后一种能不能镂空呢？记得以前堆麻将的时候试过

[Reply]
At 2007.04.15 10:29, zhiqiang said:

Paterson也考虑了稳定性。上面这个例子，是局部不稳定的，但可以以很小的代价，弄成局部稳定的。

镂空应该是不行的。要有足够的重量，才能压住两头，两头不会坍塌下去。

[Reply]
At 2007.04.15 10:50, 江南sky said:

我看全都不稳定，最长的应该是最后一个吧

[Reply]
At 2007.04.19 06:07, sog said:

这个比较强，

让人想到了模拟退火算法……

不过这个东东，怎么和计算复杂性挂上钩的，Zhang-zi不厌其烦给大家阐释一下阿？

[Reply]
- At 2007.04.19 09:34, zhiqiang said:
  
  现在做研究题目都是靠抢的，这些researches一路扫过去，寸草不留啊，或者留下一些深埋地下，谁也啃不懂的千年老树根
  
  这玩意儿大致属于组合范围，跟理论计算机也算近亲吧。因为NP的难度主要便在于组合的难度上面。
  
  [Reply]
At 2007.04.21 11:00, 常乐 said:

这条留言本来是发到“提供分类RSS地址和分类邮件订阅”的，可是同样的操作，同样的email地址，发言的时候就是出错，在“作者”后红色字体显示“email is necessary”，说明原因Zhang-Zi能解决以下吗？

[Reply]
At 2007.04.24 19:55, zixys said:

这个有意思。

[Reply]
At 2007.12.14 16:58, 生日礼物 said:

真棒。。很有创新意识。按我的思维模式，就是第一种。
看到最后一种真是佩服啊。。哎。。

[Reply]
At 2008.05.02 11:46, Eagle_Fantasy said:

强，以前做过这个题，就是算出来开头那种方案就完了，也没有想过有没有更优的。确实开眼界了！

[Reply]
At 2008.05.19 22:35, hello said:

咱们学生和老师里面，谁愿意花一两年时间，将主要精力放在这样类似的问题上么？

我不相信他一开始就想到了最后的造型。仅仅借着一点微弱的感觉，在未知的路上摸索这么久，没有兴趣支持，真是难以维持。

[Reply]
At 2008.08.21 09:06, godie said:

小学老师说的是一块一块往上码.

[Reply]

« China Theory Day

黄花城水长城 »

overhang 堆积木 - 能伸出桌面多远？

查看更多关于Funny, TCS, 理论计算机笔记的内容。

20条留言 -> 跳到留言表格

阅微堂