楼主: migl

【^_^】复旦学生历时两年多破解11年“最小曼哈顿网络问题”--2009-06-24 [复制链接]

splendidrex

透魔

大波

Rank: 6 Rank: 6

积分: 5659
帖子: 3787
精华: 4
UID: 8709
性别: 男

21^#

发表于 2009-6-27 15:43:14 |只看该作者

俺们学校的。。。

It is not your aptitude but your attitude that determines your altitude.

Rubik's magic : best single 0.89s; best average 0.97s

使用道具举报

ggglgq

资深版主

Rank: 8 Rank: 8

积分: 4787
帖子: 1876
精华: 12
UID: 93
性别: 男

22^#

发表于 2009-6-28 17:21:36 |只看该作者

　　


好资料，加精！希望本文对解决魔方最少步问题有所借鉴！


　　

～～宇宙在旋转运动～

～魔方在循环变换～～

使用道具举报

littlehua

白魔

Rank: 1

积分: 83
帖子: 75
精华: 0
UID: 65853
性别: 保密

23^#

发表于 2009-6-29 22:45:54 |只看该作者

图论图论图论呀！！！！！！！

使用道具举报

conwood

蓝魔

Rank: 2

积分: 315
帖子: 256
精华: 0
UID: 39709
性别: 保密

24^#

发表于 2009-6-30 00:55:27 |只看该作者

“破解”这个词用的不合适。

下面这个pdf应该是郭的最新进展。
http://www.madalgo.au.dk/socg200 ... bstracts/4_Chin.pdf

从摘要上看，他们证明了“最小曼哈顿网络问题”是强NP-完全问题。从欣然爹的帖子来看，似乎在这之前，郭还给出了一个效率更高的近似算法。当然，最有意义的还是NP-完全性的证明。

摘要上说是把3-SAT问题规约到了这个问题，目前还没找到论文的全文，不过可以想象的是，那一定是个非常美妙的规约。

已有 1 人评分	经验	收起理由
sokoban	+ 10	感谢分享

总评分: 经验 + 10 查看全部评分

使用道具举报

migl

透魔

米糕咪够咯。。。。。。

Rank: 6 Rank: 6

积分: 6923
帖子: 1462
精华: 4
UID: 52005
性别: 男

25^#

发表于 2009-6-30 09:26:47 |只看该作者

“破解”这个词用得确实不合适，确切而言应该是“取得重大突破”。
从多方面的资料来看，中国人是站在了前辈们的肩膀上取得了又一“突破”。

===============

也不知道他们对魔方的感觉如何。
如果他们研究“最少步问题”的话，也许能取得轰动魔坛的成果。

最少步推箱子

使用道具举报

Lonely_7X

透魔

Rank: 6 Rank: 6

积分: 7727
帖子: 7132
精华: 3
UID: 31785
性别: 男

26^#

发表于 2009-6-30 09:45:25 |只看该作者

這個看不太懂啊不過感覺華人的智商在世界上還是相當有知名度的哦

Skype：ruixing_yu

使用道具举报

sokoban

银魔

Rank: 7 Rank: 7 Rank: 7

积分: 5289
帖子: 3234
精华: 19
UID: 13140
性别: 男

27^#

发表于 2009-7-5 20:34:32 |只看该作者

回复 24# 的帖子

conwood 兄说的中肯，这个问题主要还是一个算法设计问题。用“破解”一次的确不当。

另外新闻中的“阔别18年后，中国大陆数学家重返计算几何国际大会（SCG）舞台”
一句话中“阔别”、“重返...舞台”等字眼我感觉用得也不合适，有点怪怪的。

[ 本帖最后由 sokoban 于 2009-7-5 20:42 编辑 ]