{"id":30960,"date":"2021-12-13T22:52:09","date_gmt":"2021-12-13T14:52:09","guid":{"rendered":"https:\/\/swarma.org\/?p=30960"},"modified":"2021-12-13T22:52:09","modified_gmt":"2021-12-13T14:52:09","slug":"%e4%bb%80%e4%b9%88%e6%98%af%e7%bb%84%e5%90%88%e4%bc%98%e5%8c%96-%e9%9b%86%e6%99%ba%e7%99%be%e7%a7%91","status":"publish","type":"post","link":"https:\/\/swarma.org\/?p=30960","title":{"rendered":"\u4ec0\u4e48\u662f\u7ec4\u5408\u4f18\u5316 | \u96c6\u667a\u767e\u79d1"},"content":{"rendered":"
\n

<\/p>\n


<\/p>\n

\u201c\u96c6\u667a\u767e\u79d1\u7cbe\u9009\u201d\u662f\u4e00\u4e2a\u957f\u671f\u4e13\u680f\uff0c\u6301\u7eed\u4e3a\u5927\u5bb6\u63a8\u9001\u590d\u6742\u6027\u79d1\u5b66\u76f8\u5173\u7684\u57fa\u672c\u6982\u5ff5\u548c\u8d44\u6e90\u4fe1\u606f\u3002\u4f5c\u4e3a\u96c6\u667a\u4ff1\u4e50\u90e8\u7684\u5f00\u6e90\u79d1\u5b66\u9879\u76ee\uff0c\u96c6\u667a\u767e\u79d1\u5e0c\u671b\u6253\u9020\u590d\u6742\u6027\u79d1\u5b66\u9886\u57df\u6700\u5168\u9762\u7684\u767e\u79d1\u5168\u4e66\uff0c\u6b22\u8fce\u5bf9\u590d\u6742\u6027\u79d1\u5b66\u611f\u5174\u8da3\u3001\u70ed\u7231\u77e5\u8bc6\u6574\u7406\u548c\u5206\u4eab\u7684\u670b\u53cb\u52a0\u5165\uff01
<\/span><\/section>\n

<\/section>\n
\u672c\u6587\u662f\u5bf9\u96c6\u667a\u767e\u79d1\u4e2d\u201c\u7ec4\u5408\u4f18\u5316<\/span>\u201d\u8bcd\u6761\u7684\u6458\u5f55\uff0c\u53c2\u8003\u8d44\u6599\u53ca\u76f8\u5173\u8bcd\u6761\u8bf7\u53c2\u9605\u767e\u79d1\u8bcd\u6761\u539f\u6587\u3002<\/span><\/section>\n

<\/section>\n
\n
\n
\n
\n
\n
\n
\n
\n
\n
\n

\u672c\u8bcd\u6761\u7531\u96c6\u667a\u4ff1\u4e50\u90e8\u4f17\u5305\u751f\u4ea7\uff0c\u96be\u514d\u5b58\u5728\u7eb0\u6f0f\u548c\u95ee\u9898\uff0c\u6b22\u8fce\u5927\u5bb6\u7559\u8a00\u53cd\u9988\u6216\u8005\u524d\u5f80\u5bf9\u5e94\u7684\u767e\u79d1\u8bcd\u6761\u9875\u9762\u8fdb\u884c\u4fee\u6539\uff0c\u4e00\u7ecf\u4fee\u6539\uff0c\u53ef\u4ee5\u83b7\u5f97\u5bf9\u5e94\u7684\u79ef\u5206\u5956\u52b1\u5662\uff01<\/em><\/span><\/p>\n


<\/p>\n

\n
\n
\n
\n
\n
\n
\n
\n
\n
\n

\u76ee\u5f55<\/strong><\/p>\n


<\/p>\n

\n
\u4e00\u3001\u5e94\u7528<\/span><\/strong><\/section>\n
\u4e8c\u3001\u65b9\u6cd5<\/strong><\/span><\/section>\n
\u4e09\u3001\u5f62\u5f0f\u5316\u5b9a\u4e49<\/strong><\/span><\/section>\n
\u56db\u3001NP\u4f18\u5316\u95ee\u9898<\/strong><\/span><\/section>\n
\u4e94\u3001\u7279\u5b9a\u95ee\u9898<\/strong><\/span><\/section>\n
\u516d\u3001<\/strong>\u7f16\u8005\u63a8\u8350<\/strong><\/strong><\/strong><\/span><\/section>\n
\u4e03\u3001\u767e\u79d1\u9879\u76ee\u5fd7\u613f\u8005\u62db\u52df<\/strong><\/strong><\/strong><\/span><\/section>\n<\/section>\n<\/section>\n<\/section>\n<\/section>\n<\/section>\n<\/section>\n<\/section>\n<\/section>\n<\/section>\n<\/section>\n<\/section>\n<\/section>\n<\/section>\n<\/section>\n<\/section>\n<\/section>\n<\/section>\n<\/section>\n<\/section>\n<\/section>\n<\/section>\n
<\/section>\n


<\/p>\n

\u4e00\u4e2a\u52a0\u6743\u5e73\u9762\u56fe\u7684\u6700\u5c0f<\/span>\u751f\u6210\u6811<\/span> Minimum Spanning Tree\u3002\u627e\u5230\u6700\u5c0f<\/span>\u751f\u6210\u6811<\/span>\u662f\u4e00\u4e2a\u6d89\u53ca\u7ec4\u5408\u4f18\u5316 Combinatorial Optimization\u7684\u5e38\u89c1\u95ee\u9898\u3002<\/span><\/p>\n


<\/p>\n

\u7ec4\u5408\u4f18\u5316\u662f\u6570\u5b66\u4f18\u5316\u65b9\u6cd5 Mathematical Optimization\u7684\u4e00\u4e2a\u5b50\u9886\u57df\uff0c\u4e0e\u8fd0\u7b79\u5b66 Operations Research\u3001\u7b97\u6cd5\u7406\u8bba Algorithm Theory\u548c\u8ba1\u7b97\u590d\u6742\u6027\u7406\u8bba Computational Complexity\u6709\u5173\u3002\u5b83\u5728<\/span>\u4eba\u5de5\u667a\u80fd<\/span> Artificial Intelligence\u3001<\/span>\u673a\u5668\u5b66\u4e60<\/span> Machine Learning\u3001\u62cd\u5356\u7406\u8bba Auction Theory\u3001\u8f6f\u4ef6\u5de5\u7a0b Software Engineering\u3001\u5e94\u7528\u6570\u5b66 Applied Mathematics\u548c\u7406\u8bba\u8ba1\u7b97\u673a\u79d1\u5b66 Theoretical Computer Science\u7b49\u9886\u57df\u6709\u7740\u91cd\u8981\u7684\u5e94\u7528\u3002<\/span><\/p>\n


\u7ec4\u5408\u4f18\u5316\u4e3b\u8981\u662f\u4ece\u4e00\u4e2a\u6709\u9650\u7684\u5bf9\u8c61\u96c6\u5408\u4e2d\u5bfb\u627e\u4e00\u4e2a\u6700\u4f73\u5bf9\u8c61\u3002\u5728\u8bb8\u591a\u8fd9\u6837\u7684\u95ee\u9898\u4e2d\uff0c\u7a77\u4e3e\u641c\u7d22 exhaustive search \u662f\u4e0d\u6613\u5904\u7406\u7684\u3002\u5982\u679c\u8fd9\u4e9b\u4f18\u5316\u95ee\u9898\u53ef\u884c\u89e3\u96c6\u662f\u79bb\u6563\u7684\uff0c\u6216\u8005\u53ef\u884c\u89e3\u96c6\u53ef\u4ee5\u5316\u4e3a\u79bb\u6563\u7684\uff0c\u90a3\u4e48\u53ef\u4ee5\u5728\u95ee\u9898\u8303\u56f4\u5185\u8fdb\u884c\u8fd0\u7b97\uff0c\u5176\u76ee\u6807\u662f\u627e\u5230\u6700\u4f18\u89e3\u3002\u5178\u578b\u7684\u95ee\u9898\u662f\u65c5\u884c\u5546\u95ee\u9898 Traveling Salesman Problem(\u201c TSP\u201d)\u3001\u6700\u5c0f<\/span>\u751f\u6210\u6811<\/span>\u95ee\u9898(\u201c MST\u201d)\u548c\u80cc\u5305\u95ee\u9898 Knapsack Problem\u3002<\/span><\/p>\n


\u4e00\u4e9b\u7814\u7a76\u6587\u732e<\/span>\u8ba4\u4e3a\u79bb\u6563\u4f18\u5316 Discrete Optimization \u662f\u7531\u6574\u6570\u89c4\u5212 Integer Programming\u548c\u7ec4\u5408\u4f18\u5316\u7ec4\u6210\u7684\uff08\u53cd\u8fc7\u6765\u7531\u89e3\u51b3\u56fe\u7ed3\u6784\u7684\u4f18\u5316\u95ee\u9898\u7ec4\u6210\uff09\uff0c\u5c3d\u7ba1\u6240\u6709\u8fd9\u4e9b\u4e3b\u9898\u7684\u7814\u7a76\u6587\u732e\u90fd\u7d27\u5bc6\u5730\u4ea4\u7ec7\u5728\u4e00\u8d77\u3002\u5b83\u901a\u5e38\u6d89\u53ca\u5982\u4f55\u6709\u6548\u5730\u5206\u914d\u7528\u4e8e\u5bfb\u627e\u6570\u5b66\u95ee\u9898\u89e3\u51b3\u65b9\u6848\u7684\u8d44\u6e90\u7684\u51b3\u7b56\u3002<\/span><\/p>\n


<\/span><\/p>\n

\n
\n
\n
\n
\n
\n
\n
\n
\n
\n
\n
\n
\n


<\/p>\n

\n
\n
\n
\n
\n
\n
\n
\n
\n
\n
\n
\n
\n

<\/section>\n

<\/section>\n
\n
<\/svg><\/section>\n<\/section>\n<\/section>\n
\n

\u5e94\u7528<\/span><\/strong><\/strong><\/span><\/strong><\/strong><\/p>\n<\/section>\n

\n

<\/section>\n
<\/strong>
<\/section>\n<\/section>\n<\/section>\n<\/section>\n<\/section>\n<\/section>\n<\/section>\n<\/section>\n<\/section>\n<\/section>\n<\/section>\n<\/section>\n<\/section>\n<\/section>\n<\/section>\n<\/section>\n<\/section>\n<\/section>\n<\/section>\n<\/section>\n<\/section>\n<\/section>\n<\/section>\n<\/section>\n<\/section>\n<\/section>\n<\/section>\n


<\/p>\n

\u7ec4\u5408\u4f18\u5316\u7684\u5e94\u7528\u5305\u62ec\u4f46\u4e0d\u9650\u4e8e:<\/span>
<\/h2>\n
    \n
  • \n
    \u7269\u6d41<\/span><\/span><\/section>\n<\/li>\n
  • \n
    \u4f9b\u5e94\u94fe\u4f18\u5316<\/span><\/span><\/section>\n<\/li>\n
  • \n
    \u53d1\u5c55\u6700\u597d\u8f90\u6761\u548c\u76ee\u7684\u5730\u7684\u822a\u7a7a\u516c\u53f8\u7f51\u7edc<\/span><\/section>\n<\/li>\n
  • \n
    \u51b3\u5b9a\u8f66\u961f\u4e2d\u54ea\u8f86\u51fa\u79df\u8f66\u6765\u8f7d\u5ba2<\/span><\/section>\n<\/li>\n
  • \n
    \u786e\u5b9a\u8fd0\u9001\u5305\u88f9\u7684\u6700\u4f73\u65b9\u5f0f<\/span><\/section>\n<\/li>\n
  • \n
    \u5236\u5b9a\u6700\u4f73\u5de5\u4f5c\u5206\u914d<\/span><\/section>\n<\/li>\n<\/ul>\n

    <\/section>\n
    \n
    \n
    \n
    \n
    \n
    \n
    \n
    \n
    \n
    \n
    \n
    \n
    \n


    <\/p>\n

    \n
    \n
    \n
    \n
    \n
    \n
    \n
    \n
    \n
    \n
    \n
    \n
    \n

    <\/section>\n

    <\/section>\n
    \n
    <\/svg><\/section>\n<\/section>\n<\/section>\n
    \n

    \u65b9\u6cd5<\/span><\/strong><\/strong><\/span><\/strong><\/strong><\/p>\n<\/section>\n

    \n

    <\/section>\n
    <\/strong><\/section>\n<\/section>\n<\/section>\n<\/section>\n<\/section>\n<\/section>\n<\/section>\n<\/section>\n<\/section>\n<\/section>\n<\/section>\n<\/section>\n<\/section>\n<\/section>\n<\/section>\n<\/section>\n<\/section>\n<\/section>\n<\/section>\n<\/section>\n<\/section>\n<\/section>\n<\/section>\n<\/section>\n<\/section>\n<\/section>\n<\/section>\n

    <\/span>
    <\/h2>\n
    \u5bf9\u4e8e\u67d0\u4e9b\u7279\u6b8a\u7684\u79bb\u6563\u4f18\u5316\u95ee\u9898\uff0c\u6709\u5927\u91cf\u7684\u6587\u732e\u662f\u5173\u4e8e\u591a\u9879\u5f0f\u65f6\u95f4\u7b97\u6cd5 Polynomial-Time Algorithm\u7684\uff0c\u5176\u4e2d\u76f8\u5f53\u4e00\u90e8\u5206\u662f\u901a\u8fc7\u7ebf\u6027\u89c4\u5212 Linear Programming\u7406\u8bba\u7edf\u4e00\u8d77\u6765\u7684\u3002\u5c5e\u4e8e\u8fd9\u4e2a\u6846\u67b6\u7684\u7ec4\u5408\u4f18\u5316\u95ee\u9898\u7684\u4e00\u4e9b\u4f8b\u5b50\u5305\u62ec\u6700\u77ed\u8def\u5f84 Shortest paths\u548c\u6700\u77ed\u8def\u5f84\u6811 Shortest-path Tree\u3001\u6d41\u548c\u5faa\u73af Flows And Circulations\u3001<\/span>\u751f\u6210\u6811<\/span>\u3001\u5339\u914d\u548c\u62df\u9635 Matching And Matroid Problems\u95ee\u9898\u3002<\/span><\/section>\n

    \u5bf9\u4e8eNP\u5b8c\u5168 NP-Complete\u7684\u79bb\u6563\u4f18\u5316\u95ee\u9898\uff0c\u76ee\u524d\u7684\u7814\u7a76\u6587\u732e\u5305\u62ec\u4ee5\u4e0b\u4e3b\u9898:<\/span><\/section>\n
      \n
    • \n
      \u591a\u9879\u5f0f\u65f6\u95f4\u53ef\u7cbe\u786e\u89e3\u51b3\u7684\u7279\u6b8a\u95ee\u9898\uff08\u4f8b\u5982,\u56fa\u5b9a\u53c2\u6570\u53ef\u89e3\uff09<\/span><\/section>\n<\/li>\n
    • \n
      \u5728\u201c\u968f\u673a\u201d\u5b9e\u4f8b\u4e0a\u8868\u73b0\u826f\u597d\u7684\u7b97\u6cd5\uff08\u4f8b\u5982\uff0cTSP\uff09<\/span><\/section>\n<\/li>\n
    • \n
      \u8fd1\u4f3c\u7b97\u6cd5 Approximation Algorithm\u5728\u591a\u9879\u5f0f\u65f6\u95f4\u5185\u8fd0\u884c\u5e76\u627e\u5230\u4e00\u4e2a\u201c\u63a5\u8fd1\u201d\u6700\u4f18\u503c\u7684\u89e3<\/span><\/section>\n<\/li>\n
    • \n
      \u89e3\u51b3\u73b0\u5b9e\u4e16\u754c\u4e2d\u51fa\u73b0\u7684\u5b9e\u4f8b\uff0c\u8fd9\u4e9b\u5b9e\u4f8b\u4e0d\u4e00\u5b9a\u8868\u73b0\u51faNP\u5b8c\u5168\u95ee\u9898\u56fa\u6709\u7684\u6700\u574f\u60c5\u51b5\uff08\u4f8b\u5982\uff0c\u5177\u6709\u6210\u5343\u4e0a\u4e07\u4e2a\u8282\u70b9\u7684TSP\u5b9e\u4f8b)<\/span><\/section>\n<\/li>\n<\/ul>\n

      \u7ec4\u5408\u4f18\u5316\u95ee\u9898\u53ef\u4ee5\u770b\u4f5c\u662f\u5728\u4e00\u4e9b\u79bb\u6563\u9879\u76ee\u4e2d\u641c\u7d22\u6700\u4f73\u5143\u7d20\uff0c\u56e0\u6b64\uff0c\u539f\u5219\u4e0a\uff0c\u4efb\u4f55\u4e00\u79cd\u641c\u7d22\u7b97\u6cd5\u6216\u5143\u542f\u53d1\u5f0f\u7b97\u6cd5\u90fd\u53ef\u4ee5\u7528\u6765\u89e3\u51b3\u5b83\u4eec\u3002\u4e5f\u8bb8\u6700\u666e\u904d\u9002\u7528\u7684\u65b9\u6cd5\u662f\u5206\u652f\u5b9a\u754c\u6cd5 Branch-and-bound (\u4e00\u79cd\u53ef\u4ee5\u5728\u4efb\u4f55\u65f6\u95f4\u70b9\u505c\u6b62\u6765\u7528\u4f5c\u542f\u53d1\u5f0f\u7684\u7cbe\u786e\u7b97\u6cd5)\u3001\u5206\u652f\u5207\u5272\u6cd5 Branch-and-cut (\u4f7f\u7528\u7ebf\u6027\u6700\u4f18\u5316\u751f\u6210\u8fb9\u754c)\u3001\u52a8\u6001\u89c4\u5212\u6cd5 Dynamic Programming (\u4e00\u79cd\u6709\u9650\u641c\u7d22\u7a97\u53e3\u7684\u9012\u5f52\u89e3\u6784\u6cd5)\u548c\u7981\u5fcc\u641c\u7d22\u6cd5 Tabu Search (\u4e00\u79cd\u8d2a\u5a6a\u4ea4\u6362\u7b97\u6cd5)\u3002\u7136\u800c\uff0c\u9057\u4f20\u641c\u7d22\u7b97\u6cd5 Generic Search Algorithms \u4e0d\u80fd\u4fdd\u8bc1\u9996\u5148\u627e\u5230\u6700\u4f18\u89e3\uff0c\u4e5f\u4e0d\u80fd\u4fdd\u8bc1\u5feb\u901f\u8fd0\u884c(\u5728\u591a\u9879\u5f0f\u65f6\u95f4\u5185)\u3002\u7531\u4e8e\u4e00\u4e9b\u79bb\u6563\u4f18\u5316\u95ee\u9898\u662fNP\u5b8c\u5168\u7684\uff0c\u4f8b\u5982\u65c5\u884c\u5546\u95ee\u9898\uff0c\u9664\u975eP=NP\uff0c\u5426\u5219\u8fd9\u662f\u53ef\u4ee5\u9884\u671f\u7684\u3002<\/span><\/section>\n

      <\/section>\n
      \n
      \n
      \n
      \n
      \n
      \n
      \n
      \n
      \n
      \n
      \n
      \n
      \n


      <\/p>\n

      \n
      \n
      \n
      \n
      \n
      \n
      \n
      \n
      \n
      \n
      \n
      \n
      \n

      <\/section>\n

      <\/section>\n
      \n
      <\/svg><\/section>\n<\/section>\n<\/section>\n
      \n

      \u5f62\u5f0f\u5316\u5b9a\u4e49<\/span><\/strong><\/strong><\/span><\/strong><\/strong><\/p>\n<\/section>\n

      \n

      <\/section>\n
      <\/strong><\/section>\n<\/section>\n<\/section>\n<\/section>\n<\/section>\n<\/section>\n<\/section>\n<\/section>\n<\/section>\n<\/section>\n<\/section>\n<\/section>\n<\/section>\n<\/section>\n<\/section>\n<\/section>\n<\/section>\n<\/section>\n<\/section>\n<\/section>\n<\/section>\n<\/section>\n<\/section>\n<\/section>\n<\/section>\n<\/section>\n<\/section>\n


      <\/h2>\n
      \u4ece\u5f62\u5f0f\u4e0a\u6765\u8bf4\uff0c\u4e00\u4e2a\u7ec4\u5408\u4f18\u5316\u95ee\u9898A\u662f\u6d89\u53ca\u56db\u4e2a\u53d8\u91cf\uff08I, f, m, g\uff09\u7684\u95ee\u9898 \uff1a<\/span><\/section>\n
        \n
      • \n
        I \u662f\u5b9e\u4f8b\u4e2d\u7684\u6570\u5b66\u96c6\u5408\uff1b<\/span><\/section>\n<\/li>\n
      • \n
        \u7ed9\u5b9aI\u4e2d\u7684\u4e00\u4e2a\u5b9e\u4f8b\uff0cf(x)\u662f\u53ef\u884c\u89e3\u7684\u6709\u9650\u96c6\u5408\uff1b<\/span><\/section>\n<\/li>\n
      • \n
        \u7ed9\u5b9a\u4e00\u4e2a\u5b9e\u4f8bx\u548c\u5176\u5bf9\u5e94\u7684\u53ef\u884c\u89e3y\uff0cm(x,y)\u8868\u793ay\u7684\u6d4b\u5ea6\uff0c\u5176\u4e2d\uff0cy\u901a\u5e38\u662f\u6b63\u5b9e\u6570\u3002<\/span><\/section>\n<\/li>\n
      • \n
        g\u662f\u76ee\u6807\u51fd\u6570\uff0c\u53ef\u4ee5\u662f\u6700\u5c0f\u503c\u4e5f\u53ef\u4ee5\u662f\u6700\u5927\u503c\u3002<\/span><\/section>\n<\/li>\n<\/ul>\n

        <\/section>\n
        \u7136\u540e\uff0c\u6211\u4eec\u7684\u76ee\u6807\u662f\u627e\u5230\u5b9e\u4f8bx\u4e00\u4e2a\u6700\u4f18\u89e3\uff0c\u4e5f\u5c31\u662f\u53ef\u884c\u89e3y\u3002<\/span><\/section>\n
         <\/span><\/section>\n
        <\/section>\n

        <\/span><\/section>\n
        \u5bf9\u4e8e\u6bcf\u4e00\u4e2a\u7ec4\u5408\u4f18\u5316\u95ee\u9898\uff0c\u90fd\u6709\u4e00\u4e2a\u76f8\u5e94\u7684\u51b3\u7b56\u95ee\u9898\uff0c\u5b83\u67e5\u627e\u662f\u5426\u5b58\u5728\u67d0\u4e00\u7279\u5b9a\u6d4b\u5ea6\u7684\u53ef\u884c\u89e3\u3002\u4f8b\u5982\uff0c\u5982\u679c\u4e00\u4e2a\u56fe\u5f62G\u5305\u542b\u9876\u70b9u\u548cv\uff0c\u90a3\u4e48\u6700\u4f18\u5316\u95ee\u9898\u53ef\u80fd\u662f\u201c\u627e\u5230\u4e00\u6761\u4eceu\u5230v\u4f7f\u7528\u6700\u5c11\u8fb9\u7684\u8def\u5f84\u201d\u3002\u8fd9\u4e2a\u95ee\u9898\u7684\u7b54\u6848\u53ef\u80fd\u662f\uff0c\u6bd4\u65b9\u8bf4\uff0c\u4e00\u4e2a\u76f8\u5e94\u7684\u51b3\u7b56\u95ee\u9898\u662f\u201c\u662f\u5426\u5b58\u5728\u4e00\u6761\u4eceu\u5230<\/span>v\u4f7f\u752810\u6761\u6216\u66f4\u5c11\u8fb9\u7684\u8def\u5f84? \u201d\u8fd9\u4e2a\u95ee\u9898\u53ef\u4ee5\u7528\u7b80\u5355\u7684\u201c\u662f\u201d\u6216\u201c\u5426\u201d\u6765\u56de\u7b54\u3002<\/span><\/section>\n

        \u5728\u8fd1\u4f3c\u7b97\u6cd5approximation algorithms\u9886\u57df\uff0c\u7b97\u6cd5\u88ab\u8bbe\u8ba1\u6765\u5bfb\u627e\u56f0\u96be\u95ee\u9898\u7684\u8fd1\u4f3c\u6700\u4f18\u89e3\u3002\u56e0\u6b64\uff0c\u901a\u5e38\u7684\u51b3\u7b56\u7248\u672c\u5bf9\u95ee\u9898\u7684\u5b9a\u4e49\u4e0d\u591f\u5145\u5206\uff0c\u56e0\u4e3a\u5b83\u53ea\u6307\u5b9a\u4e86\u53ef\u63a5\u53d7\u7684\u89e3\u51b3\u529e\u6cd5\u3002\u5c3d\u7ba1\u6211\u4eec\u53ef\u4ee5\u5f15\u5165\u5408\u9002\u7684\u51b3\u7b56\u95ee\u9898\uff0c\u4f7f\u8fd9\u4e2a\u95ee\u9898\u66f4\u81ea\u7136\u5730\u88ab\u63cf\u8ff0\u4e3a\u4e00\u4e2a\u6700\u4f18\u5316\u95ee\u9898\u3002<\/span><\/span><\/section>\n

        <\/section>\n
        \n
        \n
        \n
        \n
        \n
        \n
        \n
        \n
        \n
        \n
        \n
        \n
        \n


        <\/p>\n

        \n
        \n
        \n
        \n
        \n
        \n
        \n
        \n
        \n
        \n
        \n
        \n
        \n

        <\/section>\n

        <\/section>\n
        \n
        <\/svg><\/section>\n<\/section>\n<\/section>\n
        \n

        NP\u4f18\u5316\u95ee\u9898<\/span><\/strong><\/strong><\/span><\/strong><\/strong><\/p>\n<\/section>\n

        \n

        <\/section>\n
        <\/strong><\/section>\n<\/section>\n<\/section>\n<\/section>\n<\/section>\n<\/section>\n<\/section>\n<\/section>\n<\/section>\n<\/section>\n<\/section>\n<\/section>\n<\/section>\n<\/section>\n<\/section>\n<\/section>\n<\/section>\n<\/section>\n<\/section>\n<\/section>\n<\/section>\n<\/section>\n<\/section>\n<\/section>\n<\/section>\n<\/section>\n<\/section>\n

        <\/span>
        <\/h2>\n
        NP\u4f18\u5316\u95ee\u9898\uff08NPO\uff09\u662f\u4e00\u4e2a\u5177\u6709\u4ee5\u4e0b\u9644\u52a0\u6761\u4ef6\u7684\u7ec4\u5408\u4f18\u5316\u95ee\u9898\u3002<\/span>\u6ce8\u610f\uff0c\u4e0b\u9762\u63d0\u5230\u7684\u591a\u9879\u5f0f\u662f\u76f8\u5e94\u51fd\u6570\u8f93\u5165\u5927\u5c0f\u7684\u51fd\u6570\uff0c\u800c\u4e0d\u662f\u67d0\u4e9b\u9690\u5f0f\u8f93\u5165\u5b9e\u4f8b\u96c6\u5927\u5c0f\u7684\u51fd\u6570\u3002<\/span><\/section>\n
          \n
        • \n
          \u6bcf\u4e2a\u53ef\u884c\u89e3y\u2208f(x)\u7684\u5927\u5c0f\u90fd\u662f\u7531\u7ed9\u5b9a\u5b9e\u4f8bx\u7684\u5927\u5c0f\u591a\u9879\u5f0f\u7ea6\u675f\u7684\uff0c<\/span><\/section>\n<\/li>\n
        • \n
          \u8bed\u8a00{x | x\u2208I}and{(x,y) | y\u2208f(x)}\u5728\u591a\u9879\u5f0f\u65f6\u95f4\u5185\u53ef\u4ee5\u53ef\u5224\u5b9a\u8bed\u8a00\/\u8bc6\u522b\uff0c\u5e76\u4e14\uff0c<\/span><\/section>\n<\/li>\n
        • \n
          m\u662f\u53ef\u8ba1\u7b97\u7684\u591a\u9879\u5f0f\u65f6\u95f4\u3002<\/span><\/section>\n<\/li>\n<\/ul>\n

          \u8fd9\u610f\u5473\u7740\u76f8\u5e94\u7684\u51b3\u7b56\u95ee\u9898\u5728NP\u4e2d\u3002\u5728\u8ba1\u7b97\u673a\u79d1\u5b66\u4e2d\uff0c\u6709\u8da3\u7684\u4f18\u5316\u95ee\u9898\u901a\u5e38\u5177\u6709\u4e0a\u8ff0\u6027\u8d28\uff0c\u56e0\u6b64\u662fNPO\u95ee\u9898\u3002\u5982\u679c\u5b58\u5728\u4e00\u79cd\u5728\u591a\u9879\u5f0f\u65f6\u95f4\u5185\u627e\u5230\u6700\u4f18\u89e3\u7684\u7b97\u6cd5\uff0c\u5219\u8be5\u95ee\u9898\u53c8\u79f0\u4e3aP-\u4f18\u5316\uff08PO\uff09\u95ee\u9898 P-optimization problem \u3002\u901a\u5e38\uff0c\u5728\u5904\u7406NPO\u7c7b\u95ee\u9898\u65f6\uff0c\u4eba\u4eec\u5bf9\u51b3\u7b56\u7248\u672c\u4e3aNP\u5b8c\u5168\u7684\u4f18\u5316\u95ee\u9898\u611f\u5174\u8da3\u3002\u8bf7\u6ce8\u610f\uff0c\u786c\u5ea6\u5173\u7cfb\u603b\u662f\u4e0e\u67d0\u4e9b\u964d\u4f4e\u6709\u5173\u3002\u7531\u4e8e\u8fd1\u4f3c\u7b97\u6cd5\u548c\u8ba1\u7b97\u4f18\u5316\u95ee\u9898\u4e4b\u95f4\u7684\u8054\u7cfb\uff0c\u5728\u67d0\u4e9b\u65b9\u9762\u4fdd\u6301\u8fd1\u4f3c\u6027\u7684\u7f29\u51cf\u6bd4\u4e00\u822c\u7684\u56fe\u7075\u548c\u5361\u666e\u89c4\u7ea6 Turing and Karp Reductions \u66f4\u4e3a\u53ef\u53d6\u3002\u8fd9\u79cd\u89c4\u7ea6\u7684\u4e00\u4e2a\u4f8b\u5b50\u5c31\u662fL-\u89c4\u7ea6 L-reduction \u3002\u56e0\u6b64\uff0c\u5177\u6709NP\u5b8c\u5168\u51b3\u7b56\u7248\u672c\u7684\u4f18\u5316\u95ee\u9898\u4e0d\u4e00\u5b9a\u79f0\u4e3aNPO\u5b8c\u5168\u95ee\u9898\u3002<\/span><\/span><\/section>\n

          <\/span><\/section>\n
          NPO\u95ee\u9898\u6839\u636e\u5176\u8fd1\u4f3c\u6027\u53ef\u5206\u4e3a\u4ee5\u4e0b\u5b50\u7c7b: <\/span><\/span><\/section>\n
            \n
          • \n
            NPO(I)\uff1a\u7b49\u4ef7\u4e8e\u5b8c\u5168\u591a\u9879\u5f0f\u65f6\u95f4\u8fd1\u4f3c\u65b9\u6848 Fully Polynomial-time approximation scheme | PTAS \u3002\u5305\u542b\u80cc\u5305\u95ee\u9898\u3002<\/span><\/section>\n<\/li>\n
          • \n
            NPO(II)\uff1a\u7b49\u4ef7\u4e8e\u591a\u9879\u5f0f\u65f6\u95f4\u8fd1\u4f3c\u65b9\u6848 Polynomial-time approximation scheme\u3002\u5305\u542b\u5206\u6279\u8c03\u5ea6\u95ee\u9898\u3002<\/span><\/section>\n<\/li>\n
          • \n
            NPO(III)\uff1a\u5177\u6709\u591a\u9879\u5f0f\u65f6\u95f4\u7b97\u6cd5\u7684NPO\u95ee\u9898\u7c7b\uff0c\u5176\u8ba1\u7b97\u7684\u89e3\u7684\u6210\u672c\u6700\u591a\u4e3a\u6700\u4f18\u6210\u672c\u7684\u201cc\u201d\u500d\uff08\u5bf9\u4e8e\u6700\u5c0f\u5316\u95ee\u9898\uff09\uff0c\u6216\u6210\u672c\u81f3\u5c11\u4e3a\u6700\u4f18\u6210\u672c\u76841\/c\u5bf9\u4e8e\u6700\u5927\u5316\u95ee\u9898\uff09\u3002\u5728\u5c24\u62c9\u00b7\u8d6b\u7f57\u59c6\u79d1\u7ef4\u5947 Juraj Hromkovic \u7684\u4e66\u4e2d\uff0c\u9664\u4e86P=NP\u4e4b\u5916\uff0c\u6240\u6709\u7684NPO(II)\u95ee\u9898\u90fd\u88ab\u6392\u9664\u5728\u8fd9\u4e2a\u7c7b\u4e4b\u5916\u3002\u5982\u679c\u6ca1\u6709\u6392\u9664\uff0c\u5219\u7b49\u4e8eAPX\uff08approximable\uff09\u3002\u5305\u542b\u6700\u5927\u53ef\u6ee1\u8db3\u6027\u95ee\u9898 MAX-SAT \u548c\u6807\u51c6\u7684\u65c5\u884c\u5546\u95ee\u9898 | TSP\u3002<\/span><\/section>\n<\/li>\n
          • \n
            NPO(IV)\uff1a\u591a\u9879\u5f0f\u65f6\u95f4\u7b97\u6cd5\u7684\u4e00\u7c7bNPO\u95ee\u9898\uff0c\u4ee5\u6bd4\u7387\u4e3a\u8f93\u5165\u5927\u5c0f\u7684\u5bf9\u6570\u591a\u9879\u5f0f\u6765\u903c\u8fd1\u6700\u4f18\u89e3\u3002\u5728Hromkovic\u7684\u4e66\u4e2d\uff0c\u9664\u975eP=NP\uff0c\u5426\u5219\u6240\u6709\u7684NPO(III)-\u95ee\u9898\u90fd\u4e0d\u5c5e\u4e8e\u6b64\u7c7b\u3002\u5305\u542b\u96c6\u5408\u8986\u76d6\u95ee\u9898\u3002<\/span><\/section>\n<\/li>\n
          • \n
            NPO(V)\uff1a\u591a\u9879\u5f0f\u65f6\u95f4\u7b97\u6cd5\u7684\u4e00\u7c7bNPO\u95ee\u9898\uff0c\u4ee5\u67d0\u4e2a\u51fd\u6570\u9650\u5b9a\u7684\u6bd4\u7387\u6765\u903c\u8fd1\u6700\u4f18\u89e3\u3002\u5728Hromkovic\u7684\u4e66\u4e2d\uff0c\u9664\u975eP=NP\uff0c\u5426\u5219\u6240\u6709NPO(IV)-\u95ee\u9898\u90fd\u4e0d\u5c5e\u4e8e\u8fd9\u7c7b\u95ee\u9898\u3002\u5305\u542b\u65c5\u884c\u5546\u95ee\u9898\u548c\u56e2\u95ee\u9898|\u6700\u5927\u56e2\u95ee\u9898 Clique problem|Max Clique problems\u3002<\/span><\/section>\n<\/li>\n<\/ul>\n

            <\/section>\n
            \u5982\u679c\u5bf9\u4e8e\u6bcf\u4e2a\u5b9e\u4f8bx\u548cf(x)\u4e2d\u7684\u6bcf\u4e2a\u89e3y\u4e2d\u7684\u6bcf\u4e2a\u89e3m(x,y)\uff0cM(x,y)\u88ab\u4e00\u4e2a\u5927\u5c0f\u4e3ax\u7684\u591a\u9879\u5f0f\u51fd\u6570\u6240\u9650\u5236\uff0c\u5219\u8be5NPO\u95ee\u9898\u79f0\u4e3a\u591a\u9879\u5f0f\u6709\u754c\uff08PB\uff09\u3002NPOPB \u7c7b\u662f\u4e00\u7c7b\u591a\u9879\u5f0f\u6709\u754c\u7684 NPO \u95ee\u9898\u3002<\/span><\/section>\n

            <\/section>\n
            \n
            \n
            \n
            \n
            \n
            \n
            \n
            \n
            \n
            \n
            \n
            \n
            \n


            <\/p>\n

            \n
            \n
            \n
            \n
            \n
            \n
            \n
            \n
            \n
            \n
            \n
            \n
            \n

            <\/section>\n

            <\/section>\n
            \n
            <\/svg><\/section>\n<\/section>\n<\/section>\n
            \n

            \u7279\u5b9a\u95ee\u9898<\/span><\/strong><\/strong><\/span><\/strong><\/strong><\/p>\n<\/section>\n

            \n

            <\/section>\n
            <\/strong><\/section>\n<\/section>\n<\/section>\n<\/section>\n<\/section>\n<\/section>\n<\/section>\n<\/section>\n<\/section>\n<\/section>\n<\/section>\n<\/section>\n<\/section>\n<\/section>\n<\/section>\n<\/section>\n<\/section>\n<\/section>\n<\/section>\n<\/section>\n<\/section>\n<\/section>\n<\/section>\n<\/section>\n<\/section>\n<\/section>\n<\/section>\n

            <\/span>
            <\/h2>\n
            <\/section>\n

            <\/section>\n
            \u5fb7\u56fd15\u4e2a\u6700\u5927\u57ce\u5e02\u7684\u6700\u4f73\u65c5\u884c\u63a8\u9500\u5458\u4e4b\u65c5\u3002\u6700\u4f18\u7684\u65c5\u884c\u5546\u9014\u7ecf\u5fb7\u56fd15\u4e2a\u6700\u5927\u7684\u57ce\u5e02\u3002\u572843,589,145,600\u4e2a\u53ef\u80fd\u7684\u6e38\u89c8\u6bcf\u4e2a\u57ce\u5e02\u7684\u65c5\u884c\u56e2\u4e2d\uff0c\u8fd9\u662f\u6700\u77ed\u7684\u4e00\u4e2a\u3002<\/span><\/section>\n

            <\/span><\/section>\n