唯有混沌 发表于 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 发表 http://bbs.mf8-china.com/images/common/back.gif
问题的实质是,除穷举法外,目前没有任何可行的算法描述,目前所谓的最小步算法或理论,匀是欺世盗名之作,目前最小步理论的讨论已没有必要,即是弄出来了,也只是旁证别人已经证明的问题.

[ 本帖最后由 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 编辑 ]
页: [1]
查看完整版本: 计算复杂度问题