@ 2011.11.06 , 10:35
37

煎饼排序真心很难NP-HARD

[-]
这不是一个笑话,有法国的计算机科学家证明了,给煎饼排序,并且能最优化的翻转它们,是一个非常困难的难题。

如果你有两个大小不一样的煎饼同时放在锅里,你就必须不停的翻转他们,来使得它们两面都被煎到,并且火候刚好。如图。这里的问题便是,需要翻多少次。

并且在煎饼 = n 个的时候,最优的翻转数又是多少呐?这便是法国科学团队Informatique de 提出的问题,虽然这问题拿给真正做煎饼的大厨来说可能并没有这么难,但是科学家将其定位称了NP-HARD(不存在有效算法的非确定性多项式)。

据Informatique de 说他们目前只能搞定 n<=19 的问题,再往上便NP-HARD 了。 实际上这个问题,除了煎饼之外还有更实际的用途,例如基因组排序等等。 @oioi:擦,真不知道在说什么。还请达人讲解。


给这篇稿打赏,让译者更有动力
支付宝打赏 [x]
您的大名: 打赏金额:

2.6
赞一个 (3)

TOTAL COMMENTS: 37+1

  1. 940653

    似乎没什么意义

  2. yorlereiyo
    @6 years ago
    940657

    楼上ntr…….

  3. 940661

    N个煎饼叠在一起,用铲子不停地翻,直到每个煎饼的每个面都接触煎锅一次,问最少要用铲子铲几次吧?

  4. Oling Cat
    @6 years ago
    940666

    离散数学里的空间复杂度,分析算法用的,程序员应该都知道啊?

    [18] XX [2] 回复 [0]
  5. 有什么想法
    @6 years ago
    940668

    不会用个大点的锅啊,钱不是这样省的有木有!

  6. ET来过
    @6 years ago
    940671

    还可以应用在煎蛋上,嗯。

  7. 940672

    每个煎饼的味道一样,那有什么好吃的?

  8. Oling Cat
    @6 years ago
    940673

    具体不大清楚,因为这个还是没被证明的P?=NP,跟哥德巴赫猜想在同一个级别….

  9. 狻猊
    @6 years ago
    940676

    我看成煎蛋了

    [77] XX [1] 回复 [0]
  10. race2fly
    @6 years ago
    940680

    主要是达到结果的近似完美结局,理论上却是很难的东西。实际上举得煎蛋这个示例,很难分辨出来的

  11. 塌方
    @6 years ago
    940683

    我看着像在铲狗屎。。。。

  12. PeterPan
    @6 years ago
    940689

    我想到了 汉诺塔。。。。。

  13. 940690

    NP-hard不是

  14. 940692

    NP-hard不是“非确定性多项式(复杂度)”,NP才是。NP-hard是“至少有NPC那么难”,而NPC是指NP范畴内最难的那一部分。NP-hard也包括难度超出NP范畴的那些。

  15. 温柔可爱小狗狗
    @6 years ago
    940717

    不想成为数学家的厨子,不是个好厨子

  16. Delbert
    @6 years ago
    940721

    我看成了“给煎蛋排序真心很难”…

  17. wecing
    @6 years ago
    940727

    时间复杂度:在屏幕上打印出从1到N的N个数字,复杂度为O(N)。
    输出1-N之内所有满足1 <= a <= b <= N的点(a, b),复杂度为O(N*N)。
    O(N*N)的复杂度可以视为比O(N)的高一个数量级。

    总而言之就是这个问题的复杂度不是类似于O(N*2)的多项式,而是像O(2^N)的增长很快的模式。N稍微增大一点,所需要的时间就会增大很多很多很多。

  18. 940778

    P=NP not proved

  19. 940796

    实际上这个问题,除了煎饼之外还有更实际的用途,例如煎蛋

  20. booman
    @6 years ago
    940805

    给煎蛋排序也很难,所以经常超载。。。

  21. fliesfaries
    @6 years ago
    940807

    原论文在此:http://arxiv.org/PS_cache/arxiv/pdf/1111/1111.0434v1.pdf

    其中说道“原始煎蛋排序问题”是这样的: 煎蛋娘的烹饪技术很奇葩,每个蛋大小都不一样,我要把随意摆放的一叠蛋按照从小到大的顺序叠好端出来,方法只能是从一叠蛋中间把手插进去,把上面的蛋们全部翻个个,这样来排序。那么问题是,对于任意数量的蛋是否存在一个插入-反转次数的上限?

    现在法国科学家们说了:20个蛋以上无解

  22. 浅栖
    @6 years ago
    940808

    看到NP HARD我鸡冻了

  23. 940847

    食堂的大厨表示给出最优解毫无压力

  24. Will Zhong
    @6 years ago
    940864

    曾经见过与这个问题类似的问题,但当时的解法只能给出一个上界,算不上是最优的解法。
    看来最优的解法还是得搜索啊。

  25. Forise
    @6 years ago
    940865

    我来看一楼的,np问题没什么意义……..

  26. 941084

    这问题如果解决了,人工智能就不远了
    加油!

  27. meng_u
    @6 years ago
    941088

    换成煎蛋应该就煎蛋,noop,简单了

  28. 猪猪的镁镁
    @6 years ago
    941160

    小学数学课本也有这个内容。想教死人咩!!!!

  29. 941169

    就是比尔盖茨发明的算法…
    在有特殊设备时(O(1)模拟翻转的计算机)时
    可以证明是一个O(3n+2)的问题…
    但无法证明最优解的精确解

  30. 941180

    http://en.wikipedia.org/wiki/Pancake_sorting

  31. 珜羽
    @6 years ago
    941188

    把煎饼看成煎蛋的举手。。。

  32. 天净杀
    @6 years ago
    941302

    介绍个不需要反的煎饼——鸡蛋不翻,请看百科http://baike.baidu.com/view/2569765.htm
    身在地球上唯一能吃到的地方,很自豪啊。

  33. 天杀包子神
    @6 years ago
    941385

    就是模糊问题吧……比如掉一根头发不是秃头那个……不确定= =

  34. 约尔曼冈德
    @6 years ago
    941574

    天净杀 @ 2011-11-06 21:08:55 #32
    介绍个不需要反的煎饼——鸡蛋不翻,请看百科http://baike.baidu.com/view/2569765.htm
    身在地球上唯一能吃到的地方,很自豪啊。

    这个比法国科学家高到那里去了

  35. sanders.yao
    @6 years ago
    941646

    NP貌似是程序复杂度的一种程度

  36. 植物人
    @6 years ago
    942076

    翻译成容易理解的表述就是:
    假设锅子的温度是X
    煎饼A1,A2,A3…..AN的直径是Y1,Y2,Y3……YN
    煎饼AN的完美翻转时间TN是与X,YN有关的一组函数。
    每个煎饼有两面AN-1,AN-2
    AN-1和AN-2
    每次翻转的时间是一个固定值
    接触锅的一面的成熟度和时间成函数关系

    当然了 继续说下去还有很多影响的因素! 不过就算是以上这些也够忙得乐

  37. 946855

    又一个np难问题诞生了。。。。
    马上信息学奥赛的路过。。

发表评论


24H最赞