{"id":787,"date":"2025-12-09T02:51:12","date_gmt":"2025-12-09T02:51:12","guid":{"rendered":"https:\/\/learndeeplytw.com\/?p=787"},"modified":"2025-12-09T02:58:17","modified_gmt":"2025-12-09T02:58:17","slug":"minimal-spanning-tree","status":"publish","type":"post","link":"https:\/\/learndeeplytw.com\/zh_tw\/minimal-spanning-tree\/","title":{"rendered":"\u5f9e\u300c\u6ce5\u6fd8\u57ce\u5e02\u300d\u8a8d\u8b58\u6700\u7701\u9322\u7684\u92ea\u8def\u9b54\u6cd5-\u6700\u5c0f\u751f\u6210\u6a39\uff08Minimal Spanning Tree\uff09"},"content":{"rendered":"\n<p class=\"\">\u5728\u96fb\u8166\u79d1\u5b78\u4e2d\uff0c\u6709\u4e00\u500b\u5f88\u7d93\u5178\u7684\u554f\u984c\u53eb\u505a\u300c\u6700\u5c0f\u751f\u6210\u6a39 (Minimal Spanning Tree)\u300d\u3002\u807d\u8d77\u4f86\u5f88\u6df1\u5967\uff0c\u4f46\u5b83\u7684\u6838\u5fc3\u89c0\u5ff5\u5176\u5be6\u5c31\u662f\uff1a\u300c\u5982\u4f55\u7528\u6700\u5c11\u7684\u6750\u6599\uff0c\u628a\u6240\u6709\u4eba\u90fd\u9023\u63a5\u8d77\u4f86\uff1f\u300d<\/p>\n\n\n\n<p class=\"\">\u4eca\u5929\u6211\u5011\u4e0d\u5beb\u7a0b\u5f0f\uff0c\u6211\u5011\u8981\u9032\u5165\u4e00\u500b\u525b\u4e0b\u904e\u5927\u96e8\u7684\u300c\u6ce5\u6fd8\u57ce\u5e02\u300d\u3002\u6211\u5011\u8981\u9080\u8acb\u5b69\u5b50\u64d4\u4efb\u5e02\u9577\uff0c\u89e3\u6c7a\u5e02\u6c11\u7684\u56f0\u64fe\uff0c\u800c\u4e14\u53ea\u8981\u4ed6\u80fd\u6210\u529f\u7701\u4e0b\u9810\u7b97\uff0c\u57ce\u5e02\u88e1\u5c31\u80fd\u591a\u84cb\u4e00\u5ea7\u6e38\u6cf3\u6c60\uff01<\/p>\n\n\n\n<h4 class=\"wp-block-heading\">\u7b2c\u4e00\u968e\u6bb5\uff1a<strong>\u721b\u6ce5\u5df4\u8207\u6e38\u6cf3\u6c60\u7684\u6289\u64c7<\/strong><\/h4>\n\n\n\n<p class=\"\">\u9996\u5148\uff0c\u6211\u5011\u7528\u6545\u4e8b\u5275\u9020\u60c5\u5883\uff0c\u8b93\u300c\u6700\u4f73\u5316 (Optimization)\u300d\u8b8a\u6210\u4e00\u7a2e\u8feb\u5207\u7684\u9700\u6c42\u3002<\/p>\n\n\n\n<ol start=\"1\" class=\"wp-block-list\">\n<li class=\"\"><strong>\u60c5\u5883\u8a2d\u5b9a\uff1a<\/strong>\n<ul class=\"wp-block-list\">\n<li class=\"\">\u62ff\u51fa\u300c\u6ce5\u6fd8\u57ce\u5e02\u300d\u7684\u5730\u5716\uff08\u5716\u4e0a\u6709\u8a31\u591a\u623f\u5b50\u548c\u865b\u7dda\u9053\u8def\uff09\u3002<\/li>\n\n\n\n<li class=\"\"><strong>\u6545\u4e8b\uff1a<\/strong>\u300c\u5f88\u4e45\u4ee5\u524d\uff0c\u6709\u4e00\u500b\u6c92\u6709\u92ea\u8def\u7684\u5c0f\u57ce\u5e02\u3002\u6bcf\u6b21\u4e0b\u904e\u5927\u96e8\uff0c\u9019\u88e1\u5c31\u8b8a\u6210\u721b\u6ce5\u5df4\u5730\uff0c\u8eca\u5b50\u6703\u5361\u4f4f\uff0c\u5927\u5bb6\u7684\u978b\u5b50\u90fd\u6703\u9ad2\u6389\u300d\u3002<\/li>\n\n\n\n<li class=\"\"><strong>\u4efb\u52d9\uff1a<\/strong>\u300c\u4f60\u662f\u65b0\u4e0a\u4efb\u7684\u5e02\u9577\u3002\u5e02\u6c11\u62dc\u8a17\u4f60\u628a\u8def\u92ea\u597d\uff0c\u8b93\u6bcf\u4e00\u500b\u623f\u5b50\u90fd\u53ef\u4ee5\u901a\u5230\u5176\u4ed6\u4efb\u4f55\u4e00\u500b\u623f\u5b50\u300d\u3002<\/li>\n<\/ul>\n<\/li>\n\n\n\n<li class=\"\"><strong>\u95dc\u9375\u885d\u7a81\uff1a<\/strong>\n<ul class=\"wp-block-list\">\n<li class=\"\">\u300c\u4f46\u662f\uff0c\u92ea\u8def\u7684\u77f3\u982d\u5f88\u8cb4\uff01\u5e02\u5eab\u7684\u9322\u672c\u4f86\u662f\u8981\u62ff\u4f86\u84cb\u4e00\u5ea7\u5927\u6e38\u6cf3\u6c60\u7684\u300d\u3002<\/li>\n\n\n\n<li class=\"\">\u300c\u5982\u679c\u4f60\u628a\u6bcf\u4e00\u689d\u8def\u90fd\u92ea\u6eff\uff0c\u9322\u82b1\u5149\u4e86\uff0c\u6e38\u6cf3\u6c60\u5c31\u6c92\u4e86\u3002\u4f60\u7684\u6311\u6230\u662f\uff1a\u7528\u6700\u5c11\u7684\u77f3\u982d\uff0c\u628a\u6240\u6709\u623f\u5b50\u9023\u8d77\u4f86\uff0c\u7701\u4e0b\u4f86\u7684\u9322\u5c31\u62ff\u53bb\u84cb\u6cf3\u6c60\uff01\u300d\u3002<\/li>\n<\/ul>\n<\/li>\n<\/ol>\n\n\n\n<figure class=\"wp-block-image aligncenter size-large is-resized\"><img loading=\"lazy\" decoding=\"async\" width=\"1024\" height=\"659\" loading=\"lazy\" src=\"https:\/\/learndeeplytw.com\/wp-content\/uploads\/2025\/12\/image-5-1024x659.png\" alt=\"\" class=\"wp-image-790\" style=\"aspect-ratio:1.5539009388151506;width:623px;height:auto\" srcset=\"https:\/\/learndeeplytw.com\/wp-content\/uploads\/2025\/12\/image-5-1024x659.png 1024w, https:\/\/learndeeplytw.com\/wp-content\/uploads\/2025\/12\/image-5-300x193.png 300w, https:\/\/learndeeplytw.com\/wp-content\/uploads\/2025\/12\/image-5-768x494.png 768w, https:\/\/learndeeplytw.com\/wp-content\/uploads\/2025\/12\/image-5-18x12.png 18w, https:\/\/learndeeplytw.com\/wp-content\/uploads\/2025\/12\/image-5.png 1196w\" sizes=\"auto, (max-width: 1024px) 100vw, 1024px\" \/><\/figure>\n\n\n\n<h4 class=\"wp-block-heading\">\u7b2c\u4e8c\u968e\u6bb5\uff1a<strong>\u8996\u89ba\u5316\u7684\u6210\u672c<\/strong><\/h4>\n\n\n\n<p class=\"\">\u6211\u5011\u8981\u8b93\u300c\u9577\u5ea6\u300d\u8b8a\u6210\u770b\u5f97\u898b\u7684\u300c\u6578\u91cf\u300d\u3002<\/p>\n\n\n\n<ol start=\"1\" style=\"line-height:2\" class=\"wp-block-list\">\n<li class=\"\"><strong>\u6e96\u5099\u9053\u5177\uff1a<\/strong>\n<ul class=\"wp-block-list\">\n<li class=\"\">\u5217\u5370\u51fa\u4e0a\u65b9\u7684\u5730\u5716\uff0c\u6e96\u5099\u7d04 40 \u500b\u9ed1\u8272\u7c4c\u78bc\uff08\u6216\u662f\u570d\u68cb\u5b50\u3001\u5c0f\u7a4d\u6728\u3001\u771f\u6b63\u7684\u77f3\u982d\uff09\u3002<\/li>\n\n\n\n<li class=\"\">\u6216\u5229\u7528\u4e0b\u65b9\u7684\u904a\u6232\u3002<\/li>\n<\/ul>\n<\/li>\n\n\n\n<li class=\"\"><strong>\u898f\u5247\u89e3\u8aaa\uff1a<\/strong>\n<ul class=\"wp-block-list\">\n<li class=\"\">\u5730\u5716\u4e0a\u623f\u5b50\u4e4b\u9593\u7684\u65b9\u683c\u5b50\uff0c\u4ee3\u8868\u90a3\u689d\u8def\u7684\u9577\u5ea6\u3002<\/li>\n\n\n\n<li class=\"\"><strong>\u92ea\u8def\u65b9\u5f0f\uff1a<\/strong>\u62ff\u51fa\u7c4c\u78bc\u628a\u683c\u5b50\u586b\u6eff\uff0c\u5c31\u4ee3\u8868\u9019\u689d\u8def\u92ea\u597d\u4e86\u3002\u683c\u5b50\u8d8a\u591a\uff0c\u4ee3\u8868\u8def\u8d8a\u9577\uff0c\u8981\u82b1\u7684\u9322\uff08\u77f3\u982d\uff09\u5c31\u8d8a\u591a\u3002<\/li>\n\n\n\n<li class=\"\"><strong>\u76ee\u6a19\uff1a<\/strong>\u8acb\u5b69\u5b50\u8a66\u8457\u5728\u7d19\u4e0a\u64fa\u653e\u7c4c\u78bc\uff0c\u76f4\u5230\u6240\u6709\u623f\u5b50\u90fd\u300c\u9023\u901a\u300d\uff0c\u4e26\u8a08\u7b97\u7528\u4e86\u591a\u5c11\u9846\u77f3\u982d\u3002<\/li>\n<\/ul>\n<\/li>\n<\/ol>\n\n\n\n<h4 class=\"wp-block-heading\">\u7b2c\u4e09\u968e\u6bb5\uff1a<strong>Kruskal \u7684\u92ea\u8def\u9b54\u6cd5<\/strong><\/h4>\n\n\n\n<p class=\"\">\u5b69\u5b50\u4e00\u958b\u59cb\u53ef\u80fd\u6703\u96a8\u610f\u4e82\u9023\uff0c\u6216\u9023\u6210\u4e00\u500b\u5713\u5708\u3002\u9019\u6642\u6211\u5011\u8981\u5f15\u5c0e\u51fa\u96fb\u8166\u79d1\u5b78\u5bb6\u7684\u7b56\u7565\uff08Kruskal \u6f14\u7b97\u6cd5\uff09\u3002<\/p>\n\n\n\n<ol start=\"1\" style=\"line-height:2\" class=\"wp-block-list\">\n<li class=\"\"><strong>\u76f4\u89ba\u5617\u8a66\uff1a<\/strong>\n<ul class=\"wp-block-list\">\n<li class=\"\">\u8b93\u5b69\u5b50\u5148\u8a66\u4e00\u6b21\u3002\u4ed6\u5011\u53ef\u80fd\u7528\u4e86 25 \u9846\u77f3\u982d\u3002<\/li>\n\n\n\n<li class=\"\"><strong>\u5bb6\u9577\uff1a<\/strong>\u300c25 \u9846&#8230; \u597d\u50cf\u6709\u9ede\u8cb4\uff0c\u6e38\u6cf3\u6c60\u53ea\u80fd\u84cb\u4e00\u534a\u3002\u6211\u5011\u80fd\u4e0d\u80fd\u66f4\u7bc0\u7701\u4e00\u9ede\uff1f\u300d<\/li>\n<\/ul>\n<\/li>\n\n\n\n<li class=\"\"><strong>\u5f15\u5c0e\u7b56\u7565\uff1a<\/strong>\n<ul class=\"wp-block-list\">\n<li class=\"\"><strong>\u5bb6\u9577\u63d0\u554f\uff1a<\/strong>\u300c\u65e2\u7136\u6211\u5011\u8981\u7701\u9322\uff0c\u6211\u5011\u61c9\u8a72\u5148\u92ea\u300e\u9577\u7684\u8def\u300f\u9084\u662f\u300e\u77ed\u7684\u8def\u300f\uff1f\u300d<\/li>\n\n\n\n<li class=\"\"><strong>\u5b69\u5b50\uff1a<\/strong>\u300c\u77ed\u7684\uff01\u56e0\u70ba\u7528\u7684\u77f3\u982d\u5c11\u3002\u300d<\/li>\n\n\n\n<li class=\"\"><strong>\u57f7\u884c\u9b54\u6cd5\uff1a<\/strong>\n<ol start=\"1\" class=\"wp-block-list\">\n<li class=\"\">\u300c\u597d\uff01\u6211\u5011\u73fe\u5728\u773c\u775b\u6383\u63cf\u6574\u5f35\u5730\u5716\uff0c\u54ea\u88e1\u7684\u8def\u6700\u77ed\uff1f\u300d<\/li>\n\n\n\n<li class=\"\">\u5b69\u5b50\u6703\u627e\u5230\u90a3\u4e9b\u53ea\u6709 2 \u683c\u6216 3 \u683c\u7684\u8def\u3002<\/li>\n\n\n\n<li class=\"\">\u300c\u628a\u5b83\u92ea\u8d77\u4f86\uff01\u300d\uff08\u653e\u4e0a\u7c4c\u78bc\uff09\u3002<\/li>\n\n\n\n<li class=\"\">\u63a5\u8457\u627e\u300c\u7b2c\u4e8c\u77ed\u300d\u3001\u300c\u7b2c\u4e09\u77ed\u300d\u7684\u8def\uff0c\u4f9d\u5e8f\u92ea\u4e0b\u53bb\u3002<\/li>\n<\/ol>\n<\/li>\n<\/ul>\n<\/li>\n\n\n\n<li class=\"\"><strong>\u95dc\u9375\u5224\u65b7\uff1a<\/strong>\n<ul class=\"wp-block-list\">\n<li class=\"\">\u7576\u5b69\u5b50\u60f3\u92ea\u67d0\u4e00\u689d\u8def\u6642\uff0c\u8acb\u4ed6\u66ab\u505c\u4e00\u4e0b\u3002<\/li>\n\n\n\n<li class=\"\"><strong>\u63d0\u554f\uff1a<\/strong>\u300c\u7b49\u7b49\uff01\u9019\u5169\u500b\u623f\u5b50\uff0c\u900f\u904e\u5225\u689d\u8def\u5df2\u7d93\u53ef\u4ee5\u901a\u4e86\u55ce\uff1f\u300d<\/li>\n\n\n\n<li class=\"\"><strong>\u89c0\u5bdf\uff1a<\/strong> \u5982\u679c\u623f\u5b50 A \u548c\u623f\u5b50 B \u65e9\u5c31\u9023\u901a\u4e86\uff08\u7e5e\u9060\u8def\u4e5f\u80fd\u5230\uff09\uff0c\u9019\u689d\u65b0\u8def\u5c31\u662f\u300c\u6d6a\u8cbb\u9322\u7684\u6377\u5f91\u300d\u3002<\/li>\n\n\n\n<li class=\"\"><strong>\u5bb6\u9577\u6307\u4ee4\uff1a<\/strong>\u300c\u65e2\u7136\u5df2\u7d93\u901a\u4e86\uff0c\u9019\u689d\u8def\u96d6\u7136\u77ed\uff0c\u4f46\u6211\u5011\u4e0d\u92ea\uff01\u7701\u4e0b\u4f86\uff01\u300d\u3002<\/li>\n<\/ul>\n<\/li>\n\n\n\n<li class=\"\"><strong>\u7d50\u679c\u63ed\u66c9\uff1a<\/strong>\n<ul class=\"wp-block-list\">\n<li class=\"\">\u4f9d\u7167\u9019\u500b\u300c\u5148\u6311\u4fbf\u5b9c\u7684\u92ea\u3001\u4e0d\u92ea\u91cd\u8907\u7684\u8def\u300d\u7684\u898f\u5247\u505a\u5230\u5e95\u3002<\/li>\n\n\n\n<li class=\"\">\u6700\u5f8c\u7b97\u51fa\u77f3\u982d\u7e3d\u6578\uff08\u6700\u4f73\u89e3\u901a\u5e38\u6703\u6bd4\u5b69\u5b50\u4e82\u8a66\u7684\u5c11\u5f88\u591a\uff09\u3002<\/li>\n\n\n\n<li class=\"\">\u6b61\u547c\uff1a\u300c\u606d\u559c\u5e02\u9577\uff01\u4f60\u6210\u529f\u7528\u6700\u5c11\u7684\u77f3\u982d\u9023\u901a\u4e86\u5168\u57ce\uff0c\u6e38\u6cf3\u6c60\u7d93\u8cbb\u6709\u8457\u843d\u4e86\uff01\u300d<\/li>\n<\/ul>\n<\/li>\n<\/ol>\n\n\n\n<h4 class=\"wp-block-heading\">\u7b2c\u56db\u968e\u6bb5\uff1a\u6982\u5ff5\u9023\u7d50<\/h4>\n\n\n\n<ul style=\"line-height:2\" class=\"wp-block-list\">\n<li class=\"\"><strong>\u5bb6\u9577<\/strong>\uff1a\u300c\u4f60\u525b\u525b\u7528\u7684\u9019\u500b\u8d85\u7701\u9322\u7b56\u7565\uff0c\u662f\u4e00\u500b\u53eb Kruskal \u7684\u4eba\u767c\u660e\u7684\uff08Kruskal \u6f14\u7b97\u6cd5\uff09\u3002\u4f60\u89ba\u5f97\u9664\u4e86\u92ea\u99ac\u8def\uff0c\u9084\u6709\u4ec0\u9ebc\u6771\u897f\u4e5f\u9700\u8981\u9019\u6a23\u300e\u9023\u5728\u4e00\u8d77\u4f46\u8d8a\u77ed\u8d8a\u597d\u300f\uff1f\u300d<\/li>\n\n\n\n<li class=\"\"><strong>\u5f15\u5c0e\u601d\u8003\uff1a<\/strong>\n<ul class=\"wp-block-list\">\n<li class=\"\"><strong>\u96fb\u529b\u516c\u53f8\uff1a<\/strong>\u96fb\u7dda\u8981\u9023\u5230\u6bcf\u4e00\u5bb6\uff0c\u96fb\u7dda\u8d8a\u77ed\u8d8a\u7701\u9322\u3002<\/li>\n\n\n\n<li style=\"line-height:1.8\" class=\"\"><strong>\u81ea\u4f86\u6c34\u7ba1\uff1a<\/strong>\u6c34\u7ba1\u8981\u63a5\u901a\u5168\u57ce\uff0c\u7ba1\u5b50\u8d8a\u5c11\u8d8a\u4e0d\u5bb9\u6613\u6f0f\u6c34\u3002<\/li>\n\n\n\n<li class=\"\"><strong>\u7db2\u969b\u7db2\u8def\uff1a<\/strong>\u96fb\u8166\u7db2\u8def\u7684\u9023\u7dda\u4e5f\u8981\u8b1b\u7a76\u6548\u7387\u3002<\/li>\n<\/ul>\n<\/li>\n\n\n\n<li class=\"\"><strong>\u5c08\u6709\u540d\u8a5e\uff1a<\/strong>\u9019\u500b\u9023\u51fa\u4f86\u7684\u5f62\u72c0\uff0c\u96fb\u8166\u79d1\u5b78\u5bb6\u53eb\u5b83\u300c\u6700\u5c0f\u751f\u6210\u6a39 (Minimal Spanning Tree)\u300d\u3002\n<ul class=\"wp-block-list\">\n<li class=\"\"><strong>\u6700\u5c0f\uff1a<\/strong>\u82b1\u8cbb\u6700\u5c11\uff08\u9577\u5ea6\u6700\u77ed\uff09\u3002<\/li>\n\n\n\n<li class=\"\"><strong>\u751f\u6210\uff1a<\/strong>\u9023\u63a5\u4e86\u6240\u6709\u7684\u9ede\u3002<\/li>\n\n\n\n<li class=\"\"><strong>\u6a39\uff1a<\/strong>\u56e0\u70ba\u6c92\u6709\u7e5e\u5708\u5708\uff08\u8ff4\u8def\uff09\uff0c\u770b\u8d77\u4f86\u50cf\u6a39\u679d\u4e00\u6a23\u5206\u5c94\u51fa\u53bb\u3002<\/li>\n<\/ul>\n<\/li>\n<\/ul>\n\n\n\n<h4 class=\"wp-block-heading\">\u7b2c\u4e94\u968e\u6bb5\uff1a\u9664\u932f\u8207\u6311\u6230<\/h4>\n\n\n\n<p class=\"\">\u5728\u9019\u500b\u968e\u6bb5\uff0c\u6211\u5011\u8981\u5f15\u5165\u771f\u5be6\u4e16\u754c\u7684\u6311\u6230\u3002\u6211\u5011\u8981\u8b93\u5b69\u5b50\u7406\u89e3\uff0c\u6709\u6642\u5019\u300c\u7701\u9322\uff08\u6700\u5c0f\u751f\u6210\u6a39\uff09\u300d\u4e0d\u4e00\u5b9a\u4ee3\u8868\u300c\u65b9\u4fbf\u300d\u6216\u300c\u5feb\u901f\u300d\u3002<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li style=\"line-height:2\" class=\"\"><strong>\u6311\u6230\u4e00\uff1a\u7aae\u904a\u80cc\u5305\u5ba2 vs. \u8f49\u6a5f\u60e1\u5922 (Travel Budget vs. Convenience)<\/strong>\n<ul class=\"wp-block-list\">\n<li class=\"\"><strong>\u60c5\u5883\uff1a<\/strong>\u300c\u5047\u8a2d\u6709\u4e00\u5bb6\u300e\u5c0f\u6c23\u822a\u7a7a\u516c\u53f8\u300f\uff0c\u70ba\u4e86\u7701\u6cb9\u9322\uff0c\u4ed6\u5011\u6c7a\u5b9a\u7167\u8457\u6211\u5011\u525b\u525b\u756b\u7684\u300e\u6700\u5c0f\u751f\u6210\u6a39\u300f\u5730\u5716\u4f86\u958b\u98db\u6a5f\u822a\u7dda\u3002\u56e0\u70ba\u9019\u6a23\u7e3d\u98db\u884c\u8ddd\u96e2\u6700\u77ed\uff0c\u6700\u7701\u6cb9\u3002\u300d<\/li>\n\n\n\n<li class=\"\"><strong>\u63d0\u554f\uff1a<\/strong>\u300c\u5982\u679c\u4f60\u60f3\u5f9e\u5730\u5716\u6700\u5de6\u908a\u7684\u57ce\u5e02\uff0c\u98db\u5230\u6700\u53f3\u908a\u7684\u57ce\u5e02\u53bb\u65c5\u884c\uff0c\u770b\u8457\u9019\u5f35\u5730\u5716\uff0c\u4f60\u6703\u767c\u73fe\u4ec0\u9ebc\u554f\u984c\uff1f\u300d<\/li>\n\n\n\n<li class=\"\"><strong>\u767c\u73fe\uff1a<\/strong>\u5b69\u5b50\u6703\u767c\u73fe\u53ef\u80fd\u8981\u8f49\u6a5f\u5f88\u591a\u6b21\uff01\u56e0\u70ba\u70ba\u4e86\u7701\u92ea\u8def\u7684\u9322\uff0c\u4e2d\u9593\u7684\u6377\u5f91\u90fd\u88ab\u6211\u5011\u300c\u7701\u300d\u6389\u4e86\uff0c\u5fc5\u9808\u7e5e\u8457\u6a39\u679d\u72c0\u7684\u8def\u7dda\u98db\u3002<\/li>\n\n\n\n<li class=\"\"><strong>\u7e3d\u7d50\uff1a<\/strong>\u5c0d\u822a\u7a7a\u516c\u53f8\u4f86\u8aaa\uff0c\u9019\u662f\u6210\u672c\u6700\u4f4e\u7684\u84cb\u6cd5\uff08\u6700\u5c0f\u751f\u6210\u6a39\uff09\uff1b\u4f46\u5c0d\u8d95\u6642\u9593\u7684\u65c5\u5ba2\u4f86\u8aaa\uff0c\u9019\u4e0d\u662f\u6700\u597d\u7684\u8def\u7dda\u3002\u9019\u5c31\u662f\u70ba\u4ec0\u9ebc\u771f\u5be6\u4e16\u754c\u7684\u6a5f\u7968\u548c\u8def\u7dda\u898f\u5283\uff0c\u4e0d\u80fd\u53ea\u770b\u300c\u7e3d\u9577\u5ea6\u300d\uff0c\u9084\u8981\u8003\u616e\u300c\u65b9\u4e0d\u65b9\u4fbf\u300d\u3002<\/li>\n<\/ul>\n<\/li>\n<\/ul>\n\n\n\n<ul style=\"line-height:2\" class=\"wp-block-list\">\n<li style=\"line-height:2\" class=\"\"><strong>\u6311\u6230\u4e8c\uff1a\u62ab\u85a9\u5916\u9001\u54e1\u7684\u60e1\u5922 (The Travelling Salesman Problem)<\/strong>\n<ul class=\"wp-block-list\">\n<li class=\"\"><strong>\u60c5\u5883\uff1a<\/strong>\u300c\u606d\u559c\u5e02\u9577\uff0c\u4f60\u7528\u6700\u5c11\u7684\u77f3\u982d\u628a\u8def\u92ea\u597d\u4e86\uff01\u73fe\u5728\uff0c\u57ce\u5e02\u88e1\u7684\u62ab\u85a9\u5e97\u958b\u5e55\u4e86\u3002\u5916\u9001\u54e1\u9a0e\u8457\u6a5f\u8eca\uff0c\u8981\u4e00\u6b21\u628a\u62ab\u85a9\u9001\u5230\u5730\u5716\u4e0a\u7684\u6bcf\u4e00\u6236\u4eba\u5bb6\uff0c\u6700\u5f8c\u56de\u5230\u62ab\u85a9\u5e97\u300d\u3002<\/li>\n\n\n\n<li class=\"\"><strong>\u5be6\u9a57\uff1a<\/strong>\u300c\u8acb\u4f60\u62ff\u51fa\u4f60\u7684\u624b\u6307\u982d\u7576\u4f5c\u6a5f\u8eca\uff0c\u8a66\u8457\u5728\u6211\u5011\u525b\u525b\u92ea\u597d\u7684\u300e\u7701\u9322\u9053\u8def\uff08\u6700\u5c0f\u751f\u6210\u6a39\uff09\u300f\u4e0a\u8dd1\u8dd1\u770b\u3002\u898f\u5247\u662f\uff1a\u4f60\u8981\u62dc\u8a2a\u6bcf\u4e00\u5bb6\uff0c\u4f46\u76e1\u91cf\u4e0d\u8981\u8d70\u56de\u982d\u8def\u3002\u300d<\/li>\n\n\n\n<li class=\"\"><strong>\u767c\u73fe\uff08\u885d\u7a81\u9ede\uff09\uff1a<\/strong>\u5b69\u5b50\u6703\u767c\u73fe\u975e\u5e38\u56f0\u96e3\uff01\u56e0\u70ba\u6700\u5c0f\u751f\u6210\u6a39\u6709\u5f88\u591a\u300c\u6a39\u679d\u7684\u672b\u7aef\uff08\u6b7b\u5df7\u5b50\uff09\u300d\u3002\n<ul class=\"wp-block-list\">\n<li class=\"\">\u5916\u9001\u54e1\u9a0e\u9032\u53bb\u9001\u5b8c\u62ab\u85a9\u5f8c\uff0c\u5fc5\u9808\u300c\u539f\u8def\u6298\u8fd4\u300d\u624d\u80fd\u51fa\u4f86\uff0c\u518d\u53bb\u9001\u4e0b\u4e00\u5bb6\u3002<\/li>\n\n\n\n<li class=\"\">\u9019\u5c0d\u92ea\u8def\u4f86\u8aaa\u5f88\u7701\u77f3\u982d\uff0c\u4f46\u5c0d\u5916\u9001\u54e1\u4f86\u8aaa\u975e\u5e38\u6d6a\u8cbb\u6cb9\u548c\u6642\u9593\uff01<\/li>\n<\/ul>\n<\/li>\n<\/ul>\n<\/li>\n\n\n\n<li class=\"\"><strong>\u7e3d\u7d50\u8207\u77e5\u8b58\u9ede\uff1a<\/strong>\n<ul class=\"wp-block-list\">\n<li class=\"\"><strong>\u5b9a\u7fa9\u554f\u984c\uff1a<\/strong>\u9019\u500b\u300c\u5982\u4f55\u898f\u5283\u8def\u7dda\uff0c\u624d\u80fd\u62dc\u8a2a\u6bcf\u4e00\u500b\u9ede\u518d\u56de\u5230\u539f\u9ede\uff0c\u800c\u4e14\u8def\u5f91\u6700\u77ed\u300d\u7684\u554f\u984c\uff0c\u96fb\u8166\u79d1\u5b78\u5bb6\u7a31\u4e4b\u70ba\u300c\u65c5\u884c\u63a8\u92b7\u54e1\u554f\u984c (Travelling Salesman Problem, TSP)\u300d\u3002<\/li>\n\n\n\n<li class=\"\"><strong>\u5340\u5206\u5dee\u7570\uff1a<\/strong>\n<ul class=\"wp-block-list\">\n<li class=\"\"><strong>\u6700\u5c0f\u751f\u6210\u6a39 (MST)\uff1a<\/strong>\u5e6b\u96fb\u529b\u516c\u53f8\u7701\u96fb\u7dda\u3001\u5e6b\u5e02\u9577\u7701\u92ea\u8def\u8cbb\uff08\u53ea\u8981\u9023\u901a\u5c31\u597d\uff0c\u4e0d\u7528\u7e5e\u5708\uff09\u3002<\/li>\n\n\n\n<li class=\"\"><strong>\u65c5\u884c\u63a8\u92b7\u54e1 (TSP)\uff1a<\/strong>\u5e6b\u7269\u6d41\u53f8\u6a5f\u3001\u822a\u7a7a\u90f5\u4ef6\u7701\u6cb9\u9322\uff08\u9700\u8981\u4e00\u500b\u9ad8\u6548\u7387\u7684\u8ff4\u5708\uff09\u3002<\/li>\n<\/ul>\n<\/li>\n\n\n\n<li class=\"\"><strong>\u672a\u89e3\u4e4b\u8b0e\uff1a<\/strong>\u4f60\u89ba\u5f97 TSP \u5f88\u96e3\u756b\u55ce\uff1f\u544a\u8a34\u4f60\u4e00\u500b\u79d8\u5bc6\uff0c\u5c0d\u65bc\u9019\u500b\u554f\u984c\uff0c\u96fb\u8166\u79d1\u5b78\u5bb6\u5230\u73fe\u5728\u9084\u6c92\u627e\u5230\u4e00\u500b\u300c\u5920\u5feb\u53c8\u4fdd\u8b49\u662f\u6700\u4f73\u89e3\u300d\u7684\u8d85\u7d1a\u516c\u5f0f\uff01\u9019\u53ef\u662f\u96fb\u8166\u754c\u6700\u96e3\u7684\u6311\u6230\u4e4b\u4e00\u5594\u3002<\/li>\n<\/ul>\n<\/li>\n<\/ul>\n\n\n\n<h3 class=\"wp-block-heading\">\u6559\u5b78\u89c0\u5bdf\u91cd\u9ede\u8868<\/h3>\n\n\n\n<figure class=\"wp-block-table\"><table class=\"has-fixed-layout\"><thead><tr><td><strong>\u89c0\u5bdf\u9ede<\/strong><\/td><td><strong>\u274c \u8f03\u7121\u6548\u7684\u53cd\u61c9 (\u53ea\u770b\u7d50\u679c)<\/strong><\/td><td><strong>\u2705 \u8f03\u6709\u6548\u7684\u5f15\u5c0e (\u5de5\u7a0b\u5e2b\u601d\u7dad)<\/strong><\/td><\/tr><\/thead><tbody><tr><td><strong>\u7576\u5b69\u5b50\u9023\u6210\u4e00\u500b\u5713\u5708\u6642<\/strong><\/td><td>\u300c\u932f\u4e86\uff0c\u4e0d\u80fd\u6709\u5713\u5708\u3002\u300d<\/td><td>\u300c\u770b\u9019\u88e1\uff0c\u5982\u679c\u6211\u5df2\u7d93\u53ef\u4ee5\u5f9eA\u5bb6\u8d70\u5230B\u5bb6\uff0c\u518d\u92ea\u9019\u689d\u8def\u662f\u4e0d\u662f\u5c31\u300e\u591a\u9918\u300f\u4e86\uff1f\u5e02\u9577\uff0c\u9019\u689d\u8def\u7684\u9322\u80fd\u4e0d\u80fd\u7701\u4e0b\u4f86\u53bb\u8cb7\u6ed1\u6c34\u9053\uff1f\u300d(\u5f37\u8abf\u907f\u514d\u8ff4\u8def Cycle)<\/td><\/tr><tr><td><strong>\u7576\u5b69\u5b50\u554f\u70ba\u4ec0\u9ebc\u4e0d\u92ea\u6377\u5f91<\/strong><\/td><td>\u300c\u56e0\u70ba\u90a3\u6a23\u77f3\u982d\u6703\u8b8a\u591a\u3002\u300d<\/td><td>\u300c\u5982\u679c\u4f60\u662f\u65c5\u5ba2\uff0c\u4f60\u6703\u5f88\u60f3\u8981\u9019\u689d\u6377\u5f91\u3002\u4f46\u4f60\u662f\u5e02\u9577\uff0c\u9019\u689d\u8def\u8981\u591a\u82b1\u5e02\u6c11 5 \u5104\u5143\u3002\u4f60\u73fe\u5728\u8981\u9078\u64c7\u300e\u8b93\u5927\u5bb6\u65b9\u4fbf\u300f\u9084\u662f\u300e\u5e6b\u5927\u5bb6\u7701\u7a05\u91d1\u300f\uff1f\u96fb\u8166\u79d1\u5b78\u5c31\u662f\u5728\u505a\u9019\u7a2e\u53d6\u6368\u3002\u300d<\/td><\/tr><tr><td><strong>\u89e3\u91cb\u7269\u6d41\u8eca\u70ba\u4ec0\u9ebc\u4e0d\u80fd\u7528\u9019\u5f35\u5716<\/strong><\/td><td>\u300c\u56e0\u70ba\u6a39\u72c0\u5716\u6709\u6b7b\u8def\u3002\u300d<\/td><td>\u300c\u4f60\u8a66\u8457\u7528\u624b\u6307\u7576\u8ca8\u8eca\u958b\u958b\u770b\u3002\u4f60\u6703\u767c\u73fe\u4e00\u76f4\u8981\u300e\u5012\u8eca\u300f\u51fa\u4f86\u5c0d\u4e0d\u5c0d\uff1f\u6240\u4ee5\u9001\u8ca8\u7684\u8def\u7dda\uff08TSP\uff09\u8ddf\u92ea\u8def\u7684\u8def\u7dda\uff08MST\uff09\u662f\u4e0d\u4e00\u6a23\u7684\u6578\u5b78\u554f\u984c\u5594\uff01\u300d<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n<div class=\"wp-block-buttons is-layout-flex wp-block-buttons-is-layout-flex\">\n<div class=\"wp-block-button\"><a class=\"wp-block-button__link wp-element-button\" href=\"https:\/\/learndeeplytw.com\/game\/MinimalSpanningTree\/\" target=\"_blank\" rel=\"noreferrer noopener\">\u9019\u88e1\u6709\u5c0f\u904a\u6232\u5594<\/a><\/div>\n<\/div>\n\n\n\n<div style=\"height:100px\" aria-hidden=\"true\" class=\"wp-block-spacer\"><\/div>\n\n\n\n<div class=\"wp-block-columns is-layout-flex wp-container-core-columns-is-layout-28f84493 wp-block-columns-is-layout-flex\">\n<div class=\"wp-block-column is-layout-flow wp-block-column-is-layout-flow\"><\/div>\n\n\n\n<div class=\"wp-block-column is-layout-flow wp-block-column-is-layout-flow\"><\/div>\n<\/div>\n","protected":false},"excerpt":{"rendered":"<p>\u5728\u96fb\u8166\u79d1\u5b78\u4e2d\uff0c\u6709\u4e00\u500b\u5f88\u7d93\u5178\u7684\u554f\u984c\u53eb\u505a\u300c\u6700\u5c0f\u751f\u6210\u6a39 (Minimal Spanning Tree)\u300d\u3002\u807d\u8d77\u4f86\u5f88\u6df1 [&hellip;]<\/p>\n","protected":false},"author":2,"featured_media":789,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"nf_dc_page":"","footnotes":""},"categories":[9,18],"tags":[44,26,45,41,24],"class_list":["post-787","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-cs-unplugged","category-algorithms","tag-minimal-spanning-tree","tag-26","tag-45","tag-41","tag-24"],"blocksy_meta":[],"_links":{"self":[{"href":"https:\/\/learndeeplytw.com\/zh_tw\/wp-json\/wp\/v2\/posts\/787","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/learndeeplytw.com\/zh_tw\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/learndeeplytw.com\/zh_tw\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/learndeeplytw.com\/zh_tw\/wp-json\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/learndeeplytw.com\/zh_tw\/wp-json\/wp\/v2\/comments?post=787"}],"version-history":[{"count":3,"href":"https:\/\/learndeeplytw.com\/zh_tw\/wp-json\/wp\/v2\/posts\/787\/revisions"}],"predecessor-version":[{"id":799,"href":"https:\/\/learndeeplytw.com\/zh_tw\/wp-json\/wp\/v2\/posts\/787\/revisions\/799"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/learndeeplytw.com\/zh_tw\/wp-json\/wp\/v2\/media\/789"}],"wp:attachment":[{"href":"https:\/\/learndeeplytw.com\/zh_tw\/wp-json\/wp\/v2\/media?parent=787"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/learndeeplytw.com\/zh_tw\/wp-json\/wp\/v2\/categories?post=787"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/learndeeplytw.com\/zh_tw\/wp-json\/wp\/v2\/tags?post=787"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}