魔方吧·中文魔方俱乐部

 找回密码
 注册
搜索
热搜: 魔方
楼主: migl

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

透魔

大波

Rank: 6Rank: 6

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

八年元老

发表于 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

使用道具 举报

Rank: 8Rank: 8

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

魔方理论探索者 十年元老

发表于 2009-6-28 17:21:36 |显示全部楼层
  
  
  
    好资料,加精! 希望本文对解决魔方最少步问题有所借鉴!
  
  
  
~~ 宇宙在旋转运动 ~~ 魔方在循环变换 ~~

使用道具 举报

Rank: 1

积分
83
帖子
75
精华
0
UID
65853
性别
保密
发表于 2009-6-29 22:45:54 |显示全部楼层
图论  图论  图论呀!!!!!!!

使用道具 举报

Rank: 2

积分
315
帖子
256
精华
0
UID
39709
性别
保密
发表于 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   查看全部评分

使用道具 举报

透魔

米糕咪够咯。。。。。。

Rank: 6Rank: 6

积分
6923
帖子
1462
精华
4
UID
52005
性别
发表于 2009-6-30 09:26:47 |显示全部楼层

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

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

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

使用道具 举报

Rank: 6Rank: 6

积分
7727
帖子
7132
精华
3
UID
31785
性别
发表于 2009-6-30 09:45:25 |显示全部楼层
這個看不太懂啊 不過感覺華人的智商在世界上還是相當有知名度的哦


Skype:ruixing_yu

使用道具 举报

Rank: 7Rank: 7Rank: 7

积分
5262
帖子
3216
精华
19
UID
13140
性别

论坛建设奖 八年元老

发表于 2009-7-5 20:34:32 |显示全部楼层

回复 24# 的帖子

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

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



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

使用道具 举报

Rank: 1

积分
27
帖子
26
精华
0
UID
98870
性别
保密
发表于 2009-7-14 13:19:03 |显示全部楼层
不明白
HELP= =

使用道具 举报

Rank: 3Rank: 3

积分
783
帖子
737
精华
0
UID
1278340
性别

两年元老

发表于 2011-3-3 21:10:22 |显示全部楼层
给中国人争了口气啊,顶一个!
现在快进入魔方收藏界了……

使用道具 举报

红魔

言佳足艮手戈匕匕悚负

Rank: 4

积分
1900
帖子
1625
精华
1
UID
106818
性别
兴趣爱好
理论

两年元老

发表于 2011-3-3 21:12:48 |显示全部楼层
虽然不懂,但要绝对支持!!希望多出现这样的人才!

使用道具 举报

您需要登录后才可以回帖 登录 | 注册

Archiver|手机版|魔方吧·中文魔方俱乐部

GMT+8, 2024-3-29 01:36

Powered by Discuz! X2

© 2001-2011 Comsenz Inc.

回顶部