魔方吧·中文魔方俱乐部

标题: 计算复杂度问题 [打印本页]

作者: 唯有混沌 时间: 2011-6-19 20:49:52 标题: 计算复杂度问题

运算T: ”求n阶六轴魔方上某打乱状态还原的最短路径。“

T是否可以在关于n的多项式时间内完成？

作者: 肥嘟嘟左卫门 时间: 2011-6-19 21:04:35

不懂楼主在说什么数学不好的路过

作者: 小明的马甲 时间: 2011-6-19 22:03:32

我记得有报道称是NP问题，至少当前没有找到多项式界算法。

作者: pengw 时间: 2011-6-22 14:32:57

问题的实质是,除穷举法外,目前没有任何可行的算法描述,目前，如循环变换之类的最小步算理论（实为相似变换）,匀是欺世盗名之作,目前最小步理论的讨论已没有必要,即是弄出来了,也只是旁证别人已经证明的问题.

[ 本帖最后由 pengw 于 2011-6-26 07:29 编辑 ]

作者: 铯_猪哥恐鸣 时间: 2011-6-23 20:57:22

楼上不懂什么叫算法= =大家不要理他。。

作者: pengw 时间: 2011-6-24 15:34:56

即然别人已经找出答案，这个版是不是可以解散了？哈哈哈

作者: jinxian 时间: 2011-6-26 08:08:14

　　

为了配合“谩骂、改贴、删帖大师”的工作，在这里备份一下！

原帖地址： http://bbs.mf8-china.com/viewthread.php?tid=2473

原帖楼数： http://bbs.mf8-china.com/viewthread.php?tid=2473&extra=&page=5  45 楼

　　

原帖由 pengw 于 2011-6-22 14:32 发表
问题的实质是,除穷举法外,目前没有任何可行的算法描述,目前所谓的最小步算法或理论,匀是欺世盗名之作,目前最小步理论的讨论已没有必要,即是弄出来了,也只是旁证别人已经证明的问题.

[ 本帖最后由 pengw 于 2011-6-22 14:34 编辑 ]

　　

这篇文章，再配上作者自己的这段评价，真可谓是“恰如其分”了，呵呵！
　　
　　
　　
　　

作者: shifujun 时间: 2011-6-26 21:47:21

目前还是NP问题啊。

作者: 小明的马甲 时间: 2011-6-26 23:51:06

话说储存二阶所有状态只需要不到720KB。。- -

还有多说一句。。忍大师您还没骂爽么？～

[ 本帖最后由小明的马甲于 2011-6-26 23:52 编辑 ]

欢迎光临魔方吧·中文魔方俱乐部 (http://bbs.mf8-china.com/)