splendidrex 发表于 2009-6-27 15:43:14

俺们学校的。。。

ggglgq 发表于 2009-6-28 17:21:36

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

littlehua 发表于 2009-6-29 22:45:54

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

conwood 发表于 2009-6-30 00:55:27

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

下面这个pdf应该是郭的最新进展。
http://www.madalgo.au.dk/socg2009/Images/Accepted%20papers%20w%20abstracts/4_Chin.pdf

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

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

migl 发表于 2009-6-30 09:26:47

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

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

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

Lonely_7X 发表于 2009-6-30 09:45:25

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

sokoban 发表于 2009-7-5 20:34:32

回复 24# 的帖子

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

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



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

ting12377 发表于 2009-7-14 13:19:03

不明白:L
HELP= =

wyy1998 发表于 2011-3-3 21:10:22

给中国人争了口气啊，顶一个！

aadxd 发表于 2011-3-3 21:12:48

虽然不懂，但要绝对支持！！希望多出现这样的人才！
页: 1 2 [3] 4
查看完整版本: 【^_^】复旦学生历时两年多破解11年“最小曼哈顿网络问题”--2009-06-24