{"id":1427,"date":"2026-06-19T16:57:47","date_gmt":"2026-06-19T08:57:47","guid":{"rendered":"https:\/\/www.smzytyzg.tw.cn\/?p=1427"},"modified":"2026-06-19T16:57:54","modified_gmt":"2026-06-19T08:57:54","slug":"ei6303-%e7%ae%97%e6%b3%95%e8%ae%be%e8%ae%a1%e4%b8%8e%e5%88%86%e6%9e%90","status":"publish","type":"post","link":"https:\/\/www.smzytyzg.tw.cn\/?p=1427","title":{"rendered":"EI6303-\u7b97\u6cd5\u8bbe\u8ba1\u4e0e\u5206\u6790"},"content":{"rendered":"\n

\u56fe\u7b97\u6cd5<\/h2>\n\n\n\n

\u56fe\u7684\u5206\u89e3<\/h3>\n\n\n\n

\u65e0\u5411\u56fe<\/h4>\n\n\n\n

DFS<\/strong><\/p>\n\n\n\n

DFS(G)\nfor all v \u2208 V do\n| visited(v) = false;\nend\nfor all v \u2208 V do\n| if not visited(v) then Explore(G, v);\nend\n\nEXPLORE(G, v)\ninput : G = (V,E) is a graph; v \u2208 V\noutput: visited(u) to true for all nodes u reachable from v visited(v) = true<\/em>\nPREVISIT(v);\nfor each edge (v,u) \u2208 E do\n| if not visited(u) then EXPLORE(G, u);\nend\nPOSTVISIT(v);<\/code><\/pre>\n\n\n\n
\u56fe\u7684\u8fde\u901a\u6027<\/strong><\/p>\n\n\n\n
\u6811\u8fb9(tree edge)<\/strong>\uff1aDFS\u65f6\u7ecf\u8fc7\u7684\u8fb9
\u56de\u8fb9(back edge)<\/strong>\uff1a\u6811\u8fb9\u4ee5\u5916\u7684\u8fb9<\/p>\n\n\n\n
\"\"<\/div><\/figure>\n\n\n\n
\u8fde\u901a\u56fe<\/strong>\uff1a\u4efb\u610f\u9876\u70b9\u95f4\u4e24\u4e24\u6709\u8def\u5f84\u7684\u56fe
\u8fde\u901a\u90e8\u4ef6 \/\u8fde\u901a\u5206\u91cf(connected component)<\/strong>\uff1a\u539f\u56fe\u7684\u5b50\u56fe\uff0c\u4e14\u5185\u90e8\u9876\u70b9\u4e24\u4e24\u95f4\u6709\u8def\u5f84\u3002\u4e0a\u56fe\u4e2d{A,…,J}\u3001{K,L}\u90fd\u662f\u3002<\/p>\n\n\n\n
\u4ece\u67d0\u4e2a\u9876\u70b9\u5f00\u59cb\u7684DFS\u4f1a\u627e\u51fa\u9876\u70b9\u5bf9\u5e94\u7684\u8fde\u901a\u90e8\u4ef6\uff1b\u6bcf\u8c03\u7528\u4e00\u6b21Explore\u90fd\u4f1a\u4ea7\u751f\u4e00\u4e2a\u65b0\u7684\u8fde\u901a\u90e8\u4ef6\u3002<\/p>\n\n\n\n
\u524d\u5e8f\u53ca\u540e\u5e8f<\/strong><\/p>\n\n\n\n
\u7528pre[v]\u3001post[v]\u8868\u793a\u9876\u70b9v\u7b2c\u4e00\u6b21\u548c\u6700\u540e\u4e00\u6b21\u88ab\u8bbf\u95ee\u7684\u65f6\u95f4\uff0cDFS\u7ed3\u675f\u540e\uff0c\u4f1a\u53d1\u73b0\uff1a<\/p>\n\n\n\n
[pre[u], post[u]]\u3001[pre[v],post[v]]\u6216\u4e0d\u76f8\u4ea4\uff0c\u6216\u4e00\u4e2a\u5305\u542b\u53e6\u4e00\u4e2a<\/strong>
\u8bc1\u660e\uff1a<\/p>\n\n\n\n
    \n
  • \u8bbf\u95eeu\u65f6\uff0cuv\u4e4b\u95f4\u5b58\u5728\u4e00\u6761\u672a\u88ab\u8bbf\u95ee\u7684\u8def\u5f84\uff08\u8def\u5f84\u4e0a\u7684\u8282\u70b9\u90fd\u672a\u88ab\u8bbf\u95ee<\/strong>\uff09\uff0c\u5219[pre[u], post[u]]\u3001[pre[v],post[v]]\u4e00\u4e2a\u5305\u542b\u53e6\u4e00\u4e2a<\/strong><\/li>\n\n\n\n
  • \u8bbf\u95eeu\u65f6\uff0cuv\u4e4b\u95f4\u4e0d\u5b58\u5728\u8def\u5f84\uff08\u4e0d\u8fde\u901a\uff08\u5982BC\uff09\u6216\u8def\u5f84\u4e0a\u6709\u70b9\u88ab\u8bbf\u95ee\uff08\u5982BE\uff09<\/strong>\uff09\uff0c\u5219[pre[u], post[u]]\u3001[pre[v],post[v]]\u4e0d\u76f8\u4ea4<\/strong><\/li>\n<\/ul>\n\n\n\n
    \"\"<\/div><\/figure>\n\n\n\n
    \u6709\u5411\u56fe<\/h4>\n\n\n\n
    DFS<\/strong><\/p>\n\n\n\n
    DFS\u4f1a\u751f\u6210\u641c\u7d22\u6811\/\u68ee\u6797\uff0c\u4ea7\u751f\u6811\u6839\u3001\u7956\u5148\u540e\u4ee3\u3001\u7236\u5b50\u7b49\u6982\u5ff5<\/p>\n\n\n\n
    \u6811\u8fb9<\/strong>\uff1aDFS\u7ecf\u8fc7\u7684\u8fb9
    \u524d\u5411\u8fb9(forward edge)<\/strong>\uff1a\u6307\u5411\u975e\u5b50\u8282\u70b9\u7684\u540e\u4ee3
    \u56de\u8fb9<\/strong>\uff1a\u6307\u5411\u7956\u5148
    \u6a2a\u8de8\u8fb9(cross edge)<\/strong>\uff1a\u53bb\u9664\u6389\u524d\u5411\u8fb9\u548c\u56de\u8fb9\u540e\uff0c\u4ece\u4e00\u4e2a\u9876\u70b9\u6307\u5411\u53e6\u4e00\u4e2a\u88ab\u5b8c\u5168\u8bbf\u95ee\u8fc7\u7684\u8fb9<\/p>\n\n\n\n
    \"\"<\/div><\/figure>\n\n\n\n
    \u7c7b\u6bd4pre[v],post[v]\uff0c\u53ef\u4ee5\u7528\u4ee5\u4e0b\u65b9\u6cd5\u533a\u5206\u56db\u79cd\u8fb9<\/p>\n\n\n\n
    \"\"<\/div><\/figure>\n\n\n\n
    \u4e3a\u4ec0\u4e48\u4e0d\u5b58\u5728uuvv\u8fd9\u79cd\u60c5\u51b5\uff1f<\/p>\n\n\n\n
    \u8bc1\u660e\uff1a\u5b58\u5728u\u2192v\u8fd9\u6761\u8fb9\uff0c\u82e5\u5148\u8bbf\u95eeu\uff0c\u5206\u7c7b\u8ba8\u8bbau\u5230v\u662f\u5426\u8fd8\u6709\u5176\u4ed6\u8def\u5f84\uff0c\u7ed3\u679c\u5747\u4e3auvvu\uff1b\u5148\u8bbf\u95eev\uff0c\u82e5\u6709\u5176\u4ed6\u8def\u5f84\uff0c\u7ed3\u679c\u4e3avuuv\uff0c\u65e0\u5176\u4ed6\u8def\u5f84\u5219\u4e3avvuu<\/p>\n\n\n\n
    \u6709\u5411\u65e0\u73af\u56feDAG<\/strong><\/p>\n\n\n\n
    Lemma: \u6709\u5411\u56fe\u6709\u73af\uff0c\u5f53\u4e14\u4ec5\u5f53DFS\u6709\u56de\u8fb9
    \u8bc1\u660e\uff1a<\/p>\n\n\n\n
      \n
    • \u82e5\u6709\u73af\u5219\u6709\u56de\u8fb9\uff1a\u5047\u8bbe\u5728\u73af\u4e0a\u5148\u8bbf\u95ee\u9876\u70b9vk<\/sub>\uff0c\u5219vk-1<\/sub>\u2192vk<\/sub>\u662f\u4e00\u6761\u56de\u8fb9<\/li>\n\n\n\n
    • \u82e5\u6709\u56de\u8fb9\u5219\u6709\u73af\uff1a\u5047\u8bbe\u56de\u8fb9\u4e3au\u2192v\uff0c\u51fa\u73b0\u56de\u8fb9\u610f\u5473\u7740\u5b58\u5728\u53e6\u4e00\u6761\u8def\u5f84\u4ecev\u5230u\uff0c\u5219\u6210\u73af<\/li>\n<\/ul>\n\n\n\n
      \u7ebf\u6027\/\u62d3\u6251\u6392\u5e8f\uff1a\u4efb\u610f\u8c03\u7528\u4e00\u6b21EXPLORE\u7b97\u6cd5\uff0c\u628a\u6240\u6709\u9876\u70b9\u6309post number<\/strong>\u4ece\u5927\u5230\u5c0f\u6392\u5e8f\uff08\u540e\u8bbf\u95ee\u9760\u524d\uff09<\/p>\n\n\n\n
      \u5728DAG\u4e2d\u6240\u6709\u8fb9\u90fd\u662f\u6392\u540d\u9760\u524d\u7684\u8282\u70b9\u6307\u5411\u6392\u540d\u9760\u540e\u7684\u8282\u70b9<\/strong><\/p>\n\n\n\n
      \u8bc1\u660e\uff1aDAG\u6ca1\u6709\u56de\u8fb9\uff0c\u800c\u5176\u4ed6\u4e09\u79cd\u8fb9\u90fd\u6ee1\u8db3\u8fd9\u4e2a\u6027\u8d28<\/p>\n\n\n\n
      \u6240\u6709\u6709\u5411\u65e0\u73af\u56fe\u5747\u6709\u62d3\u6251\u6392\u5e8f<\/p>\n\n\n\n
      DAG\u21d4DFS\u65e0\u56de\u8fb9\u21d4\u6709\u62d3\u6251\u6392\u5e8f<\/strong><\/p>\n\n\n\n
      \n
      Lemma: DAG\u4e2d\uff0ce(u,v)\uff0cpost[v]<post[u]<\/p>\n<\/blockquote>\n\n\n\n
      \u6e90\u70b9(source)<\/strong>\uff1a\u6ca1\u6709\u5165\u8fb9\u7684\u70b9
      \u6c47\u70b9(sink)<\/strong>\uff1a\u6ca1\u6709\u51fa\u8fb9\u7684\u70b9<\/p>\n\n\n\n
      Lemma: \u6bcf\u4e2aDAG\u90fd\u6709\u81f3\u5c11\u4e00\u4e2a\u6e90\u70b9\uff0c\u81f3\u5c11\u4e00\u4e2a\u6c47\u70b9 <\/p>\n\n\n\n
      \u62d3\u6251\u6392\u5e8f\u7684\u53e6\u4e00\u79cd\u7b97\u6cd5\uff1a\u627e\u5230\u6e90\u70b9\uff0c\u8f93\u51fa\uff0c\u7136\u540e\u4ece\u56fe\u4e2d\u5220\u53bb\uff0c\u518d\u7ee7\u7eed\u627e\u6e90\u70b9<\/p>\n\n\n\n
      \u5f3a\u8fde\u901a\u90e8\u4ef6\/\u5206\u91cf<\/strong><\/p>\n\n\n\n
      \u8fde\u901a<\/strong>\uff1auv\u4e4b\u95f4\u5b58\u5728u\u2192v\u7684\u8def\u5f84\uff0c\u4e5f\u5b58\u5728v\u2192u\u7684\u8def\u5f84\uff0c\u5219uv\u8fde\u901a
      \u5f3a\u8fde\u901a\u5206\u91cf(SCC)<\/strong>\uff1a\u539f\u56fe\u7684\u5b50\u56fe\uff0c\u4e14\u5185\u90e8\u9876\u70b9\u4e24\u4e24\u95f4\u8fde\u901a\u3002\uff08\u9700\u8981\u6700\u5927\u5316\uff0c\u80fd\u5408\u5e76\u7684\u5fc5\u987b\u5408\u5e76\uff09
      \u6e90\u70b9\u5f3a\u8fde\u901a\u5206\u91cf(source SCC)<\/strong>\uff1a\u5728\u201c\u8d85\u56fe\u201d(\u5373b\u56fe)\u4e2d\uff0c\u6e90\u70b9\u5bf9\u5e94\u7684\u5f3a\u8fde\u901a\u5206\u91cf({A})
      \u6c47\u70b9\u5f3a\u8fde\u901a\u5206\u91cf(sink SCC)<\/strong>\uff1a\u5728\u201c\u8d85\u56fe\u201d(\u5373b\u56fe)\u4e2d\uff0c\u6c47\u70b9\u5bf9\u5e94\u7684\u5f3a\u8fde\u901a\u5206\u91cf({D}\u548c{G,H,I,J,K,L})<\/p>\n\n\n\n
      \u53ef\u4ee5\u5c06\u56fe\u5206\u4e3a\u591a\u4e2a\u4e92\u4e0d\u76f8\u4ea4\u7684SCC<\/p>\n\n\n\n
      \"\"<\/div><\/figure>\n\n\n\n
      \n
      Lemma: \u6bcf\u4e2a\u6709\u5411\u56fe\u5173\u4e8e\u5176SCC\u662f\u4e00\u4e2aDAG\uff0c\u4e0a\u56fe\u4e2d\u5de6\u4fa7\u6709\u73af\uff0c\u53f3\u4fa7\u65e0\u73af<\/p>\n<\/blockquote>\n\n\n\n
      \n
      <\/p>\n<\/blockquote>\n\n\n\n
      \u6c42\u51fa\u5f3a\u8fde\u901a\u90e8\u4ef6<\/strong><\/p>\n\n\n\n
      \n
      Lemma1: DFS\u65f6\uff0c\u4e00\u6b21Explore\u4eceu\u70b9\u5f00\u59cb\uff0c\u90a3\u4e48\u8be5\u8fdb\u7a0b\u6070\u597d\u4f1a\u5728 \u6240\u6709u\u53ef\u8fbe\u7684\u9876\u70b9v\u88ab\u8bbf\u95ee\u540e \u505c\u6b62<\/p>\n<\/blockquote>\n\n\n\n
      \u6240\u4ee5\uff0c\u5982\u679c\u9876\u70b9u\u5728\u4e00\u4e2a\u6c47\u70b9\u5f3a\u8fde\u901a\u5206\u91cf\u4e2d\uff0c\u6211\u4eec\u6070\u597d\u80fd\u5f97\u5230\u8fd9\u4e2a\u5f3a\u8fde\u901a\u5206\u91cf\u3002<\/p>\n\n\n\n
      \u95ee\u9898\uff1a<\/p>\n\n\n\n
        \n
      • \u5982\u4f55\u627e\u5230\u5904\u4e8e\u6c47\u70b9\u5f3a\u8fde\u901a\u5206\u91cf\u4e2d\u7684\u9876\u70b9u<\/li>\n\n\n\n
      • \u627e\u5230\u4e00\u4e2a\u5f3a\u8fde\u901a\u5206\u91cf\u4e4b\u540e\u600e\u4e48\u529e<\/li>\n<\/ul>\n\n\n\n
        \u89e3\u51b3\u7b2c\u4e00\u4e2a\u95ee\u9898\uff1a<\/strong><\/p>\n\n\n\n
        \n
        Lemma2: C\uff0cC’\u662f\u4e24\u4e2aSCC\uff0c\u5b58\u5728\u4e00\u6761\u8fb9C\u2192C’\uff0c\u5219C\u4e2d\u6700\u5927\u7684post[u]\u5927\u4e8eC’\u4e2d\u6700\u5927\u7684post[u]<\/p>\n\n\n\n
        Proof\uff1a\u62d3\u6251\u6392\u5e8f<\/p>\n\n\n\n
        \u6839\u636eLemma2\u53ef\u4ee5\u5f97\u5230\u4e0b\u9762\u7684Lemma3<\/p>\n\n\n\n
        Lemma3: post[u]\u6700\u5927\u7684u\u5fc5\u5b9a\u843d\u5728\u4e00\u4e2a\u6e90\u70b9\u5f3a\u8fde\u901a\u5206\u91cf\u4e2d<\/p>\n<\/blockquote>\n\n\n\n
        \u8003\u8651\u539f\u56fe\u7684\u53cd\u8f6c\u56fe(reverse graph)\uff0c\u5373G\u4e2de(u,v)\u2192G’\u4e2de(v,u)\uff0cG’\u4e2d\u7684\u6e90\u70b9\u5f3a\u8fde\u901a\u5206\u91cf\u6070\u597d\u662fG\u4e2d\u6c47\u70b9\u5f3a\u8fde\u901a\u5206\u91cf\uff0c\u56e0\u6b64\u5728G’\u4e2d\u505aDFS\u53ef\u4ee5\u89e3\u51b3\u7b2c\u4e00\u4e2a\u95ee\u9898\u3002<\/p>\n\n\n\n
        \u89e3\u51b3\u7b2c\u4e8c\u4e2a\u95ee\u9898\uff1a<\/strong><\/p>\n\n\n\n
        \u6839\u636eLemma3\uff0c\u5220\u9664\u7b2c\u4e00\u4e2aSCC\u540e\uff0c\u5269\u4f59\u7684post[v]\u6700\u5927\u7684\u9876\u70b9\u6070\u597d\u843d\u5728G\u4e2d\u4e0b\u4e00\u4e2a\u6c47\u70b9\u5f3a\u8fde\u901a\u5206\u91cf\u4e2d\uff0c\u56e0\u6b64\u53ef\u4ee5\u4e00\u76f4\u5e94\u7528\u8fd9\u6761\u6027\u8d28\u76f4\u5230\u7ed3\u675f\u3002<\/p>\n\n\n\n
        \u7ebf\u6027\u65f6\u95f4\u7684\u7b97\u6cd5\uff1a<\/strong><\/p>\n\n\n\n
          \n
        • \u5728G’\u4e0a\u505aDFS<\/li>\n\n\n\n
        • \u6309\u4e0a\u4e00\u6b65\u4e2dpost[v]\u964d\u5e8f\u7684\u987a\u5e8f\uff0c\u5728G\u4e0a\u8fd0\u884cDFS(\u8bbf\u95ee\u8fc7\u7684\u4e0d\u518dExplore)<\/li>\n<\/ul>\n\n\n\n
          \u76f8\u5173\u95ee\u9898\uff1a<\/h4>\n\n\n\n
          \u56e2\u95ee\u9898<\/strong><\/p>\n\n\n\n
          \u628a\u56fe\u5206\u6210n\u4e2a\u4e24\u4e24\u4e4b\u95f4\u6709\u8fb9\u7684\u90e8\u5206\uff08\u65e0\u591a\u9879\u5f0f\u65f6\u95f4\u7b97\u6cd5\uff09<\/p>\n\n\n\n
          \u5173\u952e\u8def\u5f84<\/strong><\/p>\n\n\n\n
          ps\uff1a\u5047\u8bbe\u6240\u6709\u8def\u5f84\u957f\u5ea6\u90fd\u4e3a1<\/p>\n\n\n\n
            \n
          • \u8fdb\u884c\u904d\u5386\uff0c\u6807\u8bb0\u6bcf\u4e2a\u9876\u70b9\u7684\u5165\u5ea6<\/li>\n\n\n\n
          • \u5b8c\u6210\u5165\u5ea6\u4e3a0\u7684\u4efb\u52a1<\/li>\n\n\n\n
          • \u66f4\u65b0\u4e00\u904d\u5165\u5ea6\uff0c\u91cd\u590d\u6b65\u9aa42-3\u76f4\u5230\u7ed3\u675f<\/li>\n<\/ul>\n\n\n\n
            \u7ed9\u5b9a\u6709\u5411\u56fe\uff0c\u627e\u5230\u4e00\u9876\u70b9\u53ef\u4ee5\u5230\u8fbe\u6240\u6709\u5176\u4ed6\u9876\u70b9<\/strong><\/p>\n\n\n\n
            \u6cd51\uff1a<\/p>\n\n\n\n
              \n
            • \u7ed8\u5236\u201c\u8d85\u56fe\u201d<\/li>\n\n\n\n
            • \u5982\u679c\u6709\u591a\u4e2a\u6e90\u70b9\u5f3a\u8fde\u901a\u5206\u91cf\uff0c\u5219\u4e0d\u5b58\u5728\uff1b\u5982\u679c\u53ea\u6709\u4e00\u4e2a\u6e90\u70b9\u5f3a\u8fde\u901a\u5206\u91cf\uff0c\u5219\u8fd9\u4e2aSCC\u4e2d\u7684\u4efb\u610f\u4e00\u4e2a\u70b9\u90fd\u6ee1\u8db3<\/li>\n<\/ul>\n\n\n\n
              \u6cd52\uff1a<\/p>\n\n\n\n
                \n
              • \u8c03\u7528DFS\uff0c\u627e\u5230post[u]\u6700\u5927\u7684\u9876\u70b9u<\/li>\n\n\n\n
              • \u4eceu\u5f00\u59cbDFS\uff0c\u5982\u679c\u8bbf\u95ee\u4e86\u6240\u6709\u9876\u70b9\uff0c\u5219\u6ee1\u8db3\u6761\u4ef6<\/li>\n<\/ul>\n\n\n\n
                \u6700\u5c0f\u751f\u6210\u6811<\/h3>\n\n\n\n
                \u95ee\u9898\u63cf\u8ff0\uff1a\u7ed9\u5b9aG(V,E)\uff0c\u5728\u5176\u5b50\u56feH(V,T)\u4e2d\uff0c\u4f7fH\u4e0d\u7834\u574f\u56fe\u7684\u8fde\u901a\u6027\u4e14T\u7684\u6743\u91cd\u548c\u6700\u5c0f\u3002<\/p>\n\n\n\n
                \u8def\u5f84\uff1a\u8fde\u63a5\u4e86\u4e00\u4e2a\u9876\u70b9\u5e8f\u5217\u7684\u8fb9\u7684\u5e8f\u5217
                \u73af\uff1a\u4e00\u6761\u9996\u5c3e\u76f8\u63a5\uff0c\u6ca1\u6709\u91cd\u590d\u9876\u70b9\u7684\u8def\u5f84
                \u5272\uff1a\u5b9a\u4e49\u5728\u9876\u70b9\u96c6V\u4e0a\u7684\u4e00\u79cd\u5206\u5272\uff0c\u5c06V\u5206\u5272\u4e3aS\u548cV-S\u4e24\u4e2a\u975e\u7a7a\u96c6\u5408
                \u5272\u96c6\uff1a\u6a2a\u8de8V\u548cV-S\u4e24\u4e2a\u9876\u70b9\u96c6\u7684\u8fb9\u7684\u96c6\u5408<\/p>\n\n\n\n
                \u6027\u8d28\uff1a\u4e00\u4e2a\u73af\u548c\u4e00\u4e2a\u5272\u96c6\u7684\u4ea4\u96c6\u5fc5\u5b9a\u6709\u5076\u6570\u6761\u8fb9<\/p>\n\n\n\n
                \"\"<\/div><\/figure>\n\n\n\n
                \u57fa\u672c\u73af\uff1a\u4ee4H(V,T)\u4e3a\u56feG(V,E)\u7684\u4e00\u9897\u751f\u6210\u6811\uff0ce\u2209T\uff0c\u5219T\u222a{e}\u4f1a\u5f62\u6210\u4e00\u4e2a\u73afC\uff0c\u79f0\u4e3a\u4e00\u4e2a\u57fa\u672c\u73af
                \u5bf9\u4efb\u610ff\u2208C\uff0cT\u222a{e}-{f}\u4ecd\u662f\u4e00\u9897\u751f\u6210\u6811<\/p>\n\n\n\n
                \u57fa\u672c\u5272\u96c6\uff1a\u4ee4H(V,T)\u4e3a\u56feG(V,E)\u7684\u4e00\u9897\u751f\u6210\u6811\uff0cf\u2208T\uff0cT-{f}\u5c06G\u5206\u4e3a\u4e24\u90e8\u5206\uff0c\u4ee4D\u4e3a\u6a2a\u8de8\u4e24\u90e8\u5206\u7684\u8fb9\u7684\u96c6\u5408\uff0c\u79f0\u4e3a\u4e00\u4e2a\u57fa\u672c\u5272\u96c6
                \u5bf9\u4efb\u610fe\u2208D\uff0cT\u222a{e}-{f}\u4ecd\u662f\u4e00\u9897\u751f\u6210\u6811<\/p>\n\n\n\n
                \u7ea2\u84dd\u67d3\u8272\u7b97\u6cd5<\/h4>\n\n\n\n
                  \n
                • \u7ea2\u8272\u89c4\u5219\uff1a\u5728\u6ca1\u6709\u7ea2\u8fb9\u7684\u73afC\u4e0a\u627e\u51fa\u6700\u957f\u7684\u8fb9\u67d3\u7ea2<\/li>\n\n\n\n
                • \u84dd\u8272\u89c4\u5219\uff1a\u5728\u6ca1\u6709\u84dd\u8fb9\u7684\u5272\u96c6D\u4e0a\u627e\u51fa\u6700\u77ed\u7684\u8fb9\u67d3\u84dd<\/li>\n\n\n\n
                • \u4e0d\u65ad\u5e94\u7528\u4e0a\u8ff0\u4e24\u6761\u89c4\u5219\uff08\u987a\u5e8f\u4e0d\u5b9a\uff09\uff0c\u76f4\u5230\u6240\u6709\u8fb9\u90fd\u88ab\u67d3\u8272\uff0c\u5219\u84dd\u8fb9\u4e3aMST\uff08\u53ef\u4ee5\u5728\u67d3\u8272|V|-1\u6761\u84dd\u8fb9\u540e\u7ec8\u6b62\uff09<\/li>\n<\/ul>\n\n\n\n
                  \u8bc1\u660e\u6b63\u786e\u6027<\/strong><\/p>\n\n\n\n
                  \u5047\u8bbe\uff1a\u5b58\u5728\u4e00\u4e2a\u53ef\u80fd\u7684\u6700\u5c0f\u751f\u6210\u6811MST(V,T*)\u5305\u62ec\u5f53\u524d\u6240\u6709\u84dd\u8fb9\uff0c\u4e0d\u5305\u542b\u4efb\u4f55\u7ea2\u8fb9<\/p>\n\n\n\n
                  base\uff1a\u672a\u8fd0\u884c\u65f6\u4e00\u5b9a\u6210\u7acb<\/p>\n\n\n\n
                  \u5f52\u7eb3\uff1a\u8fd0\u884c\u5230\u67d0\u4e00\u6b65\uff08\u5047\u8bbe\u8fd9\u4e00\u6b65\u67d3\u84dd\u8272\uff09\u65f6\uff1a
                  1.\u5982\u679c\u67d3\u8272\u8fb9f\u2208T*\uff0c\u663e\u7136\u6ee1\u8db3\uff1b
                  2.\u5982\u679c\u67d3\u8272\u8fb9f\u2209T*\uff0c\u5219T*\u222a{f}\u4f1a\u5f62\u6210\u4e00\u4e2a\u57fa\u672c\u73af\uff0c\u73af\u548c\u5272\u96c6\u7684\u53e6\u4e00\u4e2a\u516c\u5171\u8fb9\u662fe\uff08\u663e\u7136e\u4e0d\u6bd4f\u77ed\uff09\uff0c\u5219MST(V,T*-{e}+{f})\u662f\u4e00\u68f5\u6ee1\u8db3\u5047\u8bbe\u7684\u6700\u5c0f\u751f\u6210\u6811<\/p>\n\n\n\n
                  \u5f52\u7eb3\uff1a\u8fd0\u884c\u5230\u67d0\u4e00\u6b65\uff08\u5047\u8bbe\u8fd9\u4e00\u6b65\u67d3\u7ea2\u8272\uff09\u65f6\uff1a
                  1.\u5982\u679c\u67d3\u8272\u8fb9f\u2209T*\uff0c\u663e\u7136\u6ee1\u8db3\uff1b
                  2.\u5982\u679c\u67d3\u8272\u8fb9f\u2208T*\uff0c\u5219T*-{f}\u4f1a\u5f62\u6210\u4e00\u4e2a\u57fa\u672c\u5272\uff0c\u73af\u548c\u5272\u96c6\u7684\u53e6\u4e00\u4e2a\u516c\u5171\u8fb9\u662fe\uff08\u663e\u7136e\u4e0d\u6bd4f\u957f\uff09\uff0c\u5219MST(V,T*+{e}-{f})\u662f\u4e00\u68f5\u6ee1\u8db3\u5047\u8bbe\u7684\u6700\u5c0f\u751f\u6210\u6811<\/p>\n\n\n\n
                  \u8bc1\u660e\u7b97\u6cd5\u7ec8\u6b62<\/strong><\/p>\n\n\n\n
                  \u53ea\u9700\u8bc1\u660e\u4e00\u6761\u8fb9\u6216\u88ab\u67d3\u7ea2\uff0c\u6216\u88ab\u67d3\u84dd<\/p>\n\n\n\n
                  \u9009\u53d6\u4e00\u6761\u672a\u88ab\u67d3\u8272\u7684\u8fb9e\uff0c\u7b97\u6cd5\u8fd0\u884c\u65f6\u84dd\u8fb9\u5f62\u6210\u4e00\u4e2a\u68ee\u6797\uff0c\u4f1a\u51fa\u73b0\u4ee5\u4e0b\u60c5\u51b5
                  1.e\u7684\u4e24\u4e2a\u7aef\u70b9\u5728\u4e00\u68f5\u6811\u4e2d\uff0c\u5219e\u4e0e\u8fd9\u68f5\u6811\u5f62\u6210\u4e86\u4e00\u4e2a\u73af\uff0c\u53ef\u4ee5\u5e94\u7528\u7ea2\u8272\u89c4\u5219
                  2.e\u7684\u4e24\u4e2a\u7aef\u70b9\u5728\u4e24\u4e2a\u6811\u4e2d\uff0c\u5219e\u5c5e\u4e8e\u4e00\u4e2a\u5272\u96c6\uff0c\u53ef\u4ee5\u5e94\u7528\u84dd\u8272\u89c4\u5219<\/p>\n\n\n\n
                  Prim\u7b97\u6cd5<\/h4>\n\n\n\n
                  \u5047\u8bbeAB\u4e24\u90e8\u5206\u5206\u522b\u6709\u4e24\u9897\u6700\u5c0f\u751f\u6210\u6811S\uff0cT\uff0c\u9009\u53d6A\u2192B\u6700\u77ed\u8fb9e\uff0cS\u222aT\u222ae\u662f\u6574\u4f53\u7684\u6700\u5c0f\u751f\u6210\u6811<\/p>\n\n\n\n
                    \n
                  • \u9009\u53d6\u4e00\u4e2a\u9876\u70b9\u6dfb\u52a0\u5230T\u4e2d<\/li>\n\n\n\n
                  • \u9009\u53d6\u4e00\u6761T\u5230V-T\u7684\u6700\u77ed\u8fb9e(u,v)\uff0c\u5c06v\u6dfb\u52a0\u5230T\u4e2d\uff08\u5047\u8bbeu\u539f\u672c\u5728T\u4e2d\uff09<\/li>\n\n\n\n
                  • \u91cd\u590d\u4e0a\u4e00\u6b65|V|-1\u6b21<\/li>\n<\/ul>\n\n\n\n
                    algo:<\/strong><\/p>\n\n\n\n
                    PRIM(G, w)
                    input : A connected undirected graph G = (V, E), with edge weights we
                    output: A minimum spanning tree defined by the array prev<\/em>
                    for all u \u2208 V do
                    | cost(u) = \u221e;
                    | prev(u) = nil;
                    end
                    pick any initial node u0<\/sub>;
                    cost(u0<\/sub>) = 0;
                    H =makequeue(V) using cost-values as keys;
                    while H is not empty do
                    | v=deletemin(H);
                    | for each (v, z) \u2208 E do
                    | | if cost(z) > w(v, z) then
                    | | | cost(v) = w(v, z); prev(z) = v;
                    | | | decreasekey (H,z);
                    | | end
                    | end
                    end<\/p>\n\n\n\n
                    \u8bc1\u660e\uff1a\u76f8\u5f53\u4e8e\u53ea\u753b\u84dd\u8272\u8fb9<\/p>\n\n\n\n
                    \u65f6\u95f4\u590d\u6742\u5ea6O(|E|\u00b7log|V|)<\/p>\n\n\n\n
                    Kruskal\u7b97\u6cd5<\/h4>\n\n\n\n
                      \n
                    • \u5c06\u6240\u6709\u8fb9\u6309\u6743\u503c\u5347\u5e8f\u6392\u5217<\/li>\n\n\n\n
                    • \u6309\u987a\u5e8f\u904d\u5386\u6240\u6709\u8fb9\uff0c\u6dfb\u52a0\u5230\u56fe\u4e2d\uff0c\u5982\u679c\u6210\u73af\u820d\u53bb<\/li>\n<\/ul>\n\n\n\n
                      algo:<\/strong><\/p>\n\n\n\n
                      KRUSKAL(G, w)\ninput : A connected undirected graph G = (V, E), with edge weight we<\/sub>\noutput: A minimum spanning tree defined by the edges X<\/em>\nfor all u \u2208 V do\n| makeset (u);\nend\nX = { };\nSort the edges E by weight;\nfor all (u, v) E in increasing order of weight do\n| if find (u)\u2260find (v) then\n| | add (u, v) to X;\n| | union (u,v)\n| end\nend<\/code><\/pre>\n\n\n\n
                      \u4f7f\u7528\u7684\u6570\u636e\u7ed3\u6784\uff1a\u4e0d\u76f8\u4ea4\u96c6\/\u5e76\u67e5\u96c6<\/p>\n\n\n\n
                        \n
                      • makeset(x): create a singleton set containing x;  |V|<\/li>\n\n\n\n
                      • find(x): find the set that x belong to;  2\u00b7|E|<\/li>\n\n\n\n
                      • union(x, y): merge the sets containing x and y; |V| – 1<\/li>\n<\/ul>\n\n\n\n
                        \u8bc1\u660e\uff1a\u662f\u7ea2\u84dd\u67d3\u8272\u7b97\u6cd5\u7684\u7279\u6b8a\u60c5\u51b5
                        \u9009\u4e2d\u4e00\u6761\u8fb9e\uff0c\u82e5e\u7684\u4e24\u4e2a\u7aef\u70b9\u5728\u4e00\u9897\u84dd\u8272\u6811\u4e2d\uff0c\u5219\u5e94\u7528\u7ea2\u8272\u89c4\u5219\u5c06e\u67d3\u7ea2\uff1b\u5426\u5219\u5e94\u7528\u84dd\u8272\u89c4\u5219\u5c06e\u67d3\u84dd<\/p>\n\n\n\n
                        \u65f6\u95f4\u590d\u6742\u5ea6\uff1aO(|E|\u00b7log|E|)\uff08\u6392\u5e8f\u7684\u590d\u6742\u5ea6\uff09\uff0c\u7eaf\u7b97\u6cd5\u590d\u6742\u5ea6\u4e3aO(|E|)<\/p>\n\n\n\n
                        Reverse-Delete\u7b97\u6cd5<\/h4>\n\n\n\n
                        \u5c06E\u4e2d\u8fb9\u6309\u6743\u91cd\u4ece\u5927\u5230\u5c0f\u6392\u5e8f\uff0c\u5982\u679c\u5220\u9664\u8fb9e\u4e0d\u5f71\u54cd\u8fde\u901a\u6027\uff0c\u5219\u5220\u9664\uff0c\u5426\u5219\u4fdd\u7559\uff08\u76f8\u5f53\u4e8e\u6301\u7eed\u5e94\u7528\u7ea2\u8272\u89c4\u5219\uff09<\/p>\n\n\n\n
                        \u65f6\u95f4\u590d\u6742\u5ea6\uff1aO(|E|log|V|(loglog|V|)\u00b3)<\/p>\n\n\n\n
                        Bor\u016fvka\u2019s\u7b97\u6cd5<\/h4>\n\n\n\n
                        \u628a\u56fe\u4e2d\u5f53\u524d\u7684\u8fde\u901a\u5757\u770b\u6210\u201c\u7ec4\u4ef6\u201d\uff08\u521d\u59cb\u65f6\u6bcf\u4e2a\u70b9\u5c31\u662f\u4e00\u4e2a\u7ec4\u4ef6\uff09\u3002\u5728\u6bcf\u4e00\u8f6e\u91cc\uff1a<\/p>\n\n\n\n
                          \n
                        • \u5bf9\u6bcf\u4e2a\u7ec4\u4ef6\uff0c\u627e\u4e00\u6761\u4ece\u8be5\u7ec4\u4ef6\u51fa\u53d1\u3001\u8fde\u63a5\u5230\u5176\u4ed6\u7ec4\u4ef6\u7684\u6700\u4fbf\u5b9c\u7684\u8fb9\u3002<\/li>\n\n\n\n
                        • \u628a\u6240\u6709\u7ec4\u4ef6\u5404\u81ea\u9009\u51fa\u7684\u8fd9\u4e9b\u6700\u4fbf\u5b9c\u8fb9\u4e00\u8d77\u67d3\u6210\u84dd\u8272\u3002<\/li>\n\n\n\n
                        • \u91cd\u590d\u4e0a\u8ff0\u6b65\u9aa4\uff0c\u76f4\u5230\u53ea\u5269\u4e0b 1 \u4e2a\u7ec4\u4ef6\uff08\u6216\u9009\u8fb9\u6570\u8fbe\u5230 (n-1)\uff09\u3002<\/li>\n<\/ul>\n\n\n\n
                          \u65f6\u95f4\u590d\u6742\u5ea6\uff1aO(|E|log|V|)\uff0c\u6bcf\u8f6e\u9009\u8fb9\u662f|E|\uff0c\u7ec4\u4ef6\u6570\u6bcf\u8f6e\u51cf\u534a\uff0c\u6700\u591alog|V|\u8f6e<\/p>\n\n\n\n
                          \u5982\u4f55\u5b9e\u73b0\u7ec4\u4ef6\u7684\u5408\u5e76\u2014\u2014\u538b\u7f29\u8fb9<\/p>\n\n\n\n
                          \u538b\u7f29\u8fb9<\/strong><\/p>\n\n\n\n
                          \u76ee\u6807\uff1a\u5220\u9664\u7ec4\u4ef6\u5185\u90e8\u7684\u8fb9\uff0c\u7ec4\u4ef6\u4e4b\u95f4\u7684\u5e73\u884c\u8fb9\u4fdd\u7559\u6743\u91cd\u6700\u5c0f\u7684<\/p>\n\n\n\n
                          \"\"<\/div><\/figure>\n\n\n\n
                            \n
                          • \u6807\u8bb0\u9700\u8981\u88ab\u538b\u7f29\u7684\u8fb9O(|V|+|E|)<\/li>\n\n\n\n
                          • \u8bc6\u522b\u538b\u7f29\u540e\u751f\u6210\u7684\u65b0\u7ec4\u4ef6O(|V|+|E|)<\/li>\n\n\n\n
                          • \u5c06\u6bcf\u4e2a\u7ec4\u4ef6\u66ff\u6362\u4e3a\u4e00\u4e2a\u9876\u70b9O(|V|+|E|)<\/li>\n\n\n\n
                          • \u5220\u9664\u81ea\u5faa\u73af\u8fb9\u548c\u5e73\u884c\u8fb9O(|E|)<\/li>\n<\/ul>\n\n\n\n
                            \u65f6\u95f4\u590d\u6742\u5ea6\uff1aO(|V|+|E|)<\/p>\n\n\n\n
                            \u52a8\u6001\u89c4\u5212<\/h2>\n\n\n\n
                            \u6709\u5411\u65e0\u73af\u56feDAG\u7684\u6700\u77ed\u8def\u5f84<\/strong><\/p>\n\n\n\n
                            \u6ce8\u610f\u5230\uff1a\u5728DAG\u7684\u4efb\u610f\u8def\u5f84\u4e2d\uff0c\u9876\u70b9\u6309\u62d3\u6251\u5e8f\u51fa\u73b0<\/strong><\/p>\n\n\n\n
                            DAG-SHORTEST-PATHS(G, l, s)\ninput : Graph G = (V, E), edge length le<\/sub> e \u2208 E ; Vertex s \u2208 V\noutput: For all vertices u reachable from s, dist(u) is the set to the distance from s to u<\/em>\nfor all u \u2208 V do\n| dist(u) = \u221e;\nend\ndist[s] = 0;\nlinearize G;\nfor each v \u2208 V\\{s} , in linearized order do\n| dist(v) = min(u,v)\u2208E<\/sub> {dist(u) + l(u,v)};\nend<\/code><\/pre>\n\n\n\n
                            \u5141\u8bb8\u8d1f\u8fb9\u5b58\u5728
                            \u6c42\u6700\u957f\u8def\u5f84\uff1a\u5c06\u6240\u6709\u8fb9\u957f\u53d6\u8d1f<\/p>\n\n\n\n
                            for\u5faa\u73af\u5728\u89e3\u51b3\u5b50\u95ee\u9898{dist(u): u\u2208V}\uff0c\u6700\u521d\u7684\u5b50\u95ee\u9898\u662fdist(s)=0\uff0c\u7136\u540e\u9010\u6e10\u89e3\u51b3\u4e00\u4e2a\u66f4\u5927\u7684\u5b50\u95ee\u9898<\/p>\n\n\n\n
                            \u6700\u957f\u9012\u589e\u5b50\u5e8f\u5217<\/h3>\n\n\n\n
                            \u95ee\u9898\u63cf\u8ff0\uff1a\u7ed9\u51fa\u5e8f\u5217a1<\/sub>,\u2026,an<\/sub>\uff0c\u7ed9\u51fa\u4e00\u4e2a\u6709\u5e8f\u7684\u5b50\u5e8f\u5217ai1<\/sub>,ai2<\/sub>,\u2026,aik<\/sub>\uff0c\u5176\u4e2d1\u2264i1<i2<\u2026<ik\u2264n\uff0c\u4f7fk\u6700\u5927\u3002\u5982\uff1a<\/p>\n\n\n\n
                            \"\"\/<\/div><\/figure>\n\n\n\n
                            \u7b97\u6cd5\uff1a<\/p>\n\n\n\n
                              \n
                            • \u6309\u5927\u5c0f\u5173\u7cfb\u6784\u5efaDAG<\/li>\n\n\n\n
                            • \u627e\u6700\u957f\u8def\u5f84\n
                                \n
                              • \u7b2c\u4e00\u79cd\u65b9\u5f0f\uff1a\u5c06\u6240\u6709\u8fb9\u957f\u53d6\u8d1f<\/li>\n\n\n\n
                              • \u53e6\u4e00\u79cd\u65b9\u6cd5\uff1a
                                for j=1 to n do
                                | L(j)=1+max{L(i)|(i,j)\u2208E};
                                end
                                return maxj<\/sub>L(j);<\/code>\u5b9e\u9645\u5c31\u662f\u7b2c\u4e00\u79cd\u65b9\u6cd5\u628amin\u6539\u6210max<\/li>\n<\/ul>\n<\/li>\n<\/ul>\n\n\n\n
                                \u4e24\u79cd\u7b97\u6cd5\u7684\u65f6\u95f4\u590d\u6742\u5ea6\u90fd\u662fO(n2<\/sup>)\uff0c\u56e0\u4e3a\u6784\u5efaDAG\u5c31\u662fO(n2<\/sup>)\uff0c\u5faa\u73af\u6700\u5dee\u4e5f\u662fO(n2<\/sup>)<\/p>\n\n\n\n
                                \u4e8b\u5b9e\u4e0aL(j)=1+max{L(i)|(i,j)\u2208E};\u53ef\u4ee5\u7528\u4e00\u4e2a\u9012\u5f52\u7a0b\u5e8f\u89e3\u51b3\uff0c\u4f46\u662f\u4f7f\u7528\u9012\u5f52\u4f1a\u5bfc\u81f4\u590d\u6742\u5ea6\u53d8\u6210\u6307\u6570<\/p>\n\n\n\n
                                \u5e8f\u5217\u5bf9\u9f50 \u7f16\u8f91\u8ddd\u79bb<\/h3>\n\n\n\n
                                \u7f16\u8f91\u8ddd\u79bb\uff1a\u5c06\u4e24\u4e2a\u5b57\u7b26\u4e32\u901a\u8fc7\u6dfb\u52a0\u7a7a\u683c\u548c\u4fee\u6539\u7684\u65b9\u6cd5\u5bf9\u9f50\uff0c\u6700\u5c11\u9700\u8981\u51e0\u4e2a\u7a7a\u683c\u548c\u4fee\u6539
                                \u53ef\u4ee5\u5bf9\u201c\u7a7a\u683c\u201d\u548c\u201c\u4fee\u6539\u201d\u7ed9\u4e88\u4e0d\u540c\u7684\u6743\u91cd\uff0c\u751a\u81f3\u4e0d\u540c\u5b57\u6bcd\u5bf9\u95f4\u7684\u4fee\u6539\u6743\u91cd\u4e5f\u53ef\u4ee5\u4e0d\u540c<\/p>\n\n\n\n
                                \u5e8f\u5217\u5bf9\u9f50\uff1a\u5e0c\u671b\u5728\u7f16\u8f91\u8ddd\u79bb\u7684\u57fa\u7840\u4e0a\uff0c\u7ed9\u51fa\u6700\u77ed\u7f16\u8f91\u8ddd\u79bb\u7684\u60c5\u51b5\u4e0b\uff0c\u5bf9\u9f50\u7684\u90e8\u5206<\/p>\n\n\n\n
                                \"\"\/<\/div><\/figure>\n\n\n\n
                                \u5bf9\u4e8e\u539f\u95ee\u9898\u6784\u5efa\u5b50\u95ee\u9898<\/p>\n\n\n\n
                                  \n
                                • \u5047\u8bbe\u5b57\u7b26\u4e32x,y\u7684\u957f\u5ea6\u4e3am,n\uff0cE(i,j)\u8868\u793ax[1\u2026i],y[1\u2026j]\u65f6\u7684\u7f16\u8f91\u8ddd\u79bb<\/li>\n\n\n\n
                                • E(i,j)\u7684\u53d6\u503c\u65e0\u975e\u4e09\u79cd\n
                                    \n
                                  • \u4ec5x\u53d8\u957f\uff0cy\u589e\u52a0\u4e00\u4e2a\u7a7a\u683c\uff1a1+E(i-1,j)<\/li>\n\n\n\n
                                  • \u4ec5y\u53d8\u957f\uff0cx\u589e\u52a0\u4e00\u4e2a\u7a7a\u683c\uff1a1+E(i,j-1)<\/li>\n\n\n\n
                                  • xy\u540c\u65f6\u53d8\u957f\uff1adiff(i,j)+E(i-1,j-1)<\/li>\n<\/ul>\n<\/li>\n<\/ul>\n\n\n\n
                                    \u4f8b\uff1a\u6c42EXPONENTIAL\u548cPOLYNOMIAL\u7684\u7f16\u8f91\u8ddd\u79bb\u65f6\uff0c\u89e3\u5b50\u95ee\u9898E(4,3)\uff0c\u524d\u7f00EXPO\u548cPOL\uff0c\u5bf9\u5e94\u4e09\u79cd\u53d6\u503c<\/p>\n\n\n\n
                                    \"\"\/<\/div><\/figure>\n\n\n\n
                                    \u4e8b\u5b9e\u4e0a\uff0c\u7f16\u8f91\u8ddd\u79bb\u7684\u8ba1\u7b97\u53ef\u4ee5\u770b\u6210\u586b\u5199\u4e0b\u9762\u8fd9\u6837\u7684\u8868\u683c<\/p>\n\n\n\n
                                    \"\"\/<\/div><\/figure>\n\n\n\n
                                    algo:<\/strong><\/p>\n\n\n\n
                                    for i = 0 to m do\n| E(i,0) = i;\nend\nfor j = 1 to n do\n| E(0,j) = j;\nend\nfor i = 1 to m do\n| for j = 1 to n do\n| | E(i,j) = min{1+E(i-1,j),1+E(i,j-1),diff(i,j)+E(i-1,j-1)};\n| end\nend\nreturn(E(m,n));\n\ndiff(i,j)\nreturn x[i]==y[j]<\/code><\/pre>\n\n\n\n
                                    \u89e3\u51b3\u7f16\u8f91\u8ddd\u79bb\u540e\uff0c\u518d\u89e3\u51b3\u5e8f\u5217\u5bf9\u9f50\uff1a\u9700\u8981\u627e\u51fa\u7b54\u6848\u5f97\u51fa\u7684\u8def\u5f84\uff0c\u53ef\u4ee5\u5f97\u51fa\u7b54\u6848\u540e\u9006\u5411\u5bfb\u627e\u4e00\u6b21\uff08traceback\uff09\uff0c\u989d\u5916\u7a7a\u95f4\u53ca\u65f6\u95f4O(m+n)\uff1b\u6216\u8005\u5728\u586b\u8868\u65f6\u7528\u989d\u5916\u7a7a\u95f4\u8bb0\u5f55O(m\u00b7n)<\/p>\n\n\n\n
                                    \u586b\u4e86\u4e00\u4e2am\u00b7n\u7684\u8868\uff0c\u65f6\u95f4\u590d\u6742\u5ea6O(m\u00b7n)\u7a7a\u95f4\u4e5f\u662fO(m\u00b7n)
                                    \u7a7a\u95f4\u53ef\u4f18\u5316\uff1a\u56e0\u4e3a\u586b\u8868\u662f\u4e00\u884c\u4e00\u884c\u586b\uff0c\u6211\u4eec\u53ea\u9700\u8981\u4fdd\u5b58\u4e0a\u4e00\u884c\u5c31\u884c\uff0c\u6b64\u65f6\u7a7a\u95f4\u590d\u6742\u5ea6\u4e3aO(m+n)\uff0c\u56e0\u4e3a\u9700\u8981traceback<\/p>\n\n\n\n
                                    \u5c06\u52a8\u5f52\u8868\u6784\u9020\u6210\u5982\u4e0b\u7684DAG\uff0c\u7f16\u8f91\u8ddd\u79bb\u662f\u53f3\u4e0b\u89d2\u5230\u5de6\u4e0a\u89d2\u7684\u6700\u77ed\u8def\u5f84<\/p>\n\n\n\n
                                    \"\"<\/div><\/figure>\n\n\n\n
                                    \u76ee\u524d\u65f6\u95f4\u590d\u6742\u5ea6\u4ecd\u4e3aO(m\u00b7n)\uff0c\u53ef\u4ee5\u91c7\u7528\u5206\u6cbb\u6cd5\uff08\u4ece0\u5230n\/2\uff0c\u4ecen\/2\u5230n\uff09\uff0c\u5206\u6210\u4e24\u6bb5\u6700\u77ed\u8def\u5f84\u5206\u522b\u8ba1\u7b97
                                    \u6ce8\u610f\u4ecd\u7136\u662f\u8ba1\u7b97n\/2\u6574\u5217\uff0c\u56e0\u4e3a\u4e0d\u80fd\u786e\u5b9a\u6700\u77ed\u8def\u5f84\u7ecf\u8fc7\u5217\u4e0a\u54ea\u4e2a\u70b9<\/p>\n\n\n\n
                                    \"\"<\/div><\/figure>\n\n\n\n
                                    \u6b64\u65f6\u7a7a\u95f4\u590d\u6742\u5ea6\u4e3aO(min{m,n})\uff0c\u65f6\u95f4\u4e3aO(m\u00b7n)<\/p>\n\n\n\n
                                    \u6700\u957f\u516c\u5171\u5b50\u5e8f\u5217LCS<\/h3>\n\n\n\n
                                    \u95ee\u9898\u63cf\u8ff0\uff1a\u7ed9\u5b9ax[1,…,m],y[1,…,n]\uff0c\u5206\u522b\u5220\u9664x,y\u7684\u4e00\u90e8\u5206\uff0c\u4f7f\u5f97\u5269\u4e0b\u7684\u5b57\u7b26\u4e32\u76f8\u540c\uff0c\u8fd9\u4e2a\u5b57\u7b26\u4e32\u6700\u957f\u662f\u4ec0\u4e48<\/p>\n\n\n\n
                                    \u4f8b\uff1aLCS(GGCA<\/strong>CCACG<\/strong>, ACGGC<\/strong>GGA<\/strong>TACG<\/strong> ) = GGCAACG<\/p>\n\n\n\n
                                    \"LCS[i,j]=\left\{\begin{array}{lr}& 0\\& LCS[i-1,j-1]+1\\&max\{LCS[i-1,j],LCS[i,j-1]\}\\\end{array}\right.\begin{array}{lr}& if\quad i=0 \vee j=0\\& if\quad a[i]==b[j]\\& otherwise\\\end{array}\"<\/div><\/p>\n\n\n\n
                                    \u76f8\u5173\u95ee\u9898\uff1a\u6700\u957f\u516c\u5171\u5b50\u4e32<\/strong><\/p>\n\n\n\n
                                    \"LCS[i,j]=\left\{\begin{array}{lr}& 0\\& LCS[i-1,j-1]+1\\&0\\\end{array}\right.\begin{array}{lr}& if\quad i=0 \vee j=0\\& if\quad a[i]==b[j]\\& otherwise\\\end{array}\"<\/div><\/p>\n\n\n\n
                                    \u6709\u8d1f\u8fb9\u65e0\u8d1f\u73af\u7684\u6700\u77ed\u8def\u5f84\u2014\u2014\u8d1d\u5c14\u66fc\u00b7\u798f\u7279\u7b97\u6cd5<\/h3>\n\n\n\n
                                    ShortestPaths(V,E,l,t)\nfor each node (v \u2208 V) do\n| dist[v, 0] \u2190 \u221e;\nend\ndist[t, 0] \u2190 0;\nfor i = 1 to n\u22121 do\n| for each node v \u2208 V do\n| | dist[v, i] \u2190 dist[v,i \u2212 1];\n| | for each edge (v,w) \u2208 E do\n| | | dist[v, i] \u2190 min{dist[v,i],dist[w,i \u2212 1] +lvw<\/sub>};\n| | end\n| end\nend<\/code><\/pre>\n\n\n\n
                                    \"\"<\/div><\/figure>\n\n\n\n
                                    \u95ee\u9898\uff1a\u8d1f\u73af\u7684\u51fa\u73b0\u4f7f\u5f97\u8def\u5f84\u65e0\u610f\u4e49
                                    \u89e3\u51b3\uff1a\u5728|V|-1\u8f6e\u4ee5\u540e\u518d\u8fdb\u884c\u4e00\u8f6e\uff0c\u5982\u679c\u6709\u503c\u53d8\u5316\u5219\u5b58\u5728\u8d1f\u73af<\/p>\n\n\n\n
                                    \u65f6\u95f4\u590d\u6742\u5ea6\uff1aO(|V||E|)
                                    \u7a7a\u95f4\u590d\u6742\u5ea6\uff1aO(|V|\u00b2)<\/p>\n\n\n\n
                                    \u4f18\u5316\uff1a\u53ea\u9700\u8981\u4e00\u5217\uff0c\u76f4\u63a5\u5728\u8fd9\u4e00\u5217\u4e0a\u66f4\u65b0\u5373\u53ef\uff0c\u518d\u7528\u989d\u5916\u7684\u6570\u636e\u7ed3\u6784\u8bb0\u5f55\u6700\u77ed\u8def\u5f84\u3002\u7a7a\u95f4\u964d\u4e3aO(|V|)<\/p>\n\n\n\n
                                    \u6700\u77ed\u53ef\u9760\u8def\u5f84<\/strong><\/h4>\n\n\n\n
                                    \u95ee\u9898\u63cf\u8ff0\uff1a\u6c42\u4e24\u70b9\u95f4\u6700\u77ed\u8def\u5f84\uff0c\u4f46\u9650\u5236\u6700\u591a\u7ecf\u8fc7k\u4e2a\u8282\u70b9<\/p>\n\n\n\n
                                    F(i,v) \u8868\u793a\u7ecf\u8fc7i\u4e2a\u8282\u70b9\u5230\u8fbev\u8282\u70b9\u7684\u7684\u6700\u77ed\u8def\u5f84
                                    \u9012\u63a8\u5f0f\uff1aF(i,v)=min{mine(u,v)\u2208E<\/sub>{F(i-1,u)+l(u,v)},F(i-1,v)}
                                    \u5185\u5c42min\u8868\u793a\u8868\u793a\u6c42\u6070\u597d\u7ecf\u8fc7i\u4e2a\u8282\u70b9\u7684\u6700\u77ed\u8def\u5f84\uff0c\u5916\u5c42min\u8868\u793a\u53ef\u4ee5\u7ecf\u8fc7\u6bd4i\u5c0f\u4e2a\u8282\u70b9<\/p>\n\n\n\n
                                    \u4f7f\u7528\u77aa\u773c\u6cd5\uff0c\u53ef\u4ee5\u53d1\u73b0\u6070\u597d\u662f\u8d1d\u5c14\u66fc\u00b7\u798f\u7279\u7b97\u6cd5\u586b\u8868\u7684\u524dk\u5217<\/p>\n\n\n\n
                                    \u591a\u6e90\u6700\u77ed\u8def\u5f84All-pairs shortest path<\/h4>\n\n\n\n
                                    \u95ee\u9898\u63cf\u8ff0\uff1a\u5f97\u51fa\u56fe\u4e2d\u4efb\u610f\u4e24\u4e2a\u9876\u70b9\u95f4\u7684\u6700\u77ed\u8def\u5f84<\/p>\n\n\n\n
                                    \u663e\u7136\uff0c\u6211\u4eec\u53ef\u4ee5\u5728\u6bcf\u4e2a\u8282\u70b9\u4e0a\u505a\u4e00\u6b21\u8d1d\u5c14\u66fc\u798f\u7279\u7b97\u6cd5\uff0c\u590d\u6742\u5ea6O(|V|2<\/sup>|E|)\uff0c\u56e0\u4e3a\u70b9\u4e00\u822c\u6bd4\u8fb9\u5c11\uff0c\u6240\u4ee5\u76ee\u6807\u662fO(|V|3<\/sup>)<\/p>\n\n\n\n
                                    Floyd-Warshall\u7b97\u6cd5<\/strong><\/p>\n\n\n\n
                                    \u5c06\u9876\u70b9\u7f16\u53f71…n
                                    \u7528dist(u,v,k)\u8868\u793au,v\u4e24\u70b9\u95f4\uff0c\u53ea\u4f7f\u7528\u524dk\u4e2a\u9876\u70b9\u7684\u6700\u77ed\u8ddd\u79bb
                                    \u9012\u63a8\u5f0f\uff1adist(u,v,k)=min{dist(u,v,k-1), dist(u,k,k-1)+dist(k,v,k-1)}\/\/\u6ce8\u610fk\u5728\u524d\u4e24\u4e2a\u53d8\u91cf\u65f6\u8868\u793a\u7b2ck\u4e2a\u9876\u70b9<\/p>\n\n\n\n
                                    algo:<\/strong><\/p>\n\n\n\n
                                    for i = 1 to n do\n| for j = 1 to n do\n| | dist(i, j, 0) = \u221e;\n| end\nend\nfor all (i,j) \u2208 E do\n| dist(i, j, 0) = l(i,j);\nend\nfor k = 1 to n do\n| for i = 1 to n do\n| | for j = 1 to n do\n| | | dist(i, j, k) = min{dist(i,j,k \u2212 1),dist(i,k,k \u2212 1) + dist(k,j,k \u2212 1)};\n| | end\n| end\nend<\/code><\/pre>\n\n\n\n
                                    \u80cc\u5305\u95ee\u9898<\/h3>\n\n\n\n
                                    \u95ee\u9898\u63cf\u8ff0\uff1a\u80cc\u5305\u5bb9\u91cfW\uff0c\u7269\u54c1\u6709n\u79cd\uff0c\u7269\u54c1i\u6709\u4ef7\u503cv[i]\u548c\u4f53\u79efw[i]\uff0c\u7269\u54c1\u4e2a\u6570\u65e0\u9650\uff0c\u5982\u4f55\u88c5\u4ef7\u503c\u6700\u9ad8\uff1f<\/p>\n\n\n\n
                                    \u6784\u5efa\u5b50\u95ee\u9898\uff1a<\/p>\n\n\n\n
                                    \"$K(w)=max_{i:w[i]\leq w}\{ K(w-w[i])+v[i]\} $\"<\/div><\/p>\n\n\n\n
                                    algo:<\/strong><\/p>\n\n\n\n
                                    K(0) = 0;\nfor w = 1to W do\n| K(w) =maxi:w[i]\u2264w<\/sub>{K(w-w[i])+v[i]};\nend\nreturn(K(W));<\/code><\/pre>\n\n\n\n
                                    \u65f6\u95f4\u590d\u6742\u5ea6\uff1aO(n\u00b7W)<\/p>\n\n\n\n
                                    \u5982\u679c\u4e2a\u6570\u53ea\u67091\u4e2a\uff1f<\/p>\n\n\n\n
                                    algo:<\/strong><\/p>\n\n\n\n
                                    Initialize all K(0,j) = 0 and all K(w,0) = 0;\nfor w = 1 to W do\/\/\u6c42\u51fa\u5bb9\u91cf\u4e3aw\u65f6\u7684\u6700\u5927\u4ef7\u503c\n| for j = 1 to n do\/\/\u6c42\u51fa\u53ea\u6709\u524dj\u4e2a\u7269\u54c1\u65f6\u7684\u6700\u5927\u503c\n| | if wj<\/sub> > w then K(w,j) = K(w,j-1);\n| | K(w,j) =max{K(w-wj<\/sub>,j-1)+vj<\/sub>,K(w,j-1)};\/\/\u5728\u91cd\u91cf\u4e3aw-wj<\/sub>\u7684\u57fa\u7840\u4e0a\u653e\u5165\u7b2cj\u4e2a\u7269\u54c1\u6216\u4e0d\u653e\u5165\n| end\nend\nreturn(K(W,n));<\/code><\/pre>\n\n\n\n
                                    \u65f6\u95f4\u590d\u6742\u5ea6\uff1aO(n\u00b7W)<\/p>\n\n\n\n
                                    \u7f51\u7edc\u6d41<\/h2>\n\n\n\n
                                    \u6700\u5927\u6d41\u6700\u5c0f\u5272<\/h3>\n\n\n\n
                                    \u95ee\u9898\u63cf\u8ff0\uff1a<\/p>\n\n\n\n
                                      \n
                                    • \u6700\u5927\u6d41\uff1a\u6709\u5411\u56fe\uff0c\u6bcf\u6761\u8fb9\u6709\u6700\u5927\u6d41\u91cf\uff0c\u95ee\u4eces\u5230t\u7684\u6700\u5927\u6d41\u91cf\u662f\u591a\u5c11<\/li>\n\n\n\n
                                    • \u6700\u5c0f\u5272\uff1a\u6709\u5411\u56fe\uff0c\u6bcf\u6761\u8fb9\u6709\u6743\u503c\uff0c\u7528\u4e00\u4e2a\u5272\u5c06s\u548ct\u5206\u5f00\uff0c\u5207\u5272\u7684\u6700\u5c0f\u6743\u503c\u662f\u591a\u5c11<\/li>\n<\/ul>\n\n\n\n
                                      \u8bc1\u660e\u6700\u5927\u6d41\u7b49\u4e8e\u6700\u5c0f\u5272<\/strong><\/p>\n\n\n\n
                                      \u4ee4f\u4e3a\u56fe\u4e0a\u7684\u6d41\uff0c\uff08A,B\uff09\u4e3a\u56fe\u4e0a\u7684\u5272\uff0c\u5f53\u4e14\u4ec5\u5f53val(f)=cap(A,B)\uff0cf\u4e3a\u6700\u5927\u6d41\u4e14(A,B)\u4e3a\u6700\u5c0f\u5272<\/p>\n\n\n\n
                                      \u8bc1\u660e\uff1a
                                      \u9996\u5148\u8bc1\u660e\u5bf9\u4efb\u610f\u6d41f\u548c\u4efb\u610f\u5272(A,B)\uff0c\u6709val(f)\u2264cap(A,B)<\/p>\n\n\n\n
                                      \"$val(f)=\sum_{e\ out\ of\ s}f(e)-\sum_{e\ in\ to\ s}f(e)\\=\sum_{v \in A}\left(\sum_{e\ out\ of\ v}f(e)-\sum_{v\ in\ to\ s}f(e) \right) \\=\sum_{e\ out\ of\ A}f(e)-\sum_{e\ in\ to\ A}f(e)\\ \leq\sum_{e\ out\ of\ A}f(e)\\ \leq\sum_{e\ out\ of\ A}c(e)\\=cap(A,B)$\"<\/div><\/p>\n\n\n\n
                                      \u56e0\u6b64\u6d41\u7b49\u4e8e\u5272\u65f6\uff0c\u6d41\u662f\u6700\u5927\u6d41\uff0c\u5272\u662f\u6700\u5c0f\u5272<\/p>\n\n\n\n
                                      \u798f\u7279\u00b7\u798f\u514b\u68ee\u7b97\u6cd5<\/h4>\n\n\n\n
                                        \n
                                      • \u4ece\u6240\u6709\u8fb9\u6d41\u91cf\u4e3a\u96f6\u5f00\u59cb<\/li>\n\n\n\n
                                      • \u627e\u5230\u4e00\u6761\u4eces\u5230t\u7684\u8def\u5f84\uff0c\u4f7f\u6d41\u91cf\u5c3d\u53ef\u80fd\u5927<\/li>\n\n\n\n
                                      • \u56e0\u4e3a\u6211\u4eec\u9700\u8981\u6709\u5c06\u4e00\u4e2a\u6d41\u201c\u53d6\u6d88\u201d\u80fd\u529b\uff0c\u6240\u4ee5\u5982\u679c\u5728\u7b2c\u4e8c\u6b65\u4e2d\u5360\u7528\u4e86\u8fb9(u,v)\u4e0af\u7684\u6d41\u91cf\uff0c\u5c31\u6dfb\u52a0\u4e00\u6761(v,u)\u4e0a\u5bb9\u91cf\u4e3af\u7684\u65b0\u8fb9<\/li>\n\n\n\n
                                      • \u91cd\u590d\u505a2\u548c3\uff0c\u76f4\u5230\u627e\u4e0d\u5230\u4e00\u6761s\u5230t\u7684\u8def\u5f84<\/li>\n<\/ul>\n\n\n\n
                                        \u4f8b\uff1a<\/p>\n\n\n\n
                                        \n
                                        \n
                                        \u539f\u56fe\uff1a<\/p>\n\n\n\n
                                        \"\"<\/div><\/figure>\n<\/div>\n\n\n\n
                                        \n
                                        \u627e\u5230\u8def\u5f84sabt\uff0c<\/p>\n\n\n\n
                                        \"\"<\/div><\/figure>\n<\/div>\n\n\n\n
                                        \n
                                        \u627e\u5230\u8def\u5f84sbat\uff0c\u4f7f\u7528\u4e86\u4e0a\u4e00\u6b65\u6dfb\u52a0\u7684e(b,a)<\/p>\n\n\n\n
                                        \"\"<\/div><\/figure>\n<\/div>\n<\/div>\n\n\n\n
                                        \u6700\u7ec8\u7ed3\u679c\uff1a<\/p>\n\n\n\n
                                        \"\"<\/div><\/figure>\n\n\n\n
                                        FORD\u2013FULKERSON()\nfor each edge e \u2208 E do\n| f(e)\u21900\nend\nGf \u2190residual network of G with respect to flow f;\nwhile there exists an s t path P in Gf do\n| f \u2190AUGMENT(f,P);\n| UPDATE(Gf);\nend\nRETURN f;<\/code><\/pre>\n\n\n\n
                                        \u65f6\u95f4\u590d\u6742\u5ea6\uff1a\u5047\u8bbe\u6700\u5927\u6d41\u7684\u503c\u662fC\uff0c\u6211\u4eec\u6700\u5dee\u6bcf\u6b21\u53ef\u4ee5\u589e\u52a01\uff0c\u6240\u4ee5\u65f6\u95f4\u590d\u6742\u5ea6\u662fO(C|E||V|)\uff08\u4efb\u610f\u574f\u7684\uff09\uff0c\u5982\u679c\u5bb9\u91cf\u662f\u65e0\u7406\u6570\u751a\u81f3\u65e0\u6cd5\u7ec8\u6b62<\/p>\n\n\n\n
                                        \u4e0b\u9762\u6211\u4eec\u4f1a\u4ecb\u7ecd\u51e0\u79cd\u4f18\u5316\u65b9\u6cd5\uff0c\u57fa\u4e8e\u4e0d\u540c\u7684\u589e\u5e7f\u8def\u5f84\u9009\u53d6\u7b56\u7565\uff0c\u5bf9\u798f\u7279\u00b7\u798f\u514b\u68ee\u7b97\u6cd5\u505a\u4f18\u5316<\/p>\n\n\n\n
                                        \u5bb9\u91cf\u653e\u7f29\u7b97\u6cd5Capacity-Scaling Algorithm<\/h4>\n\n\n\n
                                        \u60f3\u6cd5\uff1a\u6bcf\u6b21\u9009\u53d6\u5bb9\u91cf\u8f83\u5927\u7684\u589e\u5e7f\u8def\u5f84<\/p>\n\n\n\n
                                        \u7b97\u6cd5\uff1a\u4f7f\u7528\u4e00\u4e2a\u9010\u6e10\u53d8\u5c0f\u7684\u0394\uff0c\u4f18\u5148\u8003\u8651\u5bb9\u91cf\u5927\u4e8e\u0394\u7684\u8fb9\uff0c\u7528\u5c3d\u8fd9\u4e9b\u8fb9\u540e\u7f29\u5c0f\u0394\uff0c\u6700\u7ec8\u8003\u8651\u6240\u6709\u8fb9<\/p>\n\n\n\n
                                        CAPACITY-SCALING(G)\nfor each edge e \u2208 E do\n| f(e)\u21900\nend\n\u2206\u2190largest power of 2 \u2264 C;\nwhile \u2206 \u2265 1 do\n| Gf<\/sub>(\u2206) \u2190\u2206-residual network of G with respect to flow f;\n| while there exists an s t path P in Gf<\/sub>(\u2206) do\n| | f \u2190AUGMENT(f, P);\n| | UPDATE(G\u2206<\/sub>(f));\n| end\n| \u2206=\u2206\/2;\nend\nRETURN f;<\/code><\/pre>\n\n\n\n
                                        C\u662f\u6700\u5927\u8fb9\u957f\uff0c\u4e14\u6700\u5c0f\u8fb9\u957f\u4e3a1<\/p>\n\n\n\n
                                        \u8bc1\u660e\u6b63\u786e\u6027\uff1a\u6700\u7ec8\u0394\u4f1a\u53d6\u52301\uff0c\u0394\u53d61\u65f6\uff0c\u6bcf\u6761\u8fb9\u90fd\u4f1a\u88ab\u8003\u8651\uff0c\u76f8\u5f53\u4e8e\u798f\u7279\u798f\u514b\u68ee\u7b97\u6cd5<\/p>\n\n\n\n
                                        \u65f6\u95f4\u590d\u6742\u5ea6\uff1a\u5916\u5c42\u5faa\u73af\u8fd0\u884c1+logC\u6b21\uff0c\u5185\u5c42\u5faa\u73af\u6bcf\u6b21\u6700\u591a\u589e\u5e7f2|E|\u6b21\uff0cO(|E|2<\/sup>logC)<\/p>\n\n\n\n
                                        Edmonds-Karp\u7b97\u6cd5<\/h4>\n\n\n\n
                                        \u60f3\u6cd5\uff1a\u9009\u53d6\u6700\u77ed\u7684\u589e\u5e7f\u8def\u5f84<\/p>\n\n\n\n
                                        \u7b97\u6cd5\uff1a\u5c06DFS\u3001BFS\u6df7\u5408\u6539\u4e3a\u53ea\u4f7f\u7528BFS<\/p>\n\n\n\n
                                        EDMONDS\u2013KARP\u2019S ALGORITHM(G)\nfor each edge e \u2208 E do\n| f(e)\u21900\nend\nGf<\/sub> \u2190residual network of G with respect to flow f;\nwhile there exists an s\u2192t path in Gf<\/sub> do\n| P \u2190BFS(Gf<\/sub>);\n| f \u2190AUGMENT(f, P);\n| UPDATE(Gf<\/sub>);\nend\nRETURN f;<\/code><\/pre>\n\n\n\n
                                        \u65f6\u95f4\u590d\u6742\u5ea6\uff1aO(|V||E|2<\/sup>)<\/p>\n\n\n\n
                                        Dinitz\u2019 Algorithm<\/h4>\n\n\n\n
                                          \n
                                        • \u4eces\u5f00\u59cb\uff0c\u5c1d\u8bd5\u627e\u4e00\u6761\u5230t\u7684\u8def\u5f84<\/li>\n\n\n\n
                                        • \u5982\u679c\u627e\u5230\u8def\u5f84\uff0c\u5219\u5728\u539f\u56fe\u4e2d\u5220\u53bb\u5bf9\u5e94\u7684\u6d41<\/li>\n\n\n\n
                                        • \u5982\u679c\u4e2d\u95f4\u8d70\u5230\u70b9v\u5361\u4f4f\uff0c\u6ca1\u6709\u8def\u5f84\uff0c\u5219\u5220\u53bb\u70b9v\uff0c\u5e76\u56de\u6eaf\u5230\u4e0a\u4e00\u4e2a\u70b9<\/li>\n<\/ul>\n\n\n\n
                                          \u65f6\u95f4\u590d\u6742\u5ea6\uff1aO(|V|2<\/sup>|E|)<\/p>\n\n\n\n
                                          \u5355\u4f4d\u5bb9\u91cf\u7f51\u7edc<\/h3>\n\n\n\n
                                          \u4e8c\u5206\u5339\u914d<\/h4>\n\n\n\n
                                          \u95ee\u9898\u63cf\u8ff0\uff1a\u5728\u4e00\u4e2a\u56fe\u4e2d\uff0c\u9876\u70b9\u88ab\u5206\u4e3aLR\u4e24\u4e2a\u5b50\u96c6\uff0c\u627e\u5230\u6700\u591a\u7684\u8fb9\u6a2a\u8de8LR\uff0c\u4e14\u6bcf\u4e2a\u9876\u70b9\u53ea\u4f7f\u7528\u4e00\u6b21<\/p>\n\n\n\n
                                          \"\"<\/div><\/figure>\n\n\n\n
                                          \u89c4\u7ea6\u5230\u5982\u4e0b\u6d41\u95ee\u9898<\/p>\n\n\n\n
                                          \"\"<\/div><\/figure>\n\n\n\n
                                          \u65f6\u95f4\u590d\u6742\u5ea6\uff1aO(|E||V|)\uff08\u4f7f\u7528\u798f\u7279\u798f\u514b\u68ee\u7b97\u6cd5\uff0c\u56e0\u4e3aC\u4e00\u5b9a\uff09<\/p>\n\n\n\n
                                          \u5b8c\u7f8e\u5339\u914d<\/h4>\n\n\n\n
                                          \u5728\u4e8c\u5206\u5339\u914d\u7684\u57fa\u7840\u4e0a\uff0c\u4f7f\u5f97\u6bcf\u4e2a\u9876\u70b9\u90fd\u6709\u53e6\u4e00\u4e2a\u9876\u70b9\u4e0e\u4e4b\u5339\u914d<\/p>\n\n\n\n
                                          \u4ee4N(S)\u4e3a\u4e0eS\u4e2d\u9876\u70b9\u76f8\u8fde\u7684\u9876\u70b9\u7684\u96c6\u5408\uff0c\u7b80\u5355\u89c2\u5bdf\uff0c\u53d1\u73b0\u5bf9\u4efb\u610fS\uff0c\u90fd\u9700\u8981\u6709|N(S)|\u2265|S|\uff0c\u95ee\u9898\u624d\u6709\u53ef\u80fd\u6709\u89e3\uff08\u5fc5\u8981\u6027\uff09<\/p>\n\n\n\n
                                          Hall’s Marriage Theorem<\/strong>\uff1a\u4e8c\u5206\u56fe\u6709\u5b8c\u7f8e\u5339\u914d\uff0c\u5f53\u4e14\u4ec5\u5f53\u5bf9\u4efb\u610fS\uff0c\u90fd\u6709|N(S)|\u2265|S|<\/p>\n\n\n\n
                                          \u8bc1\u660e\uff1a\u5fc5\u8981\u6027\u6613\u5f97
                                          \u5145\u5206\u6027\uff1a
                                          \u4f7f\u7528\u53cd\u8bc1\u6cd5\uff0c\u82e5\u6ca1\u6709\u5b8c\u7f8e\u5339\u914d\uff0c\u5219\u5fc5\u6709\u4e00\u4e2a\u5b50\u96c6S\u6ee1\u8db3|N(S)|\uff1c|S|
                                          \u5047\u8bbe\u56feG(L\u222aR,E)\u6ca1\u6709\u5b8c\u7f8e\u5339\u914d\uff0c\u4ee4E\u4e2d\u6240\u6709\u8fb9\u5bb9\u91cf\u4e3a\u221e\uff0c\u6dfb\u52a0\u6e90\u70b9S\u8fde\u63a5L\uff0c\u6c47\u70b9T\u8fde\u63a5R\uff0c\u6784\u6210\u56feG’
                                          \u5219\u5728\u56feG’\u4e0a\u627e\u5230\u7684\u6700\u5c0f\u5272(A,B)\u4e0d\u4f1a\u5305\u542b\u4efb\u4f55\u4e00\u6761E\u4e0a\u7684\u8fb9\uff08\u56e0\u4e3a\u6743\u503c\u4e3a\u221e\uff09
                                          \u4ee4LA<\/sub>=L\u2229A,LB<\/sub>=L\u2229B,RA<\/sub>=R\u2229A,RB<\/sub>=R\u2229B\uff1b
                                          cap(A,B)=|RA<\/sub>|+|LB<\/sub>|\uff1c|LA<\/sub>|+|LB<\/sub>|=|L|
                                          \u5219|RA<\/sub>|<|LA<\/sub>|,
                                          LA<\/sub>\u5373\u4e3a\u6ee1\u8db3\u6761\u4ef6\u7684\u5b50\u96c6S<\/p>\n\n\n\n
                                          Hackathon Problem<\/strong><\/p>\n\n\n\n
                                          \u95ee\u9898\u63cf\u8ff0\uff1a\u5728\u4e8c\u5206\u56fe\u4e2d\uff0cL\u4e2d\u4efb\u610f\u9876\u70b9v\u90fd\u6709N(v)=k\uff0cR\u4e2d\u4efb\u610f\u9876\u70b9\u90fd\u6709N(v)=k
                                          \u8fd9\u6837\u7684\u56fe\u4e00\u5b9a\u6709\u5b8c\u7f8e\u5339\u914d<\/p>\n\n\n\n
                                          \u8bc1\u660e\uff1a\u6211\u4eec\u5e0c\u671b\u627e\u5230\u4e00\u4e2a\u6d41\u91cf\u4e3a|L|=|R|\u7684\u6d41\uff0c\u4ee4L\u5230R\u7684\u6bcf\u6761\u8fb9\u5bb9\u91cf\u4e3a1\/k\uff0c\u5176\u4f59\u8fb9\u5bb9\u91cf\u4e3a1\uff0c\u6bcf\u6761\u8fb9\u6d41\u6ee1\u7684\u65f6\u5019\u6b63\u597d\u6ee1\u8db3\u6d41\u91cf\u8981\u6c42\u3002<\/p>\n\n\n\n
                                          \"\"<\/div><\/figure>\n\n\n\n
                                          Simple Unit-Capacity Networks<\/h4>\n\n\n\n
                                          \u95ee\u9898\u63cf\u8ff0\uff1a\u5728\u6700\u5927\u6d41\u6700\u5c0f\u5272\u95ee\u9898\u4e2d\uff0c\u6240\u6709\u8fb9\u5bb9\u91cf\u5747\u4e3a1\uff0c\u5e76\u4e14\u5bf9\u4e8e\u6bcf\u4e2a\u975es\u3001t\u7684\u9876\u70b9\uff0c\u6216\u5165\u5ea6\u4e3a1\uff0c\u6216\u51fa\u5ea6\u4e3a1\uff08\u5982\u4e0a\u56fe\uff09<\/p>\n\n\n\n
                                          \u4f7f\u7528Dinitz\u2019\u7b97\u6cd5\uff0c\u65f6\u95f4\u590d\u6742\u5ea6\u4e3aO(|E||V|1\/2<\/sup>)<\/p>\n\n\n\n
                                          \u8bc1\u660e\uff1a<\/p>\n\n\n\n
                                            \n
                                          • \u6bcf\u4e00\u6b21\u627e\u5230\u4e00\u6761\u8def\u5f84\uff0c\u8017\u8d39O(|E|)\uff08\u6bcf\u6b21\u627e\u5230\u4e00\u6761\u8def\u5f84\uff0c\u90fd\u8981\u5168\u90e8\u5220\u53bb\u8def\u5f84\uff09<\/li>\n\n\n\n
                                          • \u5728|V|1\/2<\/sup>\u6b21\u589e\u5e7f\u540e\uff0cval(f*)\u2264val(f)+|V|1\/2<\/sup>\uff08\u5728|V|1\/2<\/sup>\u6b21\u589e\u5e7f\u540e\uff0c\u6700\u77ed\u8def\u5f84\u957f\u5ea6\u5927\u4e8e|V|1\/2<\/sup>\uff0c\u56e0\u6b64level graph\u81f3\u5c11|V|1\/2<\/sup>\u5c42\uff1b\u524d|V|1\/2<\/sup>\u5c42\u81f3\u5c11\u6709\u4e00\u5c42\u7684\u9876\u70b9\u6570\u91cf\u5c0f\u4e8e\u7b49\u4e8e|V|1\/2<\/sup>\uff08\u5e73\u5747\u503c\uff09\uff0c\u56e0\u6b64\u81f3\u591a\u518d\u627e\u5230|V|1\/2<\/sup>\u6761\u8def\u5f84\uff0c\u5c31\u65e0\u6cd5\u627e\u5230\u5176\u4ed6\u8def\u5f84\uff09<\/li>\n\n\n\n
                                          • O(|V|1\/2<\/sup>)\u6b21\u589e\u5e7f\u8db3\u591f\u8ba9\u6d41\u8fbe\u5230\u6700\u4f18\u503c<\/li>\n<\/ul>\n\n\n\n
                                            Edge-Disjoint Paths<\/h4>\n\n\n\n
                                            \u95ee\u9898\u63cf\u8ff0\uff1a\u5728\u6709\u5411\u65e0\u73af\u56fe\u4e2d\uff0c\u627e\u51fa\u7531\u6e90\u70b9s\u5230\u6c47\u70b9t\u6700\u591a\u7684\u8fb9\u4e0d\u76f8\u4ea4\u7684\u8def\u5f84<\/p>\n\n\n\n
                                            \u4ee4\u6bcf\u6761\u8fb9\u5bb9\u91cf\u4e3a\u4e00\uff0c\u6c42\u6700\u5927\u6d41\u5373\u53ef<\/p>\n\n\n\n
                                            Network Connectivity<\/h4>\n\n\n\n
                                            \u95ee\u9898\u63cf\u8ff0\uff1a\u5728\u56fe\u4e2d\uff0c\u53bb\u6389\u6700\u5c11\u6570\u91cf\u7684\u8fb9\uff0c\u4f7f\u5f97\u70b9s\u5230\u70b9t\u4e0d\u5b58\u5728\u8def\u5f84<\/p>\n\n\n\n
                                            \u4ee4\u6bcf\u6761\u8fb9\u5bb9\u91cf\u4e3a\u4e00\uff0c\u6c42\u6700\u5c0f\u5272\u5373\u53ef<\/p>\n\n\n\n
                                            \u4eces\u5230t\u7684\u8fb9\u4e0d\u76f8\u4ea4\u8def\u5f84\u7684\u4e2a\u6570\u7b49\u540c\u4e8e\u4f7fs\u5230t\u4e0d\u5b58\u5728\u8def\u5f84\u9700\u8981\u53bb\u6389\u7684\u6700\u5c11\u7684\u8fb9\u7684\u4e2a\u6570<\/p>\n\n\n\n
                                            \u7ebf\u6027\u89c4\u5212<\/h2>\n\n\n\n
                                            \u7ebf\u6027\u89c4\u5212\u95ee\u9898\u7684\u5b9a\u4e49\uff1a\u7ed9\u5b9a\u4e00\u7cfb\u5217\u53d8\u91cf\uff0c\u7ed9\u53d8\u91cf\u8d4b\u503c\uff0c\u4f7f\u5f97\u53d8\u91cf\u7684\u503c\u6ee1\u8db3\u4e00\u7cfb\u5217\u7b49\u5f0f\u53ca\u4e0d\u7b49\u5f0f\uff0c\u5e76\u4f7f\u76ee\u6807\u51fd\u6570\u6700\u5927\u5316\/\u6700\u5c0f\u5316<\/p>\n\n\n\n
                                            \u9664\u4e86Infeasible\uff08\u4e0d\u5b58\u5728\u53ef\u89e3\u7a7a\u95f4\uff09\u548cUnbounded\uff08\u53ef\u89e3\u7a7a\u95f4\u65e0\u8fb9\u754c\uff0c\u8fd9\u79cd\u60c5\u51b5\u4e5f\u53ef\u80fd\u5728\u9876\u70b9\u4e0a\uff09\u4e24\u79cd\u60c5\u51b5\uff0c\u7ebf\u6027\u89c4\u5212\u7684\u6700\u4f18\u89e3\u90fd\u5728\u9876\u70b9\u4e0a<\/p>\n\n\n\n
                                            \u6d45\u8c08\u5355\u7eaf\u5f62\u6cd5Simplex Method<\/h3>\n\n\n\n
                                            \u722c\u5c71\u6cd5\u3002\u5728\u591a\u8fb9\u5f62\u7684\u9876\u70b9\u4e0a\uff0c\u79fb\u52a8\u5230\u503c\u66f4\u4f18\u7684\u90bb\u5c45\uff0c\u76f4\u5230\u6ca1\u6709\u90bb\u5c45\u6bd4\u81ea\u5df1\u66f4\u4f18\u3002<\/p>\n\n\n\n
                                            \u95ee\u9898\uff1a\u600e\u4e48\u89e3\u51fa\u9876\u70b9\uff1b\u600e\u4e48\u786e\u5b9a\u90bb\u5c45<\/p>\n\n\n\n
                                            \u9876\u70b9\uff1a\u4e8c\u7ef4\u4e24\u4e2a\u4e0d\u7b49\u5f0f\u53d6\u7b49\u53f7\u7684\u70b9\uff1bn\u7ef4\uff1an\u4e2a\u4e0d\u7b49\u5f0f\u53d6\u7b49\u53f7\u7684\u70b9\u3002\u53ef\u80fd\u51fa\u73b0\u5728\u53ef\u89e3\u7a7a\u95f4\u5916\uff0c\u53bb\u9664\u5373\u53ef
                                            \u90bb\u5c45\uff1an\u7ef4\u60c5\u51b5\u4e0b\uff0c\u4e24\u4e2a\u9876\u70b9\u4e2dn\u4e2a\u9876\u70b9\u53ea\u67091\u4e2a\u4e0d\u540c\u3002\u4f46\u662f\u4e00\u4e2a\u9876\u70b9\u53ef\u80fd\u6709n+1\u4e2a\u7b49\u5f0f\u53d6\u7b49\uff0c\u5f15\u53d1\u201c\u9000\u5316\u201d\u95ee\u9898<\/p>\n\n\n\n
                                            \u6574\u6570\u7ebf\u6027\u89c4\u5212<\/h3>\n\n\n\n
                                            \u5982\u679c\u9876\u70b9\u5750\u6807\u4e0d\u662f\u6574\u6570\uff08\u5305\u62ec\u4f7f\u7528\u53d8\u6362\u4e4b\u540e\uff09\uff0c\u800c\u6211\u4eec\u4f9d\u7136\u8981\u6c42\u627e\u5230\u6700\u4f18\u7684\u6574\u6570\u89e3\uff0c\u6ca1\u6709\u591a\u9879\u5f0f\u65f6\u95f4\u7b97\u6cd5<\/p>\n\n\n\n
                                            \u5bf9\u5076\u95ee\u9898<\/h3>\n\n\n\n
                                            \u6ce8\u610fmaxmize\u2192minimize<\/p>\n\n\n\n
                                            \n
                                            \n
                                            \u539f\u95ee\u9898\uff1a<\/p>\n\n\n\n
                                            \"$\begin{array}{lr}& maxmize\quad 2x_1+3x_2\\& s.t.\quad 4x_1+8x_2\leq 12\\& 2x_1+x_2\leq 3\\& 3x_1+2x_2\leq 4\\& x_i\geq 0\\\end{array}$\"<\/div><\/p>\n<\/div>\n\n\n\n
                                            \n
                                            \u4ee4\uff1a<\/p>\n\n\n\n
                                            \"$z=2x_1+3x_2\\\leq (4y_1+2y_2+3y_3)x_1+(8y_1+y_2+2y_3)x_2\\\leq 12y_1+3y_2+4y_3$\"<\/div><\/p>\n\n\n\n
                                            \u4e0d\u7b49\u53f7\u5728<\/p>\n\n\n\n
                                            \"$\begin{array}{lr}& 4y_1+2y_2+3y_3\geq 2\\& 8y_1+y_2+2y_3\geq 3\end{array}$\"<\/div>
                                            \u65f6\u6ee1\u8db3<\/p>\n<\/div>\n\n\n\n
                                            \n
                                            \u5bf9\u5076\u95ee\u9898\uff1a<\/p>\n\n\n\n
                                            \"$\begin{array}{lr}& minimize\quad 12y_1+3y_2+4y_3\\& s.t.\quad 4y_1+2y_2+3y_3\geq 2\\&8y_1+y_2+2y_3\geq 3\\& y_i\geq 0\\\end{array}$\"<\/div><\/p>\n<\/div>\n<\/div>\n\n\n\n
                                            \n
                                            \n
                                            \u539f\u95ee\u9898\uff1a<\/p>\n\n\n\n
                                            \"$\begin{array}{lr}& maxmize\quad 6x_1-4x_3-1\\& s.t.\quad 3x_1-x_2\leq 1\\& 4x_2-x_3\leq 2\\& x_i\geq 0\\\end{array}$\"<\/div><\/p>\n<\/div>\n\n\n\n
                                            \n
                                            \u4ee4\uff1a<\/p>\n\n\n\n
                                            \"$z=6x_1-4x_3-1\\\leq (3y_1)x_1+(-y_1+4y_2)x_2+(-y_2)x_3-1\\\leq y_1+2y_2-1$\"<\/div><\/p>\n\n\n\n
                                            \u4e0d\u7b49\u53f7\u5728<\/p>\n\n\n\n
                                            \"$\begin{array}{lr}& 3y_1\geq 6\\& -y_1+4y_2\geq 0\\& -y_2\geq -4\\\end{array}$\"<\/div>
                                            \u65f6\u6ee1\u8db3<\/p>\n<\/div>\n\n\n\n
                                            \n
                                            \u5bf9\u5076\u95ee\u9898\uff1a<\/p>\n\n\n\n
                                            \"$\begin{array}{lr}& minimize\quad y_1+2y_2-1\\& s.t.\quad 3y_1\geq 6\\& -y_1+4y_2\geq 0\\& -y_2\geq -4\\& y_i\geq 0\\\end{array}$\"<\/div><\/p>\n<\/div>\n<\/div>\n\n\n\n
                                            \n
                                            Theorem\uff1a\u5982\u679c\u539f\u7ebf\u6027\u89c4\u5212\u6709\u6709\u754c\uff08bounded\uff09\u6700\u4f18\u503c\uff0c\u90a3\u4e48\u5bf9\u5076\u95ee\u9898\u4e5f\u6709\u6709\u754c\u6700\u4f18\u503c\uff0c\u4e14\u4e24\u4e2a\u6700\u4f18\u503c\u91cd\u5408<\/p>\n<\/blockquote>\n\n\n\n
                                            \u5bf9\u5076\u7684\u5e94\u7528\uff1a
                                            1.\u5c06\u4e24\u4e2a\u4e0d\u76f8\u5173\u7684\u95ee\u9898\u8054\u7cfb\u8d77\u6765\uff08\u6700\u5927\u6d41\u2192\u6700\u5c0f\u5272\uff09
                                            2.\u5047\u8bbe\u6211\u4eec\u901a\u8fc7\u5355\u7eaf\u5f62\u6cd5\u5f97\u5230\u4e86\u4e00\u4e2a\u9876\u70b9\uff0c\u6211\u4eec\u5982\u4f55\u786e\u5b9a<\/p>\n\n\n\n
                                            \u7ebf\u6027\u89c4\u5212\u6807\u51c6\u578b<\/h3>\n\n\n\n
                                            \u7ebf\u6027\u89c4\u5212\u95ee\u9898\u591a\u79cd\u591a\u6837\uff1amax\/min\uff1b\u7b49\u5f0f\/\u4e0d\u7b49\u5f0f\uff1b\u53d8\u91cf\u975e\u8d1f\/\u4efb\u610f\uff1b\u5e0c\u671b\u8f6c\u6362\u6210\u4e00\u79cd\u6807\u51c6\u683c\u5f0f\uff0c\u7136\u540e\u7528\u4e00\u79cd\u65b9\u5f0f\u89e3\u51b3<\/p>\n\n\n\n
                                            \u8f6c\u6362\u65b9\u5f0f\uff1a<\/p>\n\n\n\n
                                              \n
                                            • max\u2194min\uff1a*-1<\/li>\n\n\n\n
                                            • \u7b49\u5f0fax=b\u2192\u4e0d\u7b49\u5f0fax\u2265b\uff0cax\u2264b\uff1b\u4e0d\u7b49\u5f0fax\uff1eb\u2192\u7b49\u5f0fax+s=b\uff1bs\uff1e0<\/li>\n\n\n\n
                                            • \u8d1f\u6570\u2192\u6b63\u6570\uff1a\u5b9a\u4e49x+<\/sup>\u548cx–<\/sup>\uff0cx+<\/sup>\u548cx–<\/sup>\u5747\u975e\u8d1f\uff0cx\u66ff\u6362\u6210x+<\/sup>-x–<\/sup><\/li>\n<\/ul>\n\n\n\n
                                              \u5b9a\u4e49\u7ebf\u6027\u89c4\u5212\u6807\u51c6\u578b\uff1a<\/p>\n\n\n\n
                                                \n
                                              • \u53d8\u91cf\u975e\u8d1f<\/li>\n\n\n\n
                                              • \u7b49\u5f0f<\/li>\n\n\n\n
                                              • minimize<\/li>\n<\/ul>\n\n\n\n
                                                \"\"<\/div><\/figure>\n\n\n\n
                                                \u5355\u7eaf\u5f62\u6cd5\u7b97\u6cd5Simplex Algorithm<\/h3>\n\n\n\n
                                                Simplex\uff1av\u662f\u4e00\u4e2a\u9876\u70b9\uff0cv\u2018\u662f\u5176\u90bb\u5c45\uff0cv\u2019\u6709\u66f4\u597d\u7684value\uff0c\u5219\u4ee4v=v\u2018<\/p>\n\n\n\n
                                                \u9876\u70b9\uff1a\u67d0\u4e9b\u8d85\u5e73\u9762\uff08\u7ebf\u3001\u9762\u3001\u8d85\u5e73\u9762\uff09\u76f8\u4ea4\u7684\u552f\u4e00\u7684\u70b9\uff08\u907f\u514d\u9762\u9762\u6210\u7ebf\uff0c\u6240\u4ee5\u5f3a\u8c03\u552f\u4e00\uff09
                                                \u9009\u53d6\u4e00\u4e9b\u4e0d\u7b49\u5f0f\uff0c\u5982\u679c\u6070\u6709\u4e00\u4e2a\u70b9\u4f7f\u8fd9\u4e9b\u4e0d\u7b49\u5f0f\u53d6\u7b49\uff0c\u90a3\u4e48\u8fd9\u4e2a\u70b9\u662f\u9876\u70b9<\/p>\n\n\n\n
                                                \u90bb\u5c45\uff1an\u7ef4\u7a7a\u95f4\u4e2d\uff0c\u5982\u679c\u4e24\u4e2a\u9876\u70b9\u53d6\u7b49\u7684\u4e0d\u7b49\u5f0f\u4e2d\u6709n-1\u4e2a\u76f8\u540c\uff0c\u5219\u4e24\u70b9\u4e3a\u90bb\u5c45<\/p>\n\n\n\n
                                                \u7b97\u6cd5\uff1a<\/p>\n\n\n\n
                                                  \n
                                                • \u5728\u6bcf\u6b21\u8fed\u4ee3\u4e2d
                                                    \n
                                                  • \u4ece\u539f\u70b9\u5f00\u59cb\uff0c\u68c0\u67e5\u90bb\u5c45\u662f\u5426\u6709\u66f4\u4f18\u7684\u503c\uff0c\u5982\u679c\u81ea\u5df1\u662f\u6700\u4f18\u7684\uff0c\u5219\u505c\u6b62<\/li>\n
                                                  • \u5982\u679c\u6709\u5219\u79fb\u52a8\u8fc7\u53bb<\/li>\n<\/ul><\/li>\n\n\n\n
                                                  • \u628a\u5750\u6807\u7cfb\u539f\u70b9\u79fb\u5230\u5f53\u524d\u70b9<\/li>\n<\/ul>\n\n\n\n
                                                    \u4e3a\u4ec0\u4e48\u6bcf\u6b21\u90fd\u8981\u4ece\u539f\u70b9\u5f00\u59cb\uff1f<\/p>\n\n\n\n
                                                      \n
                                                    • \u5982\u679c\u76ee\u6807\u51fd\u6570\u4e2d\u6240\u6709\u53d8\u91cf\u7684\u7cfb\u6570\u90fd\u662f\u8d1f\u7684\uff08\u5f53\u6211\u4eec\u4e00\u76f4\u79fb\u52a8\u5230\u539f\u70b9\uff0c\u6700\u7ec8\u76ee\u6807\u51fd\u6570\u4f1a\u53d8\u6210\u8fd9\u6837\uff09\uff0c\u90a3\u4e48\u539f\u70b9\u5c31\u662f\u6700\u4f18\u503c\u3002\uff08\u5982maxmize -x1<\/sub>-3x2<\/sub>+5\uff0c\u6700\u4f18\u503c\u5c31\u662f5\uff09<\/li>\n\n\n\n
                                                    • \u5f53\u53d8\u91cf\u90fd\u4e3a0\u65f6\uff0c\u6211\u4eec\u53ef\u4ee5\u5f88\u65b9\u4fbf\u5730\u627e\u5230\u90bb\u5c45\uff08\u5982x1<\/sub>+2x2<\/sub>\u22644\uff0c\u5219\u90bb\u5c45\u4e3a(4,0) ,(0,2)\uff09<\/li>\n<\/ul>\n\n\n\n
                                                      \u5bf9\u7ebf\u6027\u89c4\u5212\u8fdb\u884c\u5750\u6807\u53d8\u6362<\/h4>\n\n\n\n
                                                      \u4ece(0,0)\u5f00\u59cb\u589e\u52a0x2<\/sub>\uff0c\u6211\u4eec\u53d1\u73b0\u4e0b\u4e00\u4e2a\u89e6\u78b0\u5230\u7684\u4e0d\u7b49\u5f0f\u662f-x1<\/sub>+x2<\/sub>\u22643\uff0c\u5373\u627e\u5230\u4e00\u4e2a\u90bb\u5c45(0,3)
                                                      \u4ee4y1<\/sub>=x1<\/sub>\uff0cy2<\/sub>=3+x1<\/sub>-x2<\/sub>\u22650\uff08\u6ce8\u610f\u65b0\u53d8\u91cf\u4e00\u5b9a\u8981\u22650\uff09\uff0c\u53ef\u4ee5\u5c06\u5de6\u8fb9\u7684\u539f\u95ee\u9898\u901a\u8fc7\u5750\u6807\u53d8\u6362\u53d8\u4e3a\u53f3\u8fb9\u7684\u65b0\u95ee\u9898<\/p>\n\n\n\n
                                                      \"\"<\/div><\/figure>\n\n\n\n
                                                      \u91cd\u590d\u4e0a\u9762\u7684\u6b65\u9aa4\uff0c\u6211\u4eec\u589e\u52a0y1<\/sub>\uff0c\u5f97\u5230\u65b0\u90bb\u5c45(1,0)
                                                      \u4ee4z1<\/sub>=3-3y1<\/sub>+2y2<\/sub>\uff0cz2<\/sub>=y2<\/sub>\uff0c\u518d\u5f97\u5230\u65b0\u95ee\u9898\uff0c\u53ef\u4ee5\u53d1\u73b0\u76ee\u6807\u51fd\u6570\u4e2d\u7cfb\u6570\u90fd\u4e3a\u8d1f\uff0c\u6700\u4f18\u503c\u662f22<\/p>\n\n\n\n
                                                      \"\"<\/div><\/figure>\n\n\n\n
                                                      \u5982\u4f55\u627e\u5230\u7b2c\u4e00\u4e2a\u9876\u70b9<\/h4>\n\n\n\n
                                                      \"\"<\/div><\/figure>\n\n\n\n
                                                      \u6211\u4eec\u53ef\u4ee5\u901a\u8fc7\u4e0a\u9762\u8fd9\u79cd\u65b9\u5f0f\uff0c\u5728\u539f\u95ee\u9898\u57fa\u7840\u4e0a\u627e\u5230\u4e00\u4e2a\u65b0\u95ee\u9898\uff0c\u65b0\u95ee\u9898\u5f88\u5bb9\u6613\u627e\u5230\u4e00\u4e2a\u9876\u70b9\uff1axi<\/sub>=0;sj<\/sub>=0;z1<\/sub>=200,z2<\/sub>=300,z3<\/sub>=400
                                                      \u5728\u8fd9\u4e2a\u9876\u70b9\u57fa\u7840\u4e0a\u89e3\u51fa\u7ebf\u6027\u89c4\u5212\uff0c\u6700\u4f18\u503c\u663e\u7136\u4f1a\u5728zk<\/sub>=0\u65f6\u53d6\u5230\uff08\u5982\u679c\u53d6\u4e0d\u5230\u663e\u7136\u539f\u95ee\u9898infeasible\uff09\uff0c\u90a3\u4e48\u5c31\u4f1a\u5f97\u5230\u4e00\u4e2a\u539f\u95ee\u9898\u7684\u9876\u70b9<\/p>\n\n\n\n
                                                      \u89e3\u51b3\u95ee\u9898<\/h4>\n\n\n\n
                                                      \u9000\u5316\u95ee\u9898<\/strong><\/p>\n\n\n\n
                                                      \u95ee\u9898\u63cf\u8ff0\uff1an\u7ef4\u7a7a\u95f4\uff0c\u540c\u4e00\u4e2a\u70b9\u6709\u5927\u4e8en\u4e2a\u4e0d\u7b49\u5f0f\u53d6\u7b49\u53f7\uff0c\u4f1a\u5bfc\u81f4\u9876\u70b9\u7684\u90bb\u5c45\u662f\u5176\u81ea\u5df1<\/p>\n\n\n\n
                                                      \u89e3\u51b3\u65b9\u6cd5\uff1a\u52a0\u4e2a\u5c0f\u6270\u52a8<\/p>\n\n\n\n
                                                      Unbounded\u95ee\u9898<\/strong><\/p>\n\n\n\n
                                                      \u95ee\u9898\u63cf\u8ff0\uff1a\u8fdb\u884c\u5750\u6807\u53d8\u6362\u65f6\uff0c\u53d1\u73b0\u6c38\u8fdc\u4e0d\u4f1a\u78b0\u5230\u4e0d\u7b49\u5f0f\uff0c\u5bfc\u81f4\u503c\u4e00\u76f4\u589e\u52a0<\/p>\n\n\n\n
                                                      \u89e3\u51b3\u65b9\u6cd5\uff1a\u8bbe\u5b9a\u4e00\u4e2amax\u503c\uff0c\u8d8a\u754c\u62a5\u9519<\/p>\n\n\n\n
                                                      \u65f6\u95f4\u590d\u6742\u5ea6<\/h4>\n\n\n\n
                                                      \u7ed9\u5b9an\u4e2a\u53d8\u91cf\uff0cm\u4e2a\u7ea6\u675f\uff08\u4e0d\u5305\u542bxi<\/sub>\u22650\uff09\uff0c\u6700\u5dee\u60c5\u51b5\u4e0b\u6211\u4eec\u9700\u8981\u8bbf\u95ee\u6bcf\u4e2a\u9876\u70b9\uff0c\u9876\u70b9\u4e2a\u6570\u4e3a<\/p>\n\n\n\n
                                                      \"$C_{m+n}^{n}= \left( \begin{array}{lr}& m+n\\ & n\\\end{array} \right)$\"<\/div><\/p>\n\n\n\n
                                                      \u662f\u6307\u6570\u7ea7\u7684\u7b97\u6cd5\uff0c\u4f46\u662f\u5728\u5b9e\u9645\u8868\u73b0\u4e0a\u5f88\u597d<\/p>\n\n\n\n
                                                      \u6700\u77ed\u8def\u5f84<\/h3>\n\n\n\n
                                                      Dijkstra\u7b97\u6cd5\u7684\u7ebf\u6027\u89c4\u5212\u5f62\u5f0f<\/h4>\n\n\n\n
                                                      \"$\left.\begin{array}{lr}& max \quad d_t\\&d_v\leq d_u+w(u,v) \\&d_s=0\\&d_i\geq 0\\\end{arrry}\right.\begin{array}{lr}& \\&(u,v) \in E\\&\\&v \in V\\\end{arrry}$\"<\/div><\/p>\n\n\n\n
                                                      \u8fb9\u754c\u6536\u7f29\uff0c\u589e\u52a0dt<\/sub>\u6765\u627e\u5230\u8fb9\u754c<\/p>\n\n\n\n
                                                      \u4ece\u6700\u77ed\u8def\u5f84\u95ee\u9898\u51fa\u53d1<\/h4>\n\n\n\n
                                                      \u5c06\u56fe\u5272\u6210S\u3001T\u4e24\u90e8\u5206\uff0c\u5176\u4e2ds\u70b9\u5728S\uff0ct\u70b9\u5728T\uff1b\u5c06\u8fd9\u4e2a\u5272\u5199\u4f5cS\uff0c\u03b4(S)\u662fS\u7ecf\u8fc7\u7684\u6240\u6709\u8fb9\u7684\u96c6\u5408\uff1b\u6240\u6709\u7b26\u5408\u6761\u4ef6\u7684\u5272S\u7684\u96c6\u5408\u5199\u4f5cC\u3002\u6700\u77ed\u8def\u5f84\u95ee\u9898\u53ef\u4ee5\u7528\u4e0b\u9762\u7684\u6574\u6570\u7ebf\u6027\u89c4\u5212\u95ee\u9898\u63cf\u8ff0<\/p>\n\n\n\n
                                                      \"$\left.\begin{array}{lr}& min \quad \sum_{e\in E}w_{e}x_e\\&\sum_{e\in \delta (S)}x_e\geq 1\\&x_e \in \{0,1\}\\\end{arrry}\right.\begin{array}{lr}& \\&S \in C\\&e \in E\\\end{arrry}$\"<\/div><\/p>\n\n\n\n
                                                      \u7b2c\u4e00\u4e2a\u4e0d\u7b49\u5f0f\u4fdd\u8bc1\u4e86\u5728\u53d6\u4efb\u610f\u4e00\u4e2a\u5272\u7684\u65f6\u5019\uff0c\u90fd\u4f1a\u6709\u81f3\u5c11\u4e00\u6761\u8fb9\u88ab\u7a7f\u8fc7\uff0c\u4e5f\u5c31\u4fdd\u8bc1\u4e86\u8def\u5f84\u8fde\u7eed
                                                      \u76ee\u6807\u51fd\u6570\u4fdd\u8bc1\u4e86dist\u6700\u5c0f<\/p>\n\n\n\n
                                                      \u4f18\u5316\uff1a<\/p>\n\n\n\n
                                                        \n
                                                      • \u5c06xe<\/sub>\u2208{0,1}\u4fee\u6539\u4e3a0\u2264xe<\/sub>\u22641\uff1a\u56e0\u4e3a\u6700\u4f18\u503c\u90fd\u5728\u6574\u6570\u70b9\uff0c\u6240\u4ee5\u53ef\u4ee5<\/li>\n\n\n\n
                                                      • \u8fdb\u4e00\u6b65\uff0c\u76f4\u63a50\u2264xe<\/sub>\uff1a\u56e0\u4e3amin\u4fdd\u8bc1\u4e86\u6700\u4f18\u503c\u9760\u8fd1\u539f\u70b9\uff0c\u6240\u4ee5\u53ef\u4ee5\u4e0d\u7528\u22641<\/li>\n<\/ul>\n\n\n\n
                                                        \u6700\u7ec8\u5f62\u5f0f\uff1a<\/p>\n\n\n\n
                                                        \"$\left.\begin{array}{lr}& min \quad \sum_{e\in E}w_{e}x_e\\&\sum_{e\in \delta (S)}x_e\geq 1\\&x_e \geq 0\\\end{arrry}\right.\begin{array}{lr}& \\&S \in C\\&e \in E\\\end{arrry}$\"<\/div><\/p>\n\n\n\n
                                                        \u53d6\u5bf9\u5076\uff1a<\/p>\n\n\n\n
                                                        \"$\left.\begin{array}{lr}& max \quad \sum_{S\in C}y_S\\&\sum_{S\in C, e\in \delta (S)}y_S\leq w_e\\&y_S \geq 0\\\end{arrry}\right.\begin{array}{lr}& \\&e \in E\\&S \in C\\\end{arrry}$\"<\/div><\/p>\n\n\n\n
                                                        \u5bf9\u5e94Moat\uff08\u62a4\u57ce\u6cb3\uff09\u95ee\u9898\uff1a\u5728\u4eces\u5230t\u95f4\u7b51\u9020\u62a4\u57ce\u6cb3\uff0c\u4f7f\u5f97\u62a4\u57ce\u6cb3\u5bbd\u5ea6\u6700\u5bbd<\/p>\n\n\n\n
                                                        \"\"<\/div><\/figure>\n\n\n\n
                                                        \u6700\u5927\u6d41\u6700\u5c0f\u5272\u95ee\u9898<\/h3>\n\n\n\n
                                                        \u6700\u5927\u6d41\u95ee\u9898\u53ef\u4ee5\u7528\u4e0b\u9762\u7684\u7ebf\u6027\u89c4\u5212\u95ee\u9898\u63cf\u8ff0\uff1a<\/p>\n\n\n\n
                                                        \u5047\u5b9a\u8fb9e(i,j)\u7684\u6700\u5927\u6d41\u91cf\u4e3acij<\/sub>\uff0c\u5b9e\u9645\u6d41\u91cf\u4e3afij<\/sub><\/p>\n\n\n\n
                                                        \n
                                                        \n
                                                        \u4e00\u822c\u5f62\u5f0f\uff1a\u6700\u5927\u5316\u6d41\uff0c\u6d41\u91cf\u5c0f\u4e8e\u6700\u5927\u6d41\u91cf\uff0c\u6d41\u5165\u7b49\u4e8e\u6d41\u51fa<\/p>\n\n\n\n
                                                        \"$\left.\begin{array}{lr}& max \quad f_{st}\\&f_{ij}\leq c_{ij}\\&\sum_{(w,i)\in E}f_{wi}=\sum_{(i,z)\in E}f_{iz}\\& f_{ij}\geq 0\\\end{arrry}\right.\begin{array}{lr}& \\&(i,j) \in E\\&i \in V\\& (i,j)\in E \\\end{arrry}$\"<\/div><\/p>\n<\/div>\n\n\n\n
                                                        \n
                                                        \u53e6\u4e00\u79cd\u5f62\u5f0f\uff1a\u52a0\u4e00\u6761t\u5230s\u7684\u8fb9\uff0c\u5bb9\u91cf\u221e\uff0c\u540c\u6837max\u6d41\u91cf\uff0c\u53ef\u4ee5\u5c06=\u6539\u4e3a\u2264\uff08\u65b9\u4fbf\u6c42\u5bf9\u5076\uff09\uff0c\u56e0\u4e3a\u662f\u4e00\u4e2a\u73af\uff0cf1<\/sub>\u2264f2<\/sub>\u2264…\u2264fn<\/sub>\u2264f1<\/sub>\uff0c\u6ce8\u610fE\u5305\u542be(t,s)<\/p>\n\n\n\n
                                                        \"$\left.\begin{array}{lr}& max \quad f_{ts}\\&f_{ij}\leq c_{ij}\\&\sum_{(w,i)\in E}f_{wi}-\sum_{(i,z)\in E}f_{iz}\leq 0\\& f_{ij}\geq 0\\\end{arrry}\right.\begin{array}{lr}& \\&(i,j) \in E\\&I \in V\\& (i,j)\in E \\\end{arrry}$\"<\/div><\/p>\n<\/div>\n<\/div>\n\n\n\n
                                                        \u96c6\u5408\u8986\u76d6<\/h3>\n\n\n\n
                                                        NP\u95ee\u9898<\/h2>\n\n\n\n
                                                        \u89c4\u7ea6<\/h3>\n\n\n\n
                                                        \"\"<\/div><\/figure>\n\n\n\n
                                                        \u5c06A\u89c4\u7ea6\u5230B\u7684\u4e00\u4e2a\u7279\u6b8a\u60c5\u51b5\uff0c\u7136\u540e\u89e3\u51b3B\uff0c\u6211\u4eec\u4e5f\u5c31\u5f97\u5230\u4e86\u4e00\u4e2aA\u7684\u89e3
                                                        \u6ce8\u610f\u662fA\u6bd4B\u7b80\u5355<\/strong>\uff08\u81f3\u5c11\u5728\u63cf\u8ff0\u4e0a\u662f\u7b80\u5355\u7684\uff09<\/p>\n\n\n\n
                                                        \u89c4\u7ea6\u7684\u4e09\u4e2a\u7528\u6cd5\uff1a\u5fc5\u8003\u5fc5\u51fa\u9519<\/strong><\/p>\n\n\n\n
                                                          \n
                                                        • \u89e3\u51b3\uff1a\u5c06\u4e00\u4e2a\u672a\u77e5\u95ee\u9898\u5f52\u7ea6\u5230\u4e00\u4e2a\u5df2\u77e5\u95ee\u9898\uff0c\u5df2\u77e5\u95ee\u9898\u6709\u4e00\u4e2a\u7b97\u6cd5\uff0c\u5219\u6211\u4eec\u5f97\u5230\u4e00\u4e2a\u672a\u77e5\u95ee\u9898\u7684\u7b97\u6cd5<\/li>\n\n\n\n
                                                        • \u8bc1\u660e\uff1a\u5c06\u4e00\u4e2a\u5df2\u77e5\u95ee\u9898\u5f52\u7ea6\u5230\u4e00\u4e2a\u672a\u77e5\u95ee\u9898\uff0c\u6211\u4eec\u53ef\u4ee5\u8bc1\u660e<\/strong>\u672a\u77e5\u95ee\u9898\u6bd4\u5df2\u77e5\u95ee\u9898\u96be<\/li>\n\n\n\n
                                                        • \u8bc4\u4f30\uff1a\u5c06\u4e00\u4e2a\u672a\u77e5\u95ee\u9898\u5f52\u7ea6\u5230\u4e00\u4e2a\u5df2\u77e5\u95ee\u9898\uff0c\u6211\u4eec\u53ef\u4ee5\u4f30\u8ba1<\/strong>\u672a\u77e5\u95ee\u9898\u7684\u96be\u5ea6<\/s><\/li>\n<\/ul>\n\n\n\n
                                                          \u4e00\u822c\u60c5\u51b5\u4e0b\uff0c\u8bc1\u660e\u548c\u8bc4\u4f30\u53ea\u53d6\u5176\u4e00\uff0c\u5373\u4e24\u4e2a\u95ee\u9898\u65e0\u6cd5\u4e92\u76f8\u89c4\u7ea6\uff0c\u5426\u5219\u5c31\u662f\u4e00\u4e2a\u95ee\u9898<\/p>\n\n\n\n
                                                          \u5224\u5b9a\u3001\u641c\u7d22\u3001\u4f18\u5316\u95ee\u9898<\/h4>\n\n\n\n
                                                          \u4e00\u4e2a\u95ee\u9898\u6709\u5224\u5b9a\u3001\u641c\u7d22\u3001\u4f18\u5316\u4e09\u4e2a\u7248\u672c\uff0c\u4e09\u4e2a\u7248\u672c\u53ef\u4ee5\u5728\u591a\u9879\u5f0f\u65f6\u95f4\u5185\u4e92\u76f8\u89c4\u7ea6<\/p>\n\n\n\n
                                                            \n
                                                          • \u5224\u5b9a\u95ee\u9898\u56de\u7b54yes\/no\uff08\u662f\u5426\u5b58\u5728\u4e00\u4e2a\u2264k\u7684\u9876\u70b9\u8986\u76d6\uff09<\/li>\n\n\n\n
                                                          • \u641c\u7d22\u95ee\u9898\u56de\u7b54\u4e00\u4e2a\u89e3\uff08\u662f\u5426\u5b58\u5728\u4e00\u4e2a=k\u7684\u9876\u70b9\u8986\u76d6\uff09<\/li>\n\n\n\n
                                                          • \u4f18\u5316\u95ee\u9898\u56de\u7b54\u4e00\u4e2a\u6700\u4f18\u89e3\uff08\u627e\u5230\u4e00\u4e2a\u6700\u5c0f\u7684\u9876\u70b9\u8986\u76d6\uff09<\/li>\n<\/ul>\n\n\n\n
                                                            \u6700\u5927\u72ec\u7acb\u96c6\u3001\u6700\u5c0f\u9876\u70b9\u8986\u76d6\u3001\u6700\u5927\u56e2<\/h4>\n\n\n\n
                                                            \u95ee\u9898\u63cf\u8ff0\uff1a<\/p>\n\n\n\n
                                                            \u6700\u5927\u72ec\u7acb\u96c6\uff1a\u5728\u56fe\u4e2d\u627e\u5230\u4e00\u7ec4\u9876\u70b9\uff0c\u4e24\u4e24\u95f4\u65e0\u8fb9\uff0c\u4f7f\u6b64\u72ec\u7acb\u96c6\u6700\u5927\u5316
                                                            \u6700\u5c0f\u9876\u70b9\u8986\u76d6\uff1a\u5728\u56fe\u4e2d\u627e\u5230\u4e00\u7ec4\u9876\u70b9\uff0c\u4f7f\u5f97\u6bcf\u6761\u8fb9\u90fd\u81f3\u5c11\u67091\u4e2a\u9876\u70b9\u88ab\u8986\u76d6\uff0c\u4f7f\u6b64\u9876\u70b9\u8986\u76d6\u6700\u5c0f\u5316
                                                            \u6700\u5927\u56e2\uff1a\u5728\u56fe\u4e2d\u627e\u5230\u4e00\u7ec4\u9876\u70b9\uff0c\u4f7f\u5f97\u9876\u70b9\u95f4\u4e24\u4e24\u6709\u8fb9\uff08\u533a\u5206\u5f3a\u8fde\u901a\u5206\u91cfSCC\uff0cSCC\u53ea\u8981\u6c42\u4e24\u4e24\u95f4\u6709\u8def\u5f84\uff09\uff0c\u4f7f\u6b64\u96c6\u5408\u6700\u5927\u5316<\/p>\n\n\n\n
                                                            \u72ec\u7acb\u96c6\u21d4\u56e2\uff1a\u539f\u56fe\u4e2d\u4e24\u4e24\u65e0\u8fb9\u7684\u72ec\u7acb\u96c6\uff0c\u5bf9\u5e94\u8865\u56fe\u4e2d\u4e24\u4e24\u6709\u8fb9\u7684\u56e2
                                                            \u72ec\u7acb\u96c6\u21d4\u9876\u70b9\u8986\u76d6\uff1a\u5047\u8bbe\u6700\u5927\u72ec\u7acb\u96c6S\uff0c\u5219V\\S\u4e3a\u6700\u5c0f\u9876\u70b9\u8986\u76d6\uff08V\\S\u4e2d\u6240\u6709\u9876\u70b9\u90fd\u4e0eS\u76f8\u8fde\uff09<\/p>\n\n\n\n
                                                            \u4e09\u4e2a\u95ee\u9898\u5b9e\u9645\u4e0a\u662f\u4e00\u4e2a\u95ee\u9898\uff0c\u53ef\u4ee5\u4e92\u76f8\u89c4\u7ea6<\/p>\n\n\n\n
                                                            \u96c6\u5408\u8986\u76d6\u95ee\u9898<\/h4>\n\n\n\n
                                                            \u95ee\u9898\u63cf\u8ff0\uff1a\u8f93\u5165\u96c6\u5408B\uff0c\u548cB\u7684\u4e00\u4e9b\u5b50\u96c6S1,<\/sub>S2<\/sub>…Sm<\/sub>\uff1b\u8f93\u51fa\u9009\u62e9\u7684Si<\/sub>\uff0c\u5176\u5e76\u96c6\u4e3aB\uff0c\u4f7f\u9009\u62e9\u7684Si<\/sub>\u6570\u91cf\u6700\u5c0f<\/p>\n\n\n\n
                                                            \u9876\u70b9\u8986\u76d6\u662f\u4e00\u4e2a\u7279\u6b8a\u7684\u96c6\u5408\u8986\u76d6\uff0c\u5728\u9876\u70b9\u5728\u96c6\u5408\u4e2d\u51fa\u73b0\u4e14\u4ec5\u51fa\u73b02\u6b21\u7684\u60c5\u51b5\u4e0b\u3002\uff08\u5c06\u9876\u70b9\u8986\u76d6\u5f52\u7ea6\u5230\u4e86\u96c6\u5408\u8986\u76d6\u4e0a\uff09<\/p>\n\n\n\n
                                                            \u53ef\u6ee1\u8db3\u6027\u95ee\u9898\u2014\u2014SAT\u95ee\u9898<\/h3>\n\n\n\n
                                                            SAT\u21923-SAT<\/h4>\n\n\n\n
                                                            3-SAT\u95ee\u9898\uff1a\u5728SAT\u95ee\u9898\u7684\u57fa\u7840\u4e0a\uff0c\u6bcf\u4e2a\u8bed\u53e5\u81f3\u591a3\u4e2a\u53d8\u91cf<\/p>\n\n\n\n
                                                            \u6211\u4eec\u53ea\u9700\u8981\u5c06SAT\u4e2d\u53d8\u91cf\u6570\u591a\u4e8e3\u7684\u8bed\u53e5\u62c6\u5206<\/p>\n\n\n\n
                                                            \"$(a_1\vee a_2\vee ...\vee a_k)$\"<\/div><\/p>\n\n\n\n
                                                            \"$(a_1\vee a_2\vee y_1)(\overline{y_1}\vee a_3 \vee y_2)(\overline{y_2}\vee a_4\vee y_3)...(\overline{y_{k-3}}\vee a_{k-1}\vee a_k)$\"<\/div><\/p>\n\n\n\n
                                                            \u4e24\u4e2a\u5f0f\u5b50\u7684\u53ef\u6ee1\u8db3\u6027\u76f8\u540c\uff08\u8bb0\u5f97\u8bc1\u4e24\u8fb9\uff09<\/p>\n\n\n\n
                                                            \u4e3a\u4e86\u5728\u786c\u4ef6\u4e0a\u6c42\u89e33-SAT\u95ee\u9898\uff0c\u6211\u4eec\u9700\u8981\u9650\u5236\u6bcf\u4e2a\u53d8\u91cf\u53ea\u51fa\u73b03\u6b21\u4ee5\u4e0b\uff08\u4ecd\u7136\u662f\u4e00\u4e2a\u56f0\u96be\u95ee\u9898\uff0c\u4f46\u53ef\u4ee5\u7528\u786c\u4ef6\u89e3\u51b3\uff09\u3002\u5982\u679c\u53d8\u91cfx\u51fa\u73b0\u5728\u4e09\u4e2a\u4ee5\u4e0a\u7684\u5b50\u53e5\u4e2d\uff0c\u6211\u4eec\u53ef\u4ee5\u5c06\u5176\u66ff\u6362\u4e3ax1<\/sub>x2<\/sub>…xn<\/sub>\uff0c\u7136\u540e\u6dfb\u52a0\u4e0b\u9762\u7684\u8bed\u53e5\uff0c\u8fd9\u4e2a\u8bed\u53e5\u53ef\u4ee5\u4fdd\u8bc1xi<\/sub>\u7684\u53d6\u503c\u4e00\u81f4<\/p>\n\n\n\n
                                                            \"$(\overline{x_1}\vee x_2)(\overline{x_2}\vee x_3)...(\overline{x_n}\vee x_1)$\"<\/div><\/p>\n\n\n\n
                                                            3-SAT\u2192\u6700\u5927\u72ec\u7acb\u96c6<\/h4>\n\n\n\n
                                                              \n
                                                            • \u5c063-SAT\u4e2d\u7684\u6bcf\u4e2a\u8bed\u53e5\u5199\u6210\u4e00\u4e2a\u4e09\u89d2\u5f62\uff0c\u9876\u70b9\u4e24\u4e24\u76f8\u8fde<\/li>\n\n\n\n
                                                            • \u5c06\u4e0d\u540c\u4e09\u89d2\u5f62\u95f4\uff0c\u5c06\u4e00\u4e2a\u503c\u4e0e\u5176\u76f8\u53cd\u53d6\u503c\u76f8\u8fde<\/li>\n\n\n\n
                                                            • \u5047\u8bbe\u539f\u6765\u6709m\u4e2a\u5b50\u53e5\uff0c\u5219\u5728\u56fe\u4e0a\u627e\u4e00\u4e2a\u5927\u5c0f\u4e3am\u7684\u72ec\u7acb\u96c6<\/li>\n<\/ul>\n\n\n\n
                                                              \"\"<\/div><\/figure>\n\n\n\n
                                                              \"\"<\/div><\/figure>\n\n\n\n
                                                              \u72ec\u7acb\u96c6\u4e2d\u7684\u6bcf\u4e2a\u70b9\uff0c\u90fd\u610f\u5473\u7740\u4e00\u6761\u8bed\u53e5\u4e3a\u771f\uff0c\u800c\u6211\u4eec\u53c8\u907f\u514d\u4e86\u4e00\u4e2a\u503c\u4e0e\u5176\u76f8\u53cd\u7684\u53d6\u503c\u540c\u65f6\u88ab\u9009\u53d6<\/p>\n\n\n\n
                                                              3-SAT\u2192\u6709\u5411\u6c49\u5bc6\u5c14\u987f\u73af<\/h4>\n\n\n\n
                                                              \u4f7f\u7528\u6bcf\u4e00\u884c\u4ee3\u88683-SAT\u95ee\u9898\u4e2d\u7684\u6bcf\u4e2a\u53d8\u91cf\uff0c\u4f7f\u7528\u6c49\u5bc6\u5c14\u987f\u73af\u7684\u65b9\u5411\u4ee3\u8868\u53d6\u503c\uff0c\u5982\u4e0b\u56fe\u4ee3\u8868\u53d6\u503c\u4e3aFFT<\/p>\n\n\n\n
                                                              \"\"<\/div><\/figure>\n\n\n\n
                                                              \u5bf9\u4e8e\u6bcf\u4e2a\u5b50\u53e5\uff0c\u5982\u679c\u5176\u5305\u542b\u67d0\u884c\u7684\u53d8\u91cf\uff0c\u5219\u5728\u8be5\u884c\u7684\u4e24\u4e2a\u9876\u70b9\u4e4b\u95f4\u6dfb\u52a0\u4e00\u6761\u8def\u5230\u8be5\u5b50\u53e5\uff08\u5355\u5411\uff09,\u5982\u679c\u53d6\u503c\u5f97\u5230\u6ee1\u8db3\uff0c\u6c49\u5bc6\u5c14\u987f\u8def\u5f84\u4f1a\u7ecf\u8fc7\u5b50\u53e5\u7684\u9876\u70b9\uff0c\u5982\u679c\u5168\u90e8\u5b50\u53e5\u7684\u8282\u70b9\u90fd\u88ab\u7ecf\u8fc7\uff0c\u5219\u4ee3\u8868\u90fd\u88ab\u6ee1\u8db3\uff0c\u52193-SAT\u95ee\u9898\u6709\u89e3\u3002<\/p>\n\n\n\n
                                                              \"\"<\/div><\/figure>\n\n\n\n
                                                              \u6709\u5411\u6c49\u5bc6\u5c14\u987f\u73af\u2192\u6c49\u5bc6\u5c14\u987f\u73af<\/h4>\n\n\n\n
                                                              \u6709\u5411\u6c49\u5bc6\u5c14\u987f\u73af<\/strong>\uff1a\u5728\u4e00\u4e2a\u56fe\u4e2d\uff0c\u627e\u5230\u4e00\u4e2a\u73af\u8def\uff0c\u7ecf\u8fc7\u6240\u6709\u9876\u70b9\u4e14\u4ec5\u7ecf\u8fc7\u4e00\u6b21
                                                              \u6c49\u5bc6\u5c14\u987f\u73af<\/strong>\uff1a\u5728\u4e00\u4e2a\u56fe\u4e2d\uff0c\u627e\u5230\u4e00\u4e2a\u73af\u8def\uff0c\u7ecf\u8fc7\u6240\u6709\u9876\u70b9\u4e14\u4ec5\u7ecf\u8fc7\u4e00\u6b21<\/p>\n\n\n\n
                                                              \u89c4\u7ea6\u65b9\u6cd5\uff1a\u5c06\u4e00\u4e2a\u70b9v\u62c6\u5206\u62103\u4e2a\u70b9vin<\/sub>,v,vout<\/sub>\uff0c\u5f3a\u5236\u65e0\u5411\u56fe\u4ea7\u751f\u6709\u5e8f\u7684\u8def\u5f84<\/p>\n\n\n\n
                                                              \"\"<\/div><\/figure>\n\n\n\n
                                                              \u6c49\u5bc6\u5c14\u987f\u73af\u2192\u65c5\u884c\u5546\u4eba\u95ee\u9898TSP<\/h4>\n\n\n\n
                                                              \u65c5\u884c\u5546\u4eba\u95ee\u9898\uff1a\u5982\u4f55\u7528\u6700\u77ed\u7684\u8def\u5f84\u8bbf\u95ee\u6240\u6709\u9876\u70b9\uff08\u8bbf\u95ee\u4e14\u4ec5\u8bbf\u95ee\u4e00\u904d\uff09\u5e76\u8fd4\u56de\u8d77\u70b9\u3002\uff08\u6bcf\u4e24\u4e2a\u9876\u70b9\u95f4\u5747\u5b58\u5728\u8def\u5f84\uff09<\/p>\n\n\n\n
                                                              \u7ed9\u5b9a\u4e00\u4e2a\u6c49\u5bc6\u5c14\u987f\u73af\u95ee\u9898\u7684\u56feG\uff0c\u56e0\u4e3aTSP\u95ee\u9898\u9700\u8981\u5b8c\u5168\u56fe\uff0c\u6240\u4ee5\u5c06\u56fe\u8865\u5168\uff0c\u539f\u6765\u7684\u8fb9\u6743\u503c\u8bbe\u4e3a1\uff0c\u8865\u5145\u7684\u8fb9\u6743\u503c\u8bbe\u4e3a1+k\uff0c\u8dd1\u4e00\u904dTSP\uff0c\u770b\u6743\u503c\u662f\u5426\u4e3a|V|<\/p>\n\n\n\n
                                                              3-SAT\u2192\u5b50\u96c6\u548c\u95ee\u9898<\/h4>\n\n\n\n
                                                              \u5b50\u96c6\u548c\u95ee\u9898<\/strong><\/p>\n\n\n\n
                                                              \u7ed9\u5b9a\u503cw\u548c\u96c6\u5408A\uff0c\u4eceA\u4e2d\u9009\u51fa\u67d0\u4e9b\u503cai<\/sub>\uff0c\u4f7f\u5f97<\/p>\n\n\n\n
                                                              \"$\sum a_i = w$\"<\/div><\/p>\n\n\n\n
                                                              \u89c4\u7ea6\u65b9\u6cd5\uff1a\u524d\u4e09\u4f4d\u4e3a1\uff0c\u4ee3\u8868xi<\/sub>\u6216\u00acxi<\/sub>\u6709\u4e14\u4ec5\u6709\u4e00\u4e2a\u88ab\u6ee1\u8db3\uff1b\u540c\u65f6\u4f1a\u5bfc\u81f4C1<\/sub>-C3<\/sub>\u4ea7\u751f0-3\u7684\u503c\uff08\u5982\u679c\u662f0\u5219\u4e0d\u88ab\u6ee1\u8db3\uff0c\u5927\u4e8e0\u5219\u88ab\u6ee1\u8db3\uff0c\u4e3a\u4e86\u5f97\u5230\u4e00\u4e2a\u786e\u5207\u7684\u503c\uff0c\u5728\u6a2a\u7ebf\u4e0b\u9762\u6dfb\u52a0\u4e86\u4e00\u4e9b\u8f85\u52a9\u503c\uff0c\u53ef\u4ee5\u5c061-3\u7684\u503c\u53d8\u4e3a4\uff0c\u4fbf\u4e8e\u8bbe\u7f6e\u5b50\u96c6\u548c\u7684w\uff09<\/p>\n\n\n\n
                                                              \n
                                                              \n
                                                              \"\"<\/div><\/figure>\n<\/div>\n\n\n\n
                                                              \n
                                                              \"\"<\/div><\/figure>\n<\/div>\n<\/div>\n\n\n\n
                                                              P\u3001NP<\/h3>\n\n\n\n
                                                              P\u95ee\u9898\uff1a<\/strong>\u7ed9\u5b9a\u4e00\u4e2a\u5224\u5b9a\u95ee\u9898\uff0c\u80fd\u5728\u591a\u9879\u5f0f\u65f6\u95f4\u5185\u7ed9\u51fa\u5176\u4e00\u4e2a\u89e3\uff0c\u5982\u679c\u4e0d\u5b58\u5728\u89e3\u4e5f\u5728\u591a\u9879\u5f0f\u65f6\u95f4\u5185\u505c\u6b62
                                                              NP\u95ee\u9898\uff1a<\/strong>\u7ed9\u5b9a\u4e00\u4e2a\u5224\u5b9a\u95ee\u9898\uff0c\u548c\u4e00\u4e2a\u53ef\u80fd\u7684\u89e3\uff0c\u5728\u591a\u9879\u5f0f\u65f6\u95f4\u5185\u53ef\u4ee5\u9a8c\u8bc1\u8fd9\u4e2a\u89e3\u662f\u5426\u4e3a\u8fd9\u4e2a\u95ee\u9898\u7684\u89e3
                                                              EXP\u95ee\u9898\uff1a<\/strong>\u5b58\u5728\u6307\u6570\u7ea7\u7b97\u6cd5\u7684\u5224\u5b9a\u95ee\u9898\uff08\u6bd4\u5982\u8f93\u51fa\u4e00\u4e2a\u96c6\u5408\u7684\u6240\u6709\u5b50\u96c6\uff0c\u4e0d\u53ef\u907f\u514d\u7684\u6307\u6570\u7ea7\u95ee\u9898\uff09
                                                              NPC\u95ee\u9898\uff1a<\/strong>\u6240\u6709NP\u95ee\u9898\u90fd\u80fd\u5728\u591a\u9879\u5f0f\u65f6\u95f4\u5185\u89c4\u7ea6\u5230\u7684\u95ee\u9898\uff08NPC\u95ee\u9898\u5c5e\u4e8eNP\u95ee\u9898\uff0c\u6240\u4ee5NPC\u95ee\u9898\u4e4b\u95f4\u53ef\u4ee5\u4e92\u76f8\u89c4\u7ea6\uff08\u5e76\u4e0d\u76f4\u89c2\uff09\uff0c\u6240\u6709NPC\u95ee\u9898\u662f\u540c\u4e00\u4e2a\u95ee\u9898\uff09
                                                              co<\/strong>–\u95ee\u9898\uff1a<\/strong>\u539f\u95ee\u9898\u56de\u7b54T\/F\uff0c\u8865\u95ee\u9898\u56de\u7b54F\/T\uff08\u662f\u5426\u5b58\u5728\u2192\u662f\u5426\u4e0d\u5b58\u5728\uff09
                                                              co-P\u95ee\u9898<\/strong>\uff1a\u6709\u591a\u9879\u5f0f\u65f6\u95f4\u7b97\u6cd5\uff0cco-P=P
                                                              co-NP\u95ee\u9898\uff1a<\/strong>\u4e0d\u4e00\u5b9a\u6709\u591a\u9879\u5f0f\u65f6\u95f4\u7684\u5224\u5b9a\u65b9\u6cd5\uff08SAT\u95ee\u9898\u7684\u8865\u95ee\u9898\u662f\u5224\u65ad\u4e00\u4e2aCNF\u662f\u5426\u6c38\u4e45\u4e3a\u5047\uff09
                                                              NP-hard\u95ee\u9898\uff1a<\/strong>\u6240\u6709NP\u95ee\u9898\u90fd\u80fd\u89c4\u7ea6\u5230\u7684\u95ee\u9898\uff08NPC=NPH\u2229NP\uff09<\/p>\n\n\n\n
                                                              P\u2286NP\u2286EXP\uff1bP\u4e00\u5b9a\u4e0d\u7b49\u4e8eEXP<\/p>\n\n\n\n
                                                              SAT\u95ee\u9898\u662f\u7b2c\u4e00\u4e2aNPC\u95ee\u9898\uff08\u901a\u8fc7\u7535\u8def\u7f16\u7801\uff09<\/p>\n\n\n\n
                                                              \u8bc1\u660e\u4e00\u4e2a\u95ee\u9898\u662fNPC\u95ee\u9898\uff1a\u9996\u5148\u8bc1\u660e\u662fNP\u95ee\u9898\uff08\u591a\u9879\u5f0f\u65f6\u95f4\u53ef\u9a8c\u8bc1\uff09\uff0c\u518d\u5c06\u4e00\u4e2aNPC\u95ee\u9898\u89c4\u7ea6\u5230\u8fd9\u4e2a\u95ee\u9898<\/p>\n\n\n\n
                                                              \u51e0\u79cd\u731c\u60f3\uff0c\u76ee\u524d\u662f\u53f3\u4e0b\u89d2\uff0c\u5b66\u8005\u503e\u5411\u4e8e\u5de6\u4e0b\u662f\u6b63\u786e\u7684\uff0c\u5de6\u4e0a\u89d2\u662fP=NP<\/p>\n\n\n\n
                                                              \"\"<\/div><\/figure>\n\n\n\n
                                                              \u8fd1\u4f3c\u7b97\u6cd5<\/h2>\n\n\n\n
                                                              \u9876\u70b9\u8986\u76d6<\/h3>\n\n\n\n
                                                              \u9876\u70b9\u8986\u76d6\u3001\u6700\u5927\u5339\u914d<\/h4>\n\n\n\n
                                                              \u6700\u5c0f\u9876\u70b9\u8986\u76d6\uff1a\u5728\u56fe\u4e2d\u627e\u5230\u4e00\u7ec4\u9876\u70b9\uff0c\u4f7f\u5f97\u6bcf\u6761\u8fb9\u90fd\u81f3\u5c11\u67091\u4e2a\u9876\u70b9\u88ab\u8986\u76d6\uff0c\u4f7f\u6b64\u9876\u70b9\u8986\u76d6\u6700\u5c0f\u5316
                                                              \u6700\u5927\u5339\u914d\uff1a\u5728\u56fe\u4e2d\u627e\u51fa\u4e0d\u5305\u542b\u76f8\u540c\u9876\u70b9\u7684n\u4e2a\u8fb9\uff0c\u4f7fn\u6700\u5927<\/p>\n\n\n\n
                                                              \u6700\u5927\u5339\u914d\u7684\u8d2a\u5a6a\u7b97\u6cd5\uff08\u6781\u5927\u5339\u914d\u7b97\u6cd5\uff09\uff1a\u4e0d\u65ad\u5730\u627e\u4e24\u4e2a\u9876\u70b9\u90fd\u672a\u88ab\u8986\u76d6\u7684\u8fb9\uff0c\u5e76\u52a0\u5165\u96c6\u5408
                                                              \u6700\u5c0f\u9876\u70b9\u8986\u76d6\u7684\u8d2a\u5a6a\u7b97\u6cd5\uff1a\u9009\u53d6\u6781\u5927\u5339\u914d\u7684\u8fb9\u7684\u9876\u70b9<\/p>\n\n\n\n
                                                              \u9876\u70b9\u8986\u76d6\u8d2a\u5a6a\u7b97\u6cd5\u7684\u8fd1\u4f3c\u6bd4\uff1a2
                                                              proof\uff1a\u663e\u7136\uff0c\u5bf9\u4e8e\u4efb\u610f\u4e00\u4e2a\u5339\u914d\uff08\u65e0\u8bba\u6700\u5927\u6216\u6781\u5927\uff09\uff0cn\u2264OPT\uff08\u9009\u62e9\u7684n\u6761\u8fb9\u81f3\u5c11\u9700\u8981n\u4e2a\u9876\u70b9\u6765\u8986\u76d6\uff0c\u800c\u6211\u4eec\u81f3\u591a\u9009\u62e9\u4e862n\u4e2a\u9876\u70b9\uff09<\/p>\n\n\n\n
                                                              \u5ea6\u6743\u56fe\u4e0a\u7684\u9876\u70b9\u8986\u76d6<\/h4>\n\n\n\n
                                                              \u95ee\u9898\u63cf\u8ff0\uff1a\u5728\u6700\u5c0f\u9876\u70b9\u8986\u76d6\u7684\u57fa\u7840\u4e0a\uff0c\u4e3a\u6bcf\u4e2a\u9876\u70b9\u6dfb\u52a0\u6743\u91cd\uff08\u6743\u91cd\u6b63\u6bd4\u4e8e\u8282\u70b9\u7684\u5ea6\u6570\uff0cw(vi<\/sub>)=c*deg(vi<\/sub>)\uff09\uff0c\u9009\u53d6\u6743\u91cd\u548c\u6700\u5c0f\u7684\u9876\u70b9\u8986\u76d6<\/p>\n\n\n\n
                                                              \u8fd1\u4f3c\u7b97\u6cd5\uff1a\u76f4\u63a5\u9009\u53d6\u6240\u6709\u9876\u70b9<\/p>\n\n\n\n
                                                              \u8fd1\u4f3c\u6bd4\u5206\u6790<\/strong><\/p>\n\n\n\n
                                                              \u6bcf\u6761\u8fb9\u90fd\u81f3\u5c11\u6709\u4e00\u4e2a\u9876\u70b9\u5728OPT\u4e2d\uff0c\u6240\u4ee5OPT\u2265c*|E|
                                                              \u53c8\u6709<\/p>\n\n\n\n
                                                              \"w(V)=\sum_{v\in V}deg(v)=2*C|E|\"<\/div><\/p>\n\n\n\n
                                                              \u6545w(V)\u22642*OPT\uff0c\u8fd1\u4f3c\u6bd4\u4e3a2<\/p>\n\n\n\n
                                                              \u5e26\u6743\u503c\u7684\u9876\u70b9\u8986\u76d6<\/h4>\n\n\n\n
                                                              \u95ee\u9898\u63cf\u8ff0\uff1a\u5728\u6700\u5c0f\u9876\u70b9\u8986\u76d6\u7684\u57fa\u7840\u4e0a\uff0c\u4e3a\u6bcf\u4e2a\u9876\u70b9\u6dfb\u52a0\u6743\u91cd\uff08\u4e0d\u540c\u4e8e\u5ea6\u6743\u56fe\uff0c\u6b64\u5904\u6743\u503c\u4e3a\u4efb\u610f\u6b63\u6570\uff09\uff0c\u9009\u53d6\u6743\u91cd\u548c\u6700\u5c0f\u7684\u9876\u70b9\u8986\u76d6<\/p>\n\n\n\n
                                                              \u5206\u5c42\u7b97\u6cd5\uff1a<\/strong><\/p>\n\n\n\n
                                                                \n
                                                              • \u5728\u56fe\u4e2d\u9009\u53d6\u4e00\u4e2a\u5ea6\u6743\u6bd4\u6700\u9ad8\u7684\u9876\u70b9\uff0c\u5ea6\u6743\u6bd4\u4e3aw(vi<\/sub>)\/deg(vi<\/sub>)<\/li>\n\n\n\n
                                                              • \u6309\u7167\u6b64\u5ea6\u6743\u6bd4\u8ba1\u7b97\u4e00\u4e2a\u65b0\u56fe<\/li>\n\n\n\n
                                                              • \u539f\u56fe\u6743\u91cd\u51cf\u53bb\u65b0\u56fe\u6743\u91cd\uff08\u81f3\u5c11\u4e00\u4e2a\u4f1a\u88ab\u51cf\u52300\uff0c\u51cf\u52300\u7684\u9876\u70b9\u6dfb\u52a0\u5230\u9876\u70b9\u8986\u76d6\u4e2d\uff09<\/li>\n\n\n\n
                                                              • \u91cd\u590d1-3\u76f4\u81f3\u56fe\u4e3a\u7a7a<\/li>\n<\/ul>\n\n\n\n
                                                                \n
                                                                \n
                                                                \u539f\u56fe\uff1a<\/p>\n\n\n\n
                                                                \"\"<\/div><\/figure>\n<\/div>\n\n\n\n
                                                                \n
                                                                \u6309\u6700\u9ad8\u5ea6\u6743\u6bd4\u8ba1\u7b97\u7684\u65b0\u56fe\uff1a<\/p>\n\n\n\n
                                                                \"\"<\/div><\/figure>\n<\/div>\n\n\n\n
                                                                \n
                                                                \u539f\u56fe\u51cf\u53bb\u65b0\u56fe\uff1a<\/p>\n\n\n\n
                                                                \"\"<\/div><\/figure>\n<\/div>\n<\/div>\n\n\n\n
                                                                \u8fd1\u4f3c\u6bd4\u5206\u6790<\/strong><\/p>\n\n\n\n
                                                                \u539f\u56fe\u53ef\u4ee5\u770b\u4f5c\u591a\u4e2a\u5ea6\u6743\u56fe\u7684\u53e0\u52a0\uff0c\u5206\u5c42\u7b97\u6cd5\u76f8\u5f53\u4e8e\u5728\u591a\u4e2a\u4e0d\u540c\u7684\u5ea6\u6743\u56fe\u4e0a\u8fdb\u884c\u8fd1\u4f3c\u7b97\u6cd5\uff0c\u6bcf\u4e2a\u5ea6\u6743\u56fe\u7684\u8fd1\u4f3c\u6bd4\u90fd\u22642\uff0c\u6240\u4ee5\u5206\u5c42\u7b97\u6cd5\u7684\u8fd1\u4f3c\u6bd4\u4e5f\u4e3a2<\/p>\n\n\n\n
                                                                \u96c6\u5408\u8986\u76d6<\/h3>\n\n\n\n
                                                                \u96c6\u5408\u8986\u76d6<\/h4>\n\n\n\n
                                                                \u95ee\u9898\u63cf\u8ff0\uff1a<\/p>\n\n\n\n
                                                                  \n
                                                                • \u8f93\u5165\uff1a\u96c6\u5408B\uff0c\u96c6\u5408B\u7684\u5b50\u96c6S1<\/sub>,S2<\/sub>,…,Sm<\/sub><\/li>\n\n\n\n
                                                                • \u8f93\u51fa\uff1a\u4e00\u7cfb\u5217Si<\/sub>\uff0cSi<\/sub>\u7684\u5e76\u96c6\u662fB<\/li>\n\n\n\n
                                                                • cost\uff1aSi<\/sub>\u7684\u6570\u91cf<\/li>\n<\/ul>\n\n\n\n
                                                                  \u8d2a\u5fc3\u7b97\u6cd5\uff1a\u6bcf\u6b21\u6dfb\u52a0\u4e00\u4e2a\u5305\u542b\u672a\u88ab\u8986\u76d6\u5143\u7d20\u6700\u591a\u7684Si<\/sub><\/p>\n\n\n\n
                                                                  \u8fd1\u4f3c\u6bd4\u5206\u6790<\/strong><\/p>\n\n\n\n
                                                                  \u6211\u4eec\u6bcf\u6b21\u9009\u53d6\u4e00\u4e2a\u65b0\u7684\u672a\u88ab\u5b8c\u5168\u8986\u76d6\u7684\u96c6\u5408\uff0c\u90fd\u81f3\u5c11\u4f1a\u5305\u542ba\/OPT\u4e2a\u65b0\u5143\u7d20\uff0ca\u4e3a\u672a\u88ab\u627e\u5230\u7684\u5143\u7d20\u7684\u4e2a\u6570\uff0c\u4e5f\u5c31\u6709<\/p>\n\n\n\n
                                                                  \"$\begin{array}{lr}&a_{t+1}\leq a_{t}-\frac{a_{t}}{OPT}\\&a_{t+1}\leq a_{t}(1-\frac{1}{OPT})\\\end{array}$\"<\/div><\/p>\n\n\n\n
                                                                  \u5e94\u75281-x\u2264e-x<\/sup><\/p>\n\n\n\n
                                                                  \u53ef\u4ee5\u5f97\u5230at<\/sub>=0\u65f6t=ln n\u00b7OPT\uff0cn\u4e3a\u5143\u7d20\u4e2a\u6570<\/p>\n\n\n\n
                                                                  \u6b64\u7b97\u6cd5\u7684\u8fd1\u4f3c\u6bd4\u4e3aln n<\/p>\n\n\n\n
                                                                  \u5e26\u6743\u91cd\u7684\u96c6\u5408\u8986\u76d6\u95ee\u9898<\/h4>\n\n\n\n
                                                                  \u95ee\u9898\u63cf\u8ff0\uff1a<\/p>\n\n\n\n
                                                                    \n
                                                                  • \u8f93\u5165\uff1a\u96c6\u5408B\uff0c\u96c6\u5408B\u7684\u5b50\u96c6S1<\/sub>,S2<\/sub>,…,Sm<\/sub>\uff0c\u6bcf\u4e2aSi<\/sub>\u6709\u4e0d\u540c\u7684\u6743\u91cdc(Si<\/sub>)<\/li>\n\n\n\n
                                                                  • \u8f93\u51fa\uff1a\u4e00\u7cfb\u5217Si<\/sub>\uff0cSi<\/sub>\u7684\u5e76\u96c6\u662fB<\/li>\n\n\n\n
                                                                  • cost\uff1aSi<\/sub>\u7684\u6570\u91cf<\/li>\n<\/ul>\n\n\n\n
                                                                    \u8d2a\u5fc3\u7b97\u6cd5\uff1a\u5b9a\u4e49\u201c\u5e73\u5747\u6743\u91cd\u201d\uff08\u6743\u91cd\/\u5305\u542b\u672a\u6dfb\u52a0\u5143\u7d20\u7684\u4e2a\u6570\uff0cc(Si<\/sub>)\/|S-C|\uff09\uff0c\u6bcf\u6b21\u6dfb\u52a0\u5e73\u5747\u6743\u91cd\u6700\u4f4e\u7684Si<\/sub><\/p>\n\n\n\n
                                                                    \u8fd1\u4f3c\u6bd4\u5206\u6790<\/strong><\/p>\n\n\n\n
                                                                    \u6211\u4eec\u8ba1\u7b97\u7b2ck\u4e2a\u88ab\u8986\u76d6\u7684\u5143\u7d20ek<\/sub>\u7684\u6743\u91cd\uff1a<\/p>\n\n\n\n
                                                                    \u9009\u62e9ek<\/sub>\u65f6\u8fd8\u6709n-k+1\u4e2a\u5143\u7d20\u672a\u88ab\u8986\u76d6\uff0c\u6700\u4f18\u89e3\u7684\u603b\u4ee3\u4ef7\u4e3aOPT\uff0c\u5219\u8fd9\u4e9b\u5143\u7d20\u7684\u5e73\u5747\u4ee3\u4ef7\u2264OPT\/(n-k+1)\uff0c\u6211\u4eec\u9009\u62e9\u4e00\u4e2a\u6027\u4ef7\u6bd4\u6700\u9ad8\u7684\uff0cprice(ek<\/sub>)\u2264OPT\/(n-k+1)\uff0c\u5bf9price(ek<\/sub><\/code>)k\u22081-n\u6c42\u548c\uff0c\u5f97\u5230\u8fd1\u4f3c\u6bd4\u5982\u4e0b<\/p>\n\n\n\n
                                                                    \u8fd1\u4f3c\u6bd4\uff1af=1+1\/2+1\/3+…+1\/n\u2264ln n+1<\/p>\n\n\n\n
                                                                    \u65af\u5766\u7eb3\u6811Steiner Tree<\/h3>\n\n\n\n
                                                                    \u95ee\u9898\u63cf\u8ff0\uff1a\u65e0\u5411\u56fe\u4e2d\u7684\u9876\u70b9\u5206\u4e3a\u4e24\u7c7b\uff1a\u9014\u5f84\u70b9\uff08required\uff09\u548c\u65af\u5766\u7eb3\u70b9\uff08Steiner\uff09\uff0c\u8981\u6c42\u627e\u51fa\u4e00\u9897\u751f\u6210\u6811\uff0c\u7ecf\u8fc7\u6240\u6709\u9014\u5f84\u70b9\uff08\u53ef\u4ee5\u7ecf\u8fc7\u65af\u5766\u7eb3\u70b9\uff09\u3002\u82e5\u56fe\u6ee1\u8db3\u4e24\u8fb9\u4e4b\u548c\u5927\u4e8e\u7b2c\u4e09\u8fb9\uff0c\u4e14\u56fe\u4e3a\u5b8c\u5168\u56fe\uff0c\u5219\u8be5\u95ee\u9898\u79f0\u4e3a\u5ea6\u91cf\u65af\u5766\u7eb3\u6811\u95ee\u9898\uff08metric Steiner tree problem\uff09<\/p>\n\n\n\n
                                                                    \u65af\u5766\u7eb3\u6811\u95ee\u9898\u5230\u5ea6\u91cf\u65af\u5766\u7eb3\u6811\u95ee\u9898\u7684\u89c4\u7ea6<\/strong><\/p>\n\n\n\n
                                                                    \u89c4\u7ea6\u7b97\u6cd5\u7565\u590d\u6742\uff0c\u76f4\u63a5\u7ed9\u51fa\u7ed3\u8bba<\/p>\n\n\n\n
                                                                    \u7ed3\u8bba\uff1a\u5728\u5ea6\u91cf\u65af\u5766\u7eb3\u6811\u95ee\u9898\u4e2d\u82e5\u6709\u8fd1\u4f3c\u6bd4\u4e3ak\u7684\u7b97\u6cd5\uff0c\u5219\u65af\u5766\u7eb3\u6811\u95ee\u9898\u4e2d\u4e5f\u6709\u8fd1\u4f3c\u6bd4\u4e3ak\u7684\u7b97\u6cd5<\/p>\n\n\n\n
                                                                    \u5ea6\u91cf\u65af\u5766\u7eb3\u6811\u95ee\u9898\u7684\u8fd1\u4f3c\u7b97\u6cd5<\/strong><\/p>\n\n\n\n
                                                                    1.\u53ea\u5728\u9014\u5f84\u70b9\u4e0a\u505a\u6700\u5c0f\u751f\u6210\u6811<\/p>\n\n\n\n
                                                                    \u8fd1\u4f3c\u6bd4\u5206\u6790<\/strong><\/p>\n\n\n\n
                                                                    \u5047\u8bbe\u539f\u56feOPT\u5982\u4e0b\u56fe\u4e2d\u9ed1\u8272\u7ebf\u6bb5(\u603b\u957f\u5ea6OPT)\uff0c\u65b9\u6846\u4e3asteiner\u9876\u70b9\uff0c\u5706\u5708\u4e3a\u9014\u5f84\u70b9\u3002\u9996\u5148double\u6240\u6709\u8fb9\uff08\u603b\u957f\u5ea62*OPT\uff09\uff0c\u7136\u540e\u4ece\u4e00\u4e2a\u9014\u5f84\u70b9\u8d70\u4e00\u6761\u4e0d\u7ecf\u8fc7steiner\u9876\u70b9\u7684\u8def\u5f84\uff08\u603b\u8def\u7a0b=E\uff09\uff0c\u7136\u540e\u53bb\u6389\u6700\u957f\u7684\u4e00\u6761\u8fb9\uff08\u53d8\u6210\u4e86\u4e00\u9897\u751f\u6210\u6811\uff09\uff08\u603b\u8def\u7a0b\u4e3aP\uff09\uff0c\u9014\u5f84\u70b9\u4e0a\u7684\u6700\u5c0f\u751f\u6210\u6811\u8868\u793a\u4e3aMST<\/p>\n\n\n\n
                                                                    \"\"<\/div><\/figure>\n\n\n\n
                                                                    MST\u2264P\u2264E\u22642*OPT<\/p>\n\n\n\n
                                                                    \u8fd1\u4f3c\u6bd4\u4e3a2<\/p>\n\n\n\n
                                                                    \u5ea6\u91cf\u65c5\u884c\u5546\u4eba\u95ee\u9898TSP<\/h3>\n\n\n\n
                                                                    \u65c5\u884c\u5546\u4eba\u95ee\u9898TSP\uff1a\u5728\u5b8c\u5168\u56fe\u4e2d\uff0c\u627e\u5230\u4e00\u6761\u6700\u77ed\u8def\u5f84\uff0c\u7ecf\u8fc7\u6240\u6709\u9876\u70b9\u4e14\u4ec5\u7ecf\u8fc7\u4e00\u6b21\uff0c\u518d\u8fd4\u56de\u8d77\u70b9<\/p>\n\n\n\n
                                                                    \u4e00\u822c\u7684TSP\u4e0d\u5b58\u5728\u4efb\u610f\u8fd1\u4f3c\u7b97\u6cd5\uff0c\u5426\u5219P=NP<\/p>\n\n\n\n
                                                                    \u5ea6\u91cf\u65c5\u884c\u5546\u4eba\u95ee\u9898\uff1a\u56fe\u6ee1\u8db3\u4e24\u8fb9\u4e4b\u548c\u5927\u4e8e\u7b2c\u4e09\u8fb9<\/p>\n\n\n\n
                                                                    \u8fd1\u4f3c\u7b97\u6cd5\uff1a<\/p>\n\n\n\n
                                                                      \n
                                                                    • \u7b97\u51fa\u6700\u5c0f\u751f\u6210\u6811<\/li>\n\n\n\n
                                                                    • \u8865\u51fa\u84dd\u8272\u8def\u5f84\uff08\u6b27\u62c9\u56de\u8def\uff09<\/li>\n\n\n\n
                                                                    • \u6cbf\u84dd\u8272\u8def\u5f84\u8d70\uff0c\u5982\u679c\u8bbf\u95ee\u8fc7\u5c31\u8df3\u5230\u4e0b\u4e00\u4e2a\u8282\u70b9<\/li>\n<\/ul>\n\n\n\n
                                                                      \n
                                                                      \n
                                                                      \"\"<\/div><\/figure>\n<\/div>\n\n\n\n
                                                                      \n
                                                                      \"\"<\/div><\/figure>\n<\/div>\n\n\n\n
                                                                      \n
                                                                      \"\"<\/div><\/figure>\n<\/div>\n<\/div>\n\n\n\n
                                                                      \u8fd1\u4f3c\u6bd4\u4e3a2
                                                                      proof\uff1aMST\u2264OPT & Red_Path \u22642*MST=Blue_Path<\/p>\n\n\n\n
                                                                      \u66f4\u597d\u7684\u7b97\u6cd5\uff1a<\/strong>\u201cdouble edge\u201d\u8fc7\u4e8e\u7c97\u66b4<\/p>\n\n\n\n
                                                                        \n
                                                                      • \u6211\u4eec\u6311\u51fa\u5947\u6570\u5ea6\u7684\u9876\u70b9<\/li>\n\n\n\n
                                                                      • \u5c06\u9876\u70b9\u914d\u5bf9\u540e\u8fde\u63a5\uff0c\u540c\u6837\u53ef\u4ee5\u5f97\u5230\u4e00\u4e2a\u6b27\u62c9\u56de\u8def\uff08\u8fd9\u91cc\u9700\u8981\u7528\u6700\u5c0f\u7684\u8fb9\u8fde\u63a5\uff0c\u8fd9\u4e2a\u95ee\u9898\u4e0d\u96be\uff09<\/li>\n<\/ul>\n\n\n\n
                                                                        \n
                                                                        \n
                                                                        \n
                                                                        \n
                                                                        \n
                                                                        \n
                                                                        \n
                                                                        \"\"<\/div><\/figure>\n<\/div>\n\n\n\n
                                                                        \n
                                                                        \"\"<\/div><\/figure>\n<\/div>\n\n\n\n
                                                                        \n
                                                                        \"\"<\/div><\/figure>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n<\/div><\/div>\n<\/div>\n<\/div>\n\n\n\n
                                                                        \u8fd1\u4f3c\u6bd41.5
                                                                        proof\uff1aBlue_Path+Yellow_Path\u2264OPT\uff0c\u56e0\u4e3aBlue_Path\u2264Yellow_Path\uff0c\u6240\u4ee5Blue_Path\u22641\/2OPT
                                                                        Blue_Path+MST\u22643\/2OPT<\/p>\n\n\n\n
                                                                        PTAS\u3001FPTAS\u3001APTAS<\/h3>\n\n\n\n
                                                                        PTAS:\u5bf9\u4efb\u610f\u7ed9\u5b9a\u7684\u7cbe\u5ea6\u53c2\u6570 \u03b5<\/mi>><\/mo>0<\/mn><\/mrow>\\varepsilon>0<\/annotation><\/semantics><\/math>\uff0c\u7b97\u6cd5\u90fd\u80fd\u5728\u591a\u9879\u5f0f\u65f6\u95f4\u5185\u5f97\u5230\u4e00\u4e2a (<\/mo>1<\/mn>+<\/mo>\u03b5<\/mi>)<\/mo><\/mrow>(1+\\varepsilon)<\/annotation><\/semantics><\/math>\u8fd1\u4f3c\u89e3\u3002\uff08\u8fd0\u884c\u65f6\u95f4\uff1a\u5bf9\u56fa\u5b9a \u03b5<\/mi><\/mrow>\\varepsilon<\/annotation><\/semantics><\/math>\uff0c\u5173\u4e8e n<\/mi><\/mrow>n<\/annotation><\/semantics><\/math>\u662f\u591a\u9879\u5f0f\uff09
                                                                        FPTAS:\u5728PTAS\u57fa\u7840\u4e0a\uff0c\u8981\u6c42\u8fd0\u884c\u65f6\u95f4\u5173\u4e8e n<\/mi><\/mrow>n<\/annotation><\/semantics><\/math>\u548c 1<\/mn>\/<\/mi>\u03b5<\/mi><\/mrow>1\/\\varepsilon<\/annotation><\/semantics><\/math>\u90fd\u662f\u591a\u9879\u5f0f
                                                                        APTAS:\u5728PTAS\u57fa\u7840\u4e0a\uff0c\u5141\u8bb8\u8fd1\u4f3c\u6bd4\u589e\u52a0\u4e00\u4e2a\u5e38\u6570\u9879ALG\u2264(1+\u03b5)OPT+c\u03b5\u200b<\/sub><\/p>\n\n\n\n
                                                                        \u540d\u79f0<\/th>\u4fdd\u8bc1<\/th>\u65f6\u95f4\u590d\u6742\u5ea6<\/th><\/tr><\/thead>
                                                                        PTAS<\/td>ALG\u2264(1+\u03b5)OPT<\/td>\u56fa\u5b9a \u03b5\u65f6\u5173\u4e8en\u591a\u9879\u5f0f<\/td><\/tr>
                                                                        FPTAS<\/td>ALG\u2264(1+\u03b5)OPT<\/td>\u5173\u4e8en\u548c1\/\u03b5\u90fd\u591a\u9879\u5f0f<\/td><\/tr>
                                                                        APTAS<\/td>ALG\u2264(1+\u03b5)OPT+c\u03b5<\/sub><\/td>\u56fa\u5b9a\u03b5\u65f6\u5173\u4e8en\u591a\u9879\u5f0f<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n
                                                                        \u80cc\u5305\u95ee\u9898<\/h4>\n\n\n\n
                                                                        \u7ed9\u5b9a\u4e00\u4e2a\u03b5\uff0c\u6211\u4eec\u53ef\u4ee5\u5f97\u5230\u4e00\u4e2a\u8fd1\u4f3c\u5ea6\u4e3a1+\u03b5\u7684\u89e3\uff0c\u8d8a\u63a5\u8fd11\uff0c\u7b97\u6cd5\u590d\u6742\u5ea6\u8d8a\u5927\uff0c\u4e5f\u662f\u5c31FPTAS<\/p>\n\n\n\n
                                                                        \u65e0\u8bba\u7269\u54c1\u662f\u5426\u53ef\u91cd\u590d\uff0c\u5bf9\u4e8e\u80cc\u5305\u95ee\u9898\u6211\u4eec\u6709O(nW)\u7684\u7b97\u6cd5\uff0c\u4f46\u662f\u4e00\u822c\u6211\u4eec\u8ba4\u4e3an\u548cW\u90fd\u5f88\u5927\uff0c\u6211\u4eec\u4f7f\u7528n\u548cW\u7684\u6570\u4f4d\u957f\u5ea6\u4f5c\u4e3a\u8f93\u5165\uff0c\u6240\u4ee5\u662f\u6307\u6570\u7ea7\u7b97\u6cd5
                                                                        \u5728\u4f7f\u75281\u8fdb\u5236\u65f6\uff08\u6570\u4f4d\u957f\u5ea6\u7b49\u4e8e\u6570\u4f4d\u5927\u5c0f\uff0c5\u5199\u4f5c11111\uff09\uff0c\u80cc\u5305\u95ee\u9898\u662f\u4e00\u4e2a\u591a\u9879\u5f0f\u65f6\u95f4\u7b97\u6cd5<\/p>\n\n\n\n
                                                                        \u53e6\u5916\uff0c\u9664\u4e86\u4e4b\u524d\u8bb2\u8fc7\u7684O(nW)\u7684\u7b97\u6cd5\uff0c\u6211\u4eec\u8fd8\u6709\u4e00\u4e2aO(nV)\u7684\u7b97\u6cd5\uff08\u586b\u8868\u65f6\u8ba1\u7b97\u8fbe\u5230\u67d0\u4e2a\u4ef7\u503c\u65f6\uff0c\u81f3\u5c11\u9700\u8981\u591a\u5c11\u5bb9\u91cf\uff09<\/p>\n\n\n\n
                                                                        \u7b97\u6cd5\uff1a<\/p>\n\n\n\n
                                                                          \n
                                                                        • vmax<\/sub>\u4e3a\u6700\u9ad8\u7684\u4ef7\u503c<\/li>\n\n\n\n
                                                                        • \u4ee4vi<\/sub>‘=\u230avi<\/sub>\u00b7n\/\u03b5\u00b7vmax<\/sub>\u230b\uff0cn\u4e3a\u5143\u7d20\u4e2a\u6570\uff08\u5c06V\u7684\u4f4d\u6570\u53d8\u5c0f\u4e86\uff0c\u5f53\u7136\u4e5f\u5e26\u6765\u4e86\u4e00\u4e9b\u8bef\u5dee\uff0c\u5b9e\u9645\u4e0a\u5c31\u662f\u5ffd\u7565\u540e\u51e0\u4f4d\uff0c\u53ea\u6bd4\u8f83\u524d\u51e0\u4f4d\uff09<\/li>\n\n\n\n
                                                                        • \u4f7f\u7528vi<\/sub>‘\u8fd0\u884c\u52a8\u6001\u89c4\u5212<\/li>\n<\/ul>\n\n\n\n
                                                                          \u5f97\u5230\u7684vi<\/sub>‘\u6700\u5927\u4e3an\/\u03b5\uff0c\u5e94\u7528O(nV)\u7684\u7b97\u6cd5\uff0c\u65f6\u95f4\u590d\u6742\u5ea6\u4e3aO(n3<\/sup>\/\u03b5)<\/p>\n\n\n\n
                                                                          \u8fd1\u4f3c\u6bd4\u5206\u6790<\/strong>
                                                                          \u4ee4S\u4e3a\u539f\u95ee\u9898\u7cbe\u786e\u89e3\u7684\u96c6\u5408\uff0cK*\u4e3a\u6700\u4f18\u503c\uff1bS’\u4e3a\u5f97\u5230\u7684\u8fd1\u4f3c\u89e3\uff0c\u5219\u6709<\/p>\n\n\n\n
                                                                          \"$\sum_{i\in S}v_i'=\sum_{i\in S}\lfloor v_i\cdot \frac{n}{\epsilon \cdot v_{max}}\rfloor \geq \sum_{i \in S}(v_i\cdot \frac{n}{\epsilon \cdot v_{max}}-1)\geq K^*\cdot \frac{n}{\epsilon \cdot v_{max}} -n$\"<\/div><\/p>\n\n\n\n
                                                                          \"\sum_{i\in S'}v_i' \geq \sum_{i\in S}v_i'\"<\/div>\u2014\u2014nature\uff0c\u56e0\u4e3a\u6211\u4eec\u627e\u7684\u5c31\u662fv’\u4e0a\u7684\u6700\u4f18\u89e3S’\uff0c\u6240\u4ee5\u5fc5\u5b9a\u6bd4S\u5728v’\u4e0a\u66f4\u4f18<\/p>\n\n\n\n
                                                                          \"$\sum_{i\in S'}v_i\geq \sum_{i\in S'}v_i'\cdot \frac{\epsilon\cdot v_{max}}{n}\geq (K^*\cdot \frac{n}{\epsilon\cdot v_{max}}-n)\cdot \frac{\epsilon\cdot v_{max}}{n}=K^*-\epsilon\cdot v_{max}\geq K^*(1-\epsilon)$\"<\/div><\/p>\n\n\n\n
                                                                          \u88c5\u586b\u95ee\u9898<\/h4>\n\n\n\n
                                                                          \u95ee\u9898\u63cf\u8ff0\uff1a\u7ed9\u5b9an\u4e2a\u7269\u54c1\uff0c\u5c3a\u5bf8\u4ecb\u4e8e0-1\u4e4b\u95f4\uff0c\u6bcf\u4e2a\u7bb1\u5b50\u5c3a\u5bf8\u4e3a1\uff0c\u5982\u4f55\u88c5\u914d\u4f7f\u7528\u7684\u7bb1\u5b50\u6700\u5c0f<\/p>\n\n\n\n
                                                                          \u8fd1\u4f3c\u7b97\u6cd5\uff1a<\/p>\n\n\n\n
                                                                            \n
                                                                          • \u6bcf\u6b21\u4efb\u610f\u53d6\u51fa1\u4e2a\u7269\u54c1\uff0c\u5c1d\u8bd5\u653e\u5165\u5f53\u524d\u672a\u88ab\u586b\u6ee1\u7684\u7bb1\u5b50<\/li>\n\n\n\n
                                                                          • \u5982\u679c\u672a\u88ab\u586b\u6ee1\u7684\u7bb1\u5b50\u88c5\u4e0d\u8fdb\u53bb\uff0c\u5219\u589e\u52a0\u4e00\u4e2a\u7a7a\u7bb1\u5b50<\/li>\n<\/ul>\n\n\n\n
                                                                            \u8fd1\u4f3c\u6bd4\u5206\u6790<\/strong><\/p>\n\n\n\n
                                                                            nature:\u2211<\/mo>a<\/mi>i<\/mi><\/msub>\u2264<\/mo>O<\/mi>P<\/mi>T<\/mi><\/mrow>\\sum a_i\\le OPT<\/annotation><\/semantics><\/math>
                                                                            \u82e5\u7b97\u6cd5\u4f7f\u7528\u4e86m\u4e2a\u7bb1\u5b50\uff0c\u5219\u81f3\u5c11m-1\u4e2a\u7bb1\u5b50\u662f\u534a\u6ee1\u7684\uff0c\u56e0\u6b64\u2211<\/mo>a<\/mi>i<\/mi><\/msub>><\/mo>m<\/mi>\u2212<\/mo>1<\/mn><\/mrow>2<\/mn><\/mfrac><\/mrow>\\sum a_i > \\frac{m-1}{2}<\/annotation><\/semantics><\/math>
                                                                            m<\/mi>\u2212<\/mo>1<\/mn><<\/mo>2<\/mn>\u2217<\/mo>O<\/mi>P<\/mi>T<\/mi>;<\/mo>M<\/mi>\u2264<\/mo>2<\/mn>\u2217<\/mo>O<\/mi>P<\/mi>T<\/mi><\/mrow>m-1<2*OPT;M\\le 2*OPT<\/annotation><\/semantics><\/math><\/p>\n\n\n\n
                                                                            \u8fd1\u4f3c\u6bd4\u4e3a2<\/p>\n\n\n\n
                                                                            \u8fd1\u4f3c\u6bd4\u7684\u6781\u9650\u662f1.5\uff0c\u56e0\u4e3a\u5982\u679c\u5c0f\u4e8e1.5\uff0c\u800c\u6211\u4eec\u5f97\u51fa\u7684\u8fd1\u4f3c\u89e3\u662f2\u4e2a\u7bb1\u5b50\uff0c\u6211\u4eec\u5c31\u786e\u5b9a\u4e86\u7cbe\u786e\u89e3\u4e00\u5b9a\u662f\u4e24\u4e2a\u7bb1\u5b50\uff0cP=NP<\/p>\n\n\n\n
                                                                            \u66f4\u597d\u7684\u7b97\u6cd5<\/strong><\/p>\n\n\n\n
                                                                            \u5047\u8bben\u4e2a\u7269\u54c1\u4e2d\u6700\u5c0f\u7269\u54c1\u7684\u4f53\u79ef\u4e3a\u03b5<\/mi>\\varepsilon<\/annotation><\/semantics><\/math>\uff0c\u7269\u54c1\u6709K\u79cd\u4e0d\u540c\u7684\u4f53\u79ef\uff1b\u5219\u6bcf\u4e2a\u7bb1\u5b50\u81f3\u591a1<\/mn>\u03b5<\/mi><\/mfrac>\\frac{1}{\\varepsilon}<\/annotation><\/semantics><\/math>\u4e2a\u7269\u54c1\uff0c\u90a3\u4e48\u7bb1\u5b50\u88c5\u586b\u7684\u72b6\u6001\u81f3\u591a\u6709R<\/mi>=<\/mo>C<\/mi>K<\/mi>+<\/mo>1<\/mn>\u03b5<\/mi><\/mfrac><\/mrow>\u03b5<\/mi><\/msubsup><\/mrow>R=C_{K+\\frac{1}{\\varepsilon}}^{\\varepsilon}<\/annotation><\/semantics><\/math>\u79cd\uff0c\u6240\u4ee5\u81f3\u591a\u6709C<\/mi>R<\/mi>+<\/mo>n<\/mi><\/mrow>R<\/mi><\/msubsup>C_{R+n}^{R}<\/annotation><\/semantics><\/math>\u79cd\u6253\u5305\u65b9\u5f0f\uff0c\u5173\u4e8en\u4ecd\u662f\u591a\u9879\u5f0f\u7ea7\uff0c\u904d\u5386\u5373\u53ef\uff1b<\/p>\n\n\n\n
                                                                            \u56e0\u6b64\u8fd1\u4f3c\u7b97\u6cd5\u4e3a\uff1a\u4f18\u5148\u8003\u8651\u4f53\u79ef\u5927\u4e8e\u03b5<\/mi>\\varepsilon<\/annotation><\/semantics><\/math>\u7684\u7269\u54c1\uff0c\u901a\u8fc7\u904d\u5386\u5f97\u51fa\u6700\u4f18\u89e3\uff0c\u7136\u540e\u4f7f\u7528\u539f\u5148\u7684\u7b97\u6cd5\u586b\u5145<\/p>\n\n\n\n
                                                                            \u5728\u03b5<\/mi><<\/mo>1<\/mn>2<\/mn><\/mfrac><\/mrow>\\varepsilon<\\frac{1}{2}<\/annotation><\/semantics><\/math>\u65f6\uff0c\u8fd1\u4f3c\u6bd4\u4e3aALG\u2264(1+2\u03b5)OPT+1<\/p>\n\n\n\n
                                                                            \u57fa\u4e8e\u7ebf\u6027\u89c4\u5212\u7684\u8fd1\u4f3c\u7b97\u6cd5<\/h3>\n\n\n\n
                                                                            \u6211\u8d4c\u4f60\u4e0d\u8003<\/p>\n\n\n\n
                                                                            \u5173\u4e8e\u8003\u8bd5<\/h2>\n\n\n\n
                                                                            6*15+1*10<\/p>\n\n\n\n
                                                                            \u56fe\u8bba<\/h3>\n\n\n\n
                                                                            \u5b9a\u7406\u8bc1\u660e<\/p>\n\n\n\n
                                                                              \n
                                                                            • DAG,SCC<\/li>\n\n\n\n
                                                                            • \u5272\u5b9a\u7406<\/li>\n\n\n\n
                                                                            • \u6700\u77ed\u8def\u5f84<\/li>\n\n\n\n
                                                                            • \u6700\u5c0f\u751f\u6210\u6811<\/li>\n<\/ul>\n\n\n\n
                                                                              \u56fe\u7b97\u6cd5\uff0c\u57fa\u4e8eSCC\u3001\u6700\u77ed\u8def\u5f84\u7b49\u7b49<\/p>\n\n\n\n
                                                                              \u52a8\u6001\u89c4\u5212<\/h3>\n\n\n\n
                                                                              \u4e00\u9053\u5177\u4f53\u9898\u76ee<\/p>\n\n\n\n
                                                                              \u9012\u5f52\u5165\u53e3\uff0c\u7ed3\u679c\u4f4d\u7f6e\uff0c\u65f6\u7a7a\u590d\u6742\u5ea6\u5206\u6790\uff08\u538b\u8f74\uff09<\/p>\n\n\n\n
                                                                              \u7f51\u7edc\u6d41<\/h3>\n\n\n\n
                                                                              \u5b9a\u7406\u8bc1\u660e\u2014\u2014\u6700\u5927\u6d41\u6700\u5c0f\u5272<\/p>\n\n\n\n
                                                                              \u89c4\u7ea6<\/p>\n\n\n\n
                                                                              \u7ebf\u6027\u89c4\u5212<\/h3>\n\n\n\n
                                                                              \u95ee\u9898\u5efa\u6a21\u5e76\u6c42\u51fa\u5bf9\u5076<\/p>\n\n\n\n
                                                                              NP\u95ee\u9898<\/h3>\n\n\n\n
                                                                              \u5c06\u4e00\u4e2a\u5df2\u77e5\u95ee\u9898\u5f52\u7ea6\u5230<\/strong>\u4e00\u4e2a\u672a\u77e5\u95ee\u9898<\/strong>\uff0c\u6211\u4eec\u53ef\u4ee5\u8bc1\u660e<\/strong>\u672a\u77e5\u95ee\u9898\u6bd4\u5df2\u77e5\u95ee\u9898\u96be<\/p>\n\n\n\n
                                                                              \u8bc1\u660e\u662fNPC\u95ee\u9898-\u4e24\u6b65\uff08\u8bc1\u660eP\u65f6\u95f4\u5185\u53ef\u9a8c\u8bc1\uff0c\u5c06NPC\u95ee\u9898\u89c4\u7ea6\u8fc7\u53bb\uff09<\/p>\n\n\n\n
                                                                              \u8bc1\u660e\u662fNP\u95ee\u9898\uff08\u8bc1\u660eP\u65f6\u95f4\u5185\u53ef\u9a8c\u8bc1\uff09<\/s><\/p>\n\n\n\n
                                                                              \u6982\u5ff5\u6027\u95ee\u9898\uff1f<\/p>\n\n\n\n
                                                                              \u8fd1\u4f3c\u7b97\u6cd5<\/h3>\n\n\n\n
                                                                              \u8fd1\u4f3c\u7b97\u6cd5\u8bbe\u8ba1<\/p>\n\n\n\n
                                                                              \u8fd1\u4f3c\u6bd4\u8bc1\u660e<\/p>\n\n\n\n
                                                                              tight example<\/p>\n","protected":false},"excerpt":{"rendered":"
                                                                              \u56fe\u7b97\u6cd5 \u56fe\u7684\u5206\u89e3 \u65e0\u5411\u56fe DFS \u56fe\u7684\u8fde\u901a\u6027 \u6811\u8fb9(tree edge)\uff1aDFS\u65f6\u7ecf\u8fc7\u7684\u8fb9\u56de\u8fb9(back ed […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[9],"tags":[],"class_list":["post-1427","post","type-post","status-publish","format-standard","hentry","category-note"],"_links":{"self":[{"href":"https:\/\/www.smzytyzg.tw.cn\/index.php?rest_route=\/wp\/v2\/posts\/1427","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.smzytyzg.tw.cn\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.smzytyzg.tw.cn\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.smzytyzg.tw.cn\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.smzytyzg.tw.cn\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=1427"}],"version-history":[{"count":39,"href":"https:\/\/www.smzytyzg.tw.cn\/index.php?rest_route=\/wp\/v2\/posts\/1427\/revisions"}],"predecessor-version":[{"id":1508,"href":"https:\/\/www.smzytyzg.tw.cn\/index.php?rest_route=\/wp\/v2\/posts\/1427\/revisions\/1508"}],"wp:attachment":[{"href":"https:\/\/www.smzytyzg.tw.cn\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=1427"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.smzytyzg.tw.cn\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=1427"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.smzytyzg.tw.cn\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=1427"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}