overhang 堆积木 - 能伸出桌面多远？
来自University of Warwick的Mike Paterson星期二在Yao的理论计算机课堂上给了一个非常有趣的小讲座。
n个长度为1的砖块，叠起来能伸出桌面多远？（只考虑方块各平面都与桌面平行的情况）。
下面这种放法，很多人高中学物理的时候都见过吧？它用N个砖块伸出了大约1/2ln(N)。
上面这种叠放方法称为Harmonic Stacks，但它是最优的吗？下面这个例子可以看出，在3个砖块，我们就已经能做的更好了。
上面这个能继续往上堆么？很不幸
下面这个也不行
如果在上面再压很多砖块就可以了
下面是一种叠放方法，可以做到大约O(lnN).
但它也不是最优的，下面是20个和30个方块的最优叠放方法，它比上面的要好
下面是砖块数目比较少的时候的最优叠放方法。
不过说了这么多，上面的方法都只能做到ln(N)的量级，而下面这个方法可以用N个砖块，往前伸出 N^(1/3)的长度。
而且，Mike Paterson及其合作者证明了，这种方法在量级上已经是最优的了！
Q.E.D., ©zhiqiang, 2007.04.13。请参考右边的相关文章列表。
太强了，这个都能研究这么透彻。
貌似你发了两边
最新文章
* overhang 堆积木 - 能伸出桌面多远？
* overhang 堆积木 - 能伸出桌面多远？
我的rss reader也收到了两个通知。
其实从图形上看，我们一般人会想到最后一个是比较稳固的摆法，而且记得小时候玩积木就是这样，只是当时没有这么的积木供我们玩。遗憾。
嗯，不小心发了两次
太强了，我想知道他是怎么弄完这个庞大的研究的。
一种一种情况计算的么？
佩服佩服
收藏了 感觉自己的创造力已经枯竭了
还曾经费尽脑汁的解出过1/2ln(N)这个结果怎么就没有想想这是不是最优呢……
呵呵
最后一个不稳定啊，风一吹就倒了哈
最后一种能不能镂空呢 ？记得以前堆麻将的时候试过
Paterson也考虑了稳定性。上面这个例子，是局部不稳定的，但可以以很小的代价，弄成局部稳定的。
镂空应该是不行的。要有足够的重量，才能压住两头，两头不会坍塌下去。
我看全都不稳定，最长的应该是最后一个吧
这个比较强，
让人想到了模拟退火算法……
不过这个东东，怎么和计算复杂性挂上钩的，Zhang-zi不厌其烦给大家阐释一下阿？
现在做研究题目都是靠抢的，这些researches一路扫过去，寸草不留啊，或者留下一些深埋地下，谁也啃不懂的千年老树根
这玩意儿大致属于组合范围，跟理论计算机也算近亲吧。因为NP的难度主要便在于组合的难度上面。
这条留言本来是发到“提供分类RSS地址和分类邮件订阅”的，可是同样的操作，同样的email地址，发言的时候就是出错，在“作者”后红色字体显示“email is necessary”，说明原因Zhang-Zi能解决以下吗？
这个有意思。
真棒。。 很有创新意识。按我的思维模式，就是第一种。
看到最后一种真是佩服啊。。哎。。
其实不然。这个问题的内部约束条件，导致了非常奇异的积木布局，根本就不是直观能够想到的。直观想到的东西，可能就满足不了那个稳定
或者最优条件。可以看看他的论文。
那个最优化的证明，更是用了很深的数学知识。不是很容易就能想到的。他说第一个问题（找出最优方法）就花了差不多一年时间，而证明
其最优，可能又是一年。
做这些老树根题目，真的需要定心。
强，以前做过这个题，就是算出来开头那种方案就完了，也没有想过有没有更优的。确实开眼界了！
咱们学生和老师里面，谁愿意花一两年时间，将主要精力放在这样类似的问题上么？
我不相信他一开始就想到了最后的造型。仅仅借着一点微弱的感觉，在未知的路上摸索这么久，没有兴趣支持，真是难以维持。
小学老师说的是一块一块往上码.
哪里能找到这个最优结果的证明？
大概的证明思路是什么？
见 http://arxiv.org/abs/0710.2357。
没有仔细读过，思路好像就是力学方程。
Pingback: Si-World » Blog Archive » 关于堆砖块的一篇blog
很有趣，我。引用了哈
Pingback: overhang 堆积木 – 能伸出桌面多远？ | 宇宙的心弦