@ 2011.11.06 , 10:35

煎饼排序真心很难NP-HARD

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

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

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

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


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

2.5
赞一个 (3)

24H最赞