{"id":200668,"date":"2024-05-10T01:58:14","date_gmt":"2024-05-09T17:58:14","guid":{"rendered":"https:\/\/docs.pingcode.com\/ask\/ask-ask\/200668.html"},"modified":"2024-05-10T01:58:20","modified_gmt":"2024-05-09T17:58:20","slug":"%e6%8c%87%e6%b4%be%e9%97%ae%e9%a2%98%e9%99%a4%e4%ba%86%e5%8c%88%e7%89%99%e5%88%a9%e7%ae%97%e6%b3%95%ef%bc%8c%e8%bf%98%e6%9c%89%e4%bb%80%e4%b9%88%e5%85%b6%e4%bb%96%e7%ae%97%e6%b3%95","status":"publish","type":"post","link":"https:\/\/docs.pingcode.com\/ask\/ask-ask\/200668.html","title":{"rendered":"\u6307\u6d3e\u95ee\u9898\u9664\u4e86\u5308\u7259\u5229\u7b97\u6cd5\uff0c\u8fd8\u6709\u4ec0\u4e48\u5176\u4ed6\u7b97\u6cd5"},"content":{"rendered":"

\"\u6307\u6d3e\u95ee\u9898\u9664\u4e86\u5308\u7259\u5229\u7b97\u6cd5\uff0c\u8fd8\u6709\u4ec0\u4e48\u5176\u4ed6\u7b97\u6cd5\"<\/p>\n

\u6307\u6d3e\u95ee\u9898\u9664\u4e86\u5308\u7259\u5229\u7b97\u6cd5\u8fd8\u5305\u62ecKM\u7b97\u6cd5\u3001\u62cd\u5356\u7b97\u6cd5\u3001\u6700\u5c0f\u8d39\u7528\u6700\u5927\u6d41\u7b97\u6cd5<\/strong>\u3002\u5176\u4e2d\uff0cKM\u7b97\u6cd5<\/strong>\u662f\u4e00\u4e2a\u6bd4\u8f83\u51fa\u540d\u7684\u66ff\u4ee3\u65b9\u6848\uff0c\u5b83\u7279\u522b\u9002\u7528\u4e8e\u6c42\u89e3\u5e26\u6743\u91cd\u7684\u6307\u6d3e\u95ee\u9898\u3002KM\u7b97\u6cd5\u5229\u7528\u8d2a\u5fc3\u601d\u60f3\u4e0e\u4e8c\u5206\u56fe\u6700\u5927\u5339\u914d\u7406\u8bba\uff0c\u901a\u8fc7\u6784\u5efa\u6807\u53f7\u51fd\u6570\u548c\u76f8\u7b49\u5b50\u56fe\u6765\u8fdb\u884c\u6c42\u89e3\u3002\u5728KM\u7b97\u6cd5\u4e2d\uff0c\u6bcf\u6b21\u8fed\u4ee3\u90fd\u4f1a\u5bfb\u627e\u6700\u5927\u6743\u503c\u7684\u5339\u914d\uff0c\u8fc7\u7a0b\u4e2d\u4f1a\u4e0d\u65ad\u8c03\u6574\u9876\u70b9\u7684\u6807\u53f7\uff0c\u76f4\u5230\u627e\u5230\u5168\u90e8\u5339\u914d\u6216\u8005\u6ee1\u8db3\u67d0\u4e9b\u6761\u4ef6\u4e3a\u6b62\u3002\u8fd9\u4e2a\u7b97\u6cd5\u7684\u65f6\u95f4\u590d\u6742\u5ea6\u5bf9\u4e8e\u4e00\u4e2aN*N\u7684\u77e9\u9635\u662fO(N^3)\uff0c\u9002\u7528\u4e8e\u5904\u7406\u7a20\u5bc6\u56fe\u4e2d\u7684\u6307\u6d3e\u95ee\u9898\u3002<\/p>\n<\/p>\n

\u4e00\u3001KM\u7b97\u6cd5<\/h3>\n<\/p>\n

KM\u7b97\u6cd5\uff08Kuhn-Munkres\u7b97\u6cd5\uff09\uff0c\u53c8\u79f0\u4e3a\u5308\u7259\u5229\u7b97\u6cd5\u7684\u6539\u8fdb\u7248\uff0c\u4e3b\u8981\u89e3\u51b3\u5e26\u6743\u5339\u914d\u95ee\u9898\u3002\u8fd9\u4e2a\u7b97\u6cd5\u7684\u6838\u5fc3\u5728\u4e8e\u8c03\u6574\u9876\u70b9\u7684\u6807\u53f7\uff08\u5373\u9876\u70b9\u7684\u6743\u503c\uff09\u4ece\u800c\u6539\u53d8\u76f8\u7b49\u5b50\u56fe\uff0c\u4ee5\u5bfb\u627e\u5b8c\u5907\u5339\u914d\u4f7f\u5f97\u603b\u6743\u503c\u6700\u5927\u3002<\/strong><\/p>\n<\/p>\n

KM\u7b97\u6cd5\u8fd0\u4f5c\u65f6\uff0c\u521d\u59cb\u5316\u4e00\u4e2a\u6807\u53f7\uff0c\u7136\u540e\u5728\u4e8c\u5206\u56fe\u4e2d\u6784\u9020\u4e00\u68f5\u4ea4\u9519\u6811\uff0c\u5bfb\u627e\u589e\u5e7f\u8def\u5f84\u3002\u82e5\u6ca1\u6709\u627e\u5230\u589e\u5e7f\u8def\u5f84\uff0c\u5219\u5bf9\u4ea4\u9519\u6811\u4e0a\u7684\u9876\u70b9\u91cd\u65b0\u8fdb\u884c\u6807\u53f7\uff0c\u66f4\u65b0\u540e\u7684\u76f8\u7b49\u5b50\u56fe\u4e2d\u5bfb\u627e\u589e\u5e7f\u8def\u5f84\u3002\u8fd9\u4e2a\u8fc7\u7a0b\u4f1a\u4e0d\u65ad\u8fed\u4ee3\uff0c\u76f4\u5230\u4e3a\u56fe\u4e2d\u6bcf\u4e00\u4e2a\u5de6\u90e8\uff08\u6216\u53f3\u90e8\uff09\u9876\u70b9\u90fd\u627e\u5230\u76f8\u5339\u914d\u7684\u9876\u70b9\u4e3a\u6b62\u3002<\/p>\n<\/p>\n

\u4e8c\u3001\u62cd\u5356\u7b97\u6cd5<\/h3>\n<\/p>\n

\u62cd\u5356\u7b97\u6cd5\u662f\u6307\u6d3e\u95ee\u9898\u4e2d\u53e6\u4e00\u79cd\u6709\u6548\u7684\u89e3\u51b3\u7b97\u6cd5\uff0c\u4e3b\u8981\u901a\u8fc7\u6a21\u62df\u62cd\u5356\u8fc7\u7a0b\u6765\u8fbe\u5230\u6c42\u89e3\u5339\u914d\u95ee\u9898\u7684\u76ee\u7684\u3002<\/strong><\/p>\n<\/p>\n

\u5728\u62cd\u5356\u7b97\u6cd5\u4e2d\uff0c\u7269\u54c1\u5c06\u88ab\u201c\u62cd\u5356\u201d\u7ed9\u51fa\u4ef7\u6700\u9ad8\u7684\u201c\u4e70\u5bb6\u201d\uff0c\u4e70\u5bb6\u4e4b\u95f4\u901a\u8fc7\u51fa\u4ef7\u7ade\u4e89\u7269\u54c1\u3002\u6bcf\u6b21\u53ea\u6709\u4e00\u4e2a\u4e70\u5bb6\u53c2\u4e0e\u7ade\u4ef7\uff0c\u4ed6\u5c06\u6839\u636e\u81ea\u5df1\u5bf9\u7269\u54c1\u7684\u4f30\u4ef7\u548c\u5f53\u524d\u7684\u5e02\u573a\u4ef7\u683c\uff0c\u51b3\u5b9a\u662f\u5426\u63d0\u9ad8\u51fa\u4ef7\u3002\u5f53\u6240\u6709\u7269\u54c1\u90fd\u88ab\u7ade\u4ef7\u7ed3\u675f\uff0c\u5e76\u4e14\u6ca1\u6709\u4e70\u5bb6\u613f\u610f\u63d0\u9ad8\u51fa\u4ef7\u65f6\uff0c\u7b97\u6cd5\u7ed3\u675f\u3002\u867d\u7136\u8fd9\u79cd\u7b97\u6cd5\u5728\u5b9e\u9645\u8ba1\u7b97\u4e2d\u6709\u53ef\u80fd\u5bfc\u81f4\u7ade\u4ef7\u6b21\u6570\u8fc7\u591a\uff0c\u8fdb\u800c\u5f71\u54cd\u6548\u7387\uff0c\u4f46\u5b83\u5728\u67d0\u4e9b\u7279\u5b9a\u60c5\u51b5\u4e0b\u7684\u8868\u73b0\u548c\u5b9e\u7528\u6027\u662f\u503c\u5f97\u80af\u5b9a\u7684\u3002<\/p>\n<\/p>\n

\u4e09\u3001\u6700\u5c0f\u8d39\u7528\u6700\u5927\u6d41\u7b97\u6cd5<\/h3>\n<\/p>\n

\u6700\u5c0f\u8d39\u7528\u6700\u5927\u6d41\u7b97\u6cd5\u662f\u53e6\u4e00\u79cd\u5728\u7f51\u7edc\u6d41\u9886\u57df\u975e\u5e38\u5b9e\u7528\u7684\u6307\u6d3e\u95ee\u9898\u7b97\u6cd5\uff0c\u5173\u952e\u5728\u4e8e\u5c06\u6307\u6d3e\u95ee\u9898\u8f6c\u5316\u4e3a\u7f51\u7edc\u6d41\u56fe\uff0c\u4ee5\u627e\u5230\u6700\u5c0f\u8d39\u7528\u7684\u6700\u5927\u6d41\u3002<\/strong><\/p>\n<\/p>\n

\u8fd9\u79cd\u7b97\u6cd5\u5229\u7528\u7f51\u7edc\u6d41\u56fe\u4e2d\u7684\u8282\u70b9\u8868\u793a\u4efb\u52a1\uff0c\u8fb9\u8868\u793a\u5206\u914d\u7684\u53ef\u80fd\u6027\uff0c\u8fb9\u7684\u5bb9\u91cf\u8868\u793a\u53ef\u4ee5\u540c\u65f6\u6267\u884c\u7684\u4efb\u52a1\u6570\u91cf\uff0c\u8fb9\u7684\u8d39\u7528\u5219\u8868\u793a\u5b8c\u6210\u4efb\u52a1\u7684\u6210\u672c\u3002\u7b97\u6cd5\u7684\u76ee\u6807\u662f\u5728\u6ee1\u8db3\u6240\u6709\u4efb\u52a1\u88ab\u5206\u914d\u5b8c\u6bd5\u7684\u524d\u63d0\u4e0b\uff0c\u627e\u5230\u4e00\u4e2a\u8d39\u7528\u4e4b\u548c\u6700\u5c0f\u7684\u6d41\u3002\u8fd9\u901a\u5e38\u901a\u8fc7\u4f7f\u7528\u5982Bellman-Ford\u3001Dijkstra\u7b97\u6cd5\u7b49\u7ecf\u5178\u6700\u77ed\u8def\u5f84\u7b97\u6cd5\u6765\u627e\u5230\u6700\u5c0f\u8d39\u7528\u7684\u589e\u5e7f\u8def\u5f84\uff0c\u7136\u540e\u589e\u52a0\u6d41\u91cf\uff0c\u76f4\u5230\u8fbe\u5230\u6700\u5927\u6d41\u3002\u8fd9\u4e2a\u7b97\u6cd5\u53ef\u4ee5\u6709\u6548\u5904\u7406\u5927\u89c4\u6a21\u7a00\u758f\u7f51\u7edc\uff0c\u7279\u522b\u662f\u89e3\u51b3\u8fd0\u8f93\u95ee\u9898\u3001\u7f51\u7edc\u8bbe\u8ba1\u7b49\u65b9\u9762\u3002<\/p>\n<\/p>\n

\u56db\u3001\u8fdb\u9636\u7b97\u6cd5<\/h3>\n<\/p>\n

\u6700\u540e\uff0c\u8fd8\u6709\u4e00\u4e9b\u66f4\u4e3a\u5148\u8fdb\u6216\u8005\u7279\u5b9a\u573a\u666f\u4e0b\u4f7f\u7528\u7684\u7b97\u6cd5\uff0c\u50cf\u57fa\u4e8e\u542f\u53d1\u5f0f\u7684\u9057\u4f20\u7b97\u6cd5\u3001\u7c92\u5b50\u7fa4\u4f18\u5316\u7b97\u6cd5\u7b49\uff0c\u867d\u7136\u8fd9\u4e9b\u7b97\u6cd5\u5728\u7406\u8bba\u6700\u4f18\u6027\u4e0a\u53ef\u80fd\u6709\u6240\u6b20\u7f3a\uff0c\u4f46\u5374\u80fd\u591f\u5728\u53ef\u63a5\u53d7\u7684\u65f6\u95f4\u5185\u627e\u5230\u8db3\u591f\u597d\u7684\u89e3\uff0c\u7279\u522b\u662f\u5728\u89c4\u6a21\u5e9e\u5927\u6216\u8005\u590d\u6742\u7a0b\u5ea6\u8f83\u9ad8\u7684\u5b9e\u9645\u5e94\u7528\u4e2d<\/strong>\u3002<\/p>\n<\/p>\n

\u9057\u4f20\u7b97\u6cd5<\/strong>\u548c\u7c92\u5b50\u7fa4\u4f18\u5316\u7b97\u6cd5<\/strong>\u90fd\u5c5e\u4e8e\u8fdb\u5316\u8ba1\u7b97\u7684\u8303\u7574\uff0c\u901a\u8fc7\u6a21\u62df\u81ea\u7136\u9009\u62e9\u548c\u9057\u4f20\u5b66\u7684\u8fc7\u7a0b\u6765\u8fed\u4ee3\u5bfb\u627e\u6700\u4f18\u89e3\u3002\u9057\u4f20\u7b97\u6cd5\u901a\u8fc7\u4ea4\u53c9\u3001\u53d8\u5f02\u3001\u9009\u62e9\u7b49\u64cd\u4f5c\u6765\u751f\u6210\u65b0\u7684\u89e3\u51b3\u65b9\u6848\uff0c\u800c\u7c92\u5b50\u7fa4\u4f18\u5316\u7b97\u6cd5\u5219\u662f\u901a\u8fc7\u6a21\u62df\u9e1f\u7fa4\u72e9\u730e\u7684\u65b9\u5f0f\uff0c\u8c03\u6574\u4e2a\u4f53\u5728\u89e3\u7a7a\u95f4\u4e2d\u7684\u4f4d\u7f6e\uff0c\u4ece\u800c\u9010\u6e10\u903c\u8fd1\u6700\u4f18\u89e3\u3002<\/p>\n<\/p>\n

\u8fd9\u4e9b\u7b97\u6cd5\u7684\u5171\u540c\u7279\u70b9\u662f\uff0c\u90fd\u6709\u7740\u8f83\u597d\u7684\u5168\u5c40\u641c\u7d22\u80fd\u529b\uff0c\u5e76\u4e14\u5bf9\u4e8e\u521d\u59cb\u89e3\u7684\u9009\u62e9\u4e0d\u592a\u654f\u611f\uff0c\u8fd9\u4f7f\u5f97\u5b83\u4eec\u5728\u591a\u76ee\u6807\u4f18\u5316\u3001\u52a8\u6001\u73af\u5883\u4e0b\u7684\u4f18\u5316\u95ee\u9898\u4e2d\u663e\u793a\u51fa\u4e86\u5f3a\u5927\u7684\u751f\u547d\u529b\u3002\u7279\u5b9a\u6761\u4ef6\u4e0b\uff0c\u8fd9\u4e9b\u7b97\u6cd5\u751a\u81f3\u80fd\u627e\u5230\u6bd4KM\u7b97\u6cd5\u3001\u62cd\u5356\u7b97\u6cd5\u7b49\u4f20\u7edf\u6570\u5b66\u4f18\u5316\u7b97\u6cd5\u66f4\u597d\u7684\u89e3\u51b3\u65b9\u6848\uff0c\u5c24\u5176\u662f\u5f53\u4f20\u7edf\u7b97\u6cd5\u56e0\u95ee\u9898\u89c4\u6a21\u592a\u5927\u800c\u53d8\u5f97\u4e0d\u518d\u9002\u7528\u7684\u65f6\u5019\u3002<\/p>\n<\/p>\n

\u76f8\u5173\u95ee\u7b54FAQs\uff1a<\/strong><\/h2>\n

1. \u5217\u4e3e\u4e00\u4e9b\u4e0e\u5308\u7259\u5229\u7b97\u6cd5\u7c7b\u4f3c\u7684\u7b97\u6cd5<\/strong><\/p>\n

    \n
  • \u4e8c\u5206\u56fe\u6700\u5927\u5339\u914d\u7b97\u6cd5\uff1a\u7528\u4e8e\u6c42\u89e3\u4e8c\u5206\u56fe\u4e2d\u7684\u6700\u5927\u5339\u914d\u95ee\u9898\uff0c\u4e0e\u5308\u7259\u5229\u7b97\u6cd5\u76f8\u4f3c\u4f46\u5b9e\u73b0\u65b9\u5f0f\u7565\u6709\u4e0d\u540c\u3002<\/li>\n
  • KM\u7b97\u6cd5\uff08Kuhn-Munkres\u7b97\u6cd5\uff09\uff1a\u4e5f\u79f0\u4e3a\u5308\u7259\u5229\u7b97\u6cd5\u7684\u53d8\u79cd\uff0c\u53ef\u4ee5\u7528\u4e8e\u6c42\u89e3\u6700\u5927\u6743\u503c\u4e8c\u5206\u56fe\u5339\u914d\u95ee\u9898\u3002<\/li>\n
  • Edmonds-Karp\u7b97\u6cd5\uff1a\u4e3b\u8981\u7528\u4e8e\u6c42\u89e3\u6700\u5927\u6d41\u95ee\u9898\uff0c\u5b83\u53ef\u4ee5\u770b\u4f5c\u662f\u5c06\u5308\u7259\u5229\u7b97\u6cd5\u5e94\u7528\u5230\u7f51\u7edc\u6d41\u4e2d\u7684\u4e00\u79cd\u63a8\u5e7f\u3002<\/li>\n<\/ul>\n

    2. \u9664\u4e86\u5308\u7259\u5229\u7b97\u6cd5\u548c\u5b83\u7684\u53d8\u79cd\uff0c\u8fd8\u6709\u54ea\u4e9b\u5e38\u7528\u7684\u56fe\u5339\u914d\u7b97\u6cd5\uff1f<\/strong><\/p>\n

      \n
    • Hopcroft-Karp\u7b97\u6cd5\uff1a\u53ef\u4ee5\u5728$O(\\sqrt{V}E)$\u7684\u65f6\u95f4\u590d\u6742\u5ea6\u4e0b\u6c42\u89e3\u6700\u5927\u5339\u914d\u95ee\u9898\uff0c\u76f8\u8f83\u4e8e\u5308\u7259\u5229\u7b97\u6cd5\u6709\u66f4\u9ad8\u7684\u6548\u7387\u3002<\/li>\n
    • Ford-Fulkerson\u7b97\u6cd5\uff1a\u7528\u4e8e\u6c42\u89e3\u6700\u5927\u6d41\u95ee\u9898\uff0c\u901a\u8fc7\u4e0d\u65ad\u5bfb\u627e\u589e\u5e7f\u8def\u5f84\u6765\u8fbe\u5230\u6700\u4f18\u89e3\u3002<\/li>\n<\/ul>\n

      3. \u9664\u4e86\u56fe\u5339\u914d\u7b97\u6cd5\uff0c\u8fd8\u6709\u54ea\u4e9b\u5e38\u7528\u7684\u641c\u7d22\u7b97\u6cd5\u53ef\u4ee5\u7528\u4e8e\u89e3\u51b3\u76f8\u4f3c\u7684\u95ee\u9898\uff1f<\/strong><\/p>\n

        \n
      • A*\u7b97\u6cd5\uff1a\u662f\u4e00\u79cd\u542f\u53d1\u5f0f\u641c\u7d22\u7b97\u6cd5\uff0c\u4e3b\u8981\u7528\u4e8e\u6c42\u89e3\u6700\u77ed\u8def\u5f84\u95ee\u9898\uff0c\u53ef\u4ee5\u5e94\u7528\u4e8e\u5bfb\u627e\u4e24\u4e2a\u56fe\u4e4b\u95f4\u7684\u6700\u4f73\u5339\u914d\u3002<\/li>\n
      • \u56de\u6eaf\u7b97\u6cd5\uff1a\u9002\u7528\u4e8e\u6c42\u89e3\u7ec4\u5408\u4f18\u5316\u95ee\u9898\uff0c\u53ef\u4ee5\u7528\u4e8e\u6c42\u89e3\u5177\u6709\u4e00\u5b9a\u7ea6\u675f\u6761\u4ef6\u7684\u6700\u4f73\u5339\u914d\u95ee\u9898\uff0c\u5982\u65c5\u884c\u5546\u95ee\u9898\u7b49\u3002<\/li>\n<\/ul>\n","protected":false},"excerpt":{"rendered":"\u6307\u6d3e\u95ee\u9898\u9664\u4e86\u5308\u7259\u5229\u7b97\u6cd5\u8fd8\u5305\u62ecKM\u7b97\u6cd5\u3001\u62cd\u5356\u7b97\u6cd5\u3001\u6700\u5c0f\u8d39\u7528\u6700\u5927\u6d41\u7b97\u6cd5\u3002\u5176\u4e2d\uff0cKM\u7b97\u6cd5\u662f\u4e00\u4e2a\u6bd4\u8f83\u51fa\u540d\u7684\u66ff\u4ee3\u65b9\u6848\uff0c\u5b83 […]","protected":false},"author":3,"featured_media":200673,"comment_status":"closed","ping_status":"","sticky":false,"template":"","format":"standard","meta":{"_acf_changed":false,"footnotes":""},"categories":[37],"tags":[],"acf":[],"_links":{"self":[{"href":"https:\/\/docs.pingcode.com\/wp-json\/wp\/v2\/posts\/200668"}],"collection":[{"href":"https:\/\/docs.pingcode.com\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/docs.pingcode.com\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/docs.pingcode.com\/wp-json\/wp\/v2\/users\/3"}],"replies":[{"embeddable":true,"href":"https:\/\/docs.pingcode.com\/wp-json\/wp\/v2\/comments?post=200668"}],"version-history":[{"count":0,"href":"https:\/\/docs.pingcode.com\/wp-json\/wp\/v2\/posts\/200668\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/docs.pingcode.com\/wp-json\/wp\/v2\/media\/200673"}],"wp:attachment":[{"href":"https:\/\/docs.pingcode.com\/wp-json\/wp\/v2\/media?parent=200668"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/docs.pingcode.com\/wp-json\/wp\/v2\/categories?post=200668"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/docs.pingcode.com\/wp-json\/wp\/v2\/tags?post=200668"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}