{"id":3498,"date":"2010-06-07T12:44:51","date_gmt":"2010-06-07T04:44:51","guid":{"rendered":"https:\/\/case.ntu.edu.tw\/blog\/?p=3498"},"modified":"2017-03-31T23:21:22","modified_gmt":"2017-03-31T15:21:22","slug":"%e3%80%90%e9%9b%bb%e8%85%a6%e8%88%87%e6%95%b8%e5%ad%b8%e3%80%91%e4%bf%84%e7%be%85%e6%96%af%e6%96%b9%e5%a1%8a%e5%af%a6%e5%9c%a8%e6%9c%89%e5%a4%a0%e9%9b%a3%ef%bc%81%ef%bc%9f","status":"publish","type":"post","link":"https:\/\/case.ntu.edu.tw\/blog\/?p=3498","title":{"rendered":"\u3010\u96fb\u8166\u8207\u6578\u5b78\u3011\u4fc4\u7f85\u65af\u65b9\u584a\u5be6\u5728\u6709\u5920\u96e3\uff01\uff1f"},"content":{"rendered":"<p><strong><span style=\"color: #800000;\">\u25a0 \u4fc4\u7f85\u65af\u65b9\u584a\u770b\u8d77\u4f86\u53ea\u662f\u4e00\u5806\u4e0d\u505c\u6389\u4e0b\u4f86\u7684\u78da\u584a\uff0c\u4f46\u5c31\u96fb\u8166\u79d1\u5b78\u7684\u610f\u7fa9\u4e0a\uff0c\u537b\u662f\u9060\u6bd4\u6578\u7368\u8981\u56f0\u96e3\u7684\u771f\u6b63\u300c\u76ca\u667a\u904a\u6232\u300d\u3002\u5c0d\u65bc\u6d89\u53ca\u6642\u9593\u800c\u4e14\u53ef\u80fd\u6c92\u6709\u6700\u4f73\u89e3\u7b54\u7684\u554f\u984c\uff0c\u4eba\u985e\u505a\u5f97\u4e0d\u898b\u5f97\u6703\u6bd4\u96fb\u8166\u5dee\u3002<\/span><\/strong><\/p>\n<p><img fetchpriority=\"high\" decoding=\"async\" class=\"alignnone size-full wp-image-3500\" title=\"schmaeche@flicker\" src=\"http:\/\/case.ntu.edu.tw\/blog\/wp-content\/uploads\/2010\/06\/schmaeche@flicker.jpg\" alt=\"schmaeche@flicker\" width=\"655\" height=\"414\" srcset=\"https:\/\/case.ntu.edu.tw\/blog\/wp-content\/uploads\/2010\/06\/schmaeche@flicker.jpg 1024w, https:\/\/case.ntu.edu.tw\/blog\/wp-content\/uploads\/2010\/06\/schmaeche@flicker-800x505.jpg 800w\" sizes=\"(max-width: 655px) 100vw, 655px\" \/><\/p>\n<p><strong>\u64b0\u6587<\/strong> \u2223 \u5f35\u8b7d\u9418<\/p>\n<p>\u81ea\u5f9e1984\u5e74\u8607\u4fc4\u79d1\u5b78\u9662\u7684<a href=\"http:\/\/en.wikipedia.org\/wiki\/Alexey_Pajitnov\" target=\"_blank\">Alexey Pajitnov<\/a>\u5275\u9020\u4e86\u4fc4\u7f85\u65af\u65b9\u584a\u5f8c\uff0c\u5e7e\u4e4e\u6240\u6709\u904b\u7528\u5230\u96fb\u5b50\u8a08\u7b97\u6a5f\u7684\u8a2d\u5099\u90fd\u6709\u5b83\u7684\u5f71\u5b50\uff1a\u624b\u6a5f\u3001\u904a\u6232\u6a5f\u3001\u96fb\u5b50\u8a5e\u5178\uff0c\u751a\u81f3\u6709\u597d\u4e8b\u8005\u85c9\u7531\u63a7\u5236\u5927\u6a13\u6bcf\u9593\u623f\u88e1\u7684\u71c8\u5149\u4f86\u904a\u73a9\u3002\u4e8c\u5341\u591a\u5e74\u4f86\u4fc4\u7f85\u65af\u65b9\u584a\u7684\u6839\u672c\u7d50\u69cb\u4e26\u6c92\u6709\u4ec0\u9ebc\u592a\u5927\u7684\u6539\u8b8a\u2014\uff0d\u5171\u4e03\u7a2e\u9762\u7a4d\u76f8\u540c\u7684\u65b9\u584a\u96a8\u6a5f\u7684\u5f9e\u4e0a\u7aef\u6389\u843d\uff0c\u800c\u73a9\u5bb6\u5c31\u662f\u8981\u5728\u6709\u9650\u7684\u6642\u9593\u88e1\u5c07\u9019\u4e00\u7cfb\u5217\u7684\u65b9\u584a\u5806\u758a\u4e26\u76e1\u53ef\u80fd\u7684\u586b\u6eff\u6bcf\u4e00\u5217\u65b9\u584a\u5806\u3002<\/p>\n<p>\u4f46\uff0c\u4f60\u6709\u6c92\u6709\u60f3\u904e\uff0c\u4fc4\u7f85\u65af\u65b9\u584a\u6709\u591a\u96e3\u5462\uff1f \u8070\u660e\u7684\u4f60\u4e5f\u8a31\u60f3\u4e86\u4e00\u6703\u5152\u5c31\u767c\u89ba\uff0c\u9084\u6709\u4e00\u500b\u66f4\u6839\u672c\u7684\u554f\u984c\uff1a\u300c\u600e\u9ebc\u6a23\u5b9a\u7fa9\u56f0\u96e3\u8207\u5426\u5462\uff1f\u300d<\/p>\n<p>\u5728\u8a08\u7b97\u6a5f\u79d1\u5b78\u88e1\uff0c\u4e00\u500b\u554f\u984c\u7684\u56f0\u96e3\u5ea6\u7531\u89e3\u6c7a\u5b83\u6240\u9700\u7684\u6642\u9593\u800c\u5b9a\uff0c\u7576\u7136\uff0c\u6211\u5011\u5728\u9019\u88e1\u6240\u8ac7\u8ad6\u7684\u662f\u53ef\u4ee5\u88ab\u89e3\u7b54\u7684\u554f\u984c\uff0c\u50cf\u662f\u300c103\u662f\u4e0d\u662f\u8cea\u6578\uff1f\u300d\u4e4b\u985e\u5b58\u5728\u89e3\u7b54\u7684\u554f\u984c\uff0c\u800c\u56f0\u64fe\u8a08\u7b97\u6a5f\u5b78\u5bb6\u5df2\u4e45\u7684\u554f\u984c\u4e4b\u4e00\uff0c\u4fbf\u662f\u300c<a href=\"http:\/\/en.wikipedia.org\/wiki\/NP_%28complexity%29\" target=\"_blank\">NP\u554f\u984c<\/a>\u300d\uff0c\u4ea6\u5373\u300c\u672a\u78ba\u5b9a\u80fd\u5426\u5728\u591a\u9805\u5f0f\u8868\u5217\u7684\u6642\u9593\u7dad\u5ea6\u88e1\u89e3\u6c7a\u7684\u554f\u984c\u300d\uff0c\u800c\u591a\u9805\u5f0f\u4fbf\u662f\u50cf\u662f<span style=\"widows: 2; text-transform: none; text-indent: 0px; border-collapse: separate; font: medium Arial; white-space: normal; orphans: 2; letter-spacing: normal; color: #000000; word-spacing: 0px; -webkit-border-horizontal-spacing: 0px; -webkit-border-vertical-spacing: 0px; -webkit-text-decorations-in-effect: none; -webkit-text-size-adjust: auto; -webkit-text-stroke-width: 0px;\"><span style=\"font-family: 'Times New Roman'; font-size: 16px;\"><span style=\"font-family: 'Liberation Serif';\">5X<\/span><span style=\"font-family: 'Liberation Serif';\"><sup>3<\/sup><\/span><span style=\"font-family: 'Liberation Serif';\">+4X<\/span><span style=\"font-family: 'Liberation Serif';\"><sup>2<\/sup><\/span><span style=\"font-family: 'Liberation Serif';\">+2X<\/span><\/span><\/span>\u4e4b\u985e\u7684\u5f0f\u5b50\uff0c\u800c\u8b8a\u6578X\u53ef\u4ee5\u88ab\u8996\u70ba\u6211\u5011\u8f38\u5165\u7684\u8cc7\u6599\u91cf\u3002\u4e5f\u8a31\u4f60\u6703\u554f\uff0c\u5373\u4f7f\u50cf\u4e0a\u8ff0\u7684\u5f0f\u5b50\uff0c\u6211\u5011\u4ee3\u5165X\uff1d100\uff0c\u5c31\u5df2\u7d93\u662f5040200\u9019\u7a2e\u6578\u5b57\u4e86\uff0c\u70ba\u4f55\u8981\u4ee5\u300c\u591a\u9805\u5f0f\u6642\u9593\u300d\u505a\u70ba\u6a19\u6e96\u5462\uff1f<\/p>\n<p><!--more--><\/p>\n<p>\u7406\u7531\u5176\u5be6\u975e\u5e38\u7684\u7c21\u55ae\uff0c\u6211\u5011\u770b\u770b\u6bd4\u8f03\u7684\u5716\u89e3\u5c31\u77e5\u9053\u4e86\u2014\u2014\u56e0\u70ba\u591a\u9805\u5f0f\u6642\u9593\u9084\u53ea\u662f\u5c0f\u5152\u79d1\u800c\u5df2\uff01\uff01\u9084\u6709\u50cf\u662f\u300c<span style=\"widows: 2; text-transform: none; text-indent: 0px; border-collapse: separate; font: medium Arial; white-space: normal; orphans: 2; letter-spacing: normal; color: #000000; word-spacing: 0px; -webkit-border-horizontal-spacing: 0px; -webkit-border-vertical-spacing: 0px; -webkit-text-decorations-in-effect: none; -webkit-text-size-adjust: auto; -webkit-text-stroke-width: 0px;\"><span style=\"font-family: 'Times New Roman'; font-size: 16px;\"><span style=\"font-family: 'Liberation Serif';\">2<\/span><span style=\"font-family: 'Liberation Serif';\"><sup>X<\/sup><\/span><\/span><\/span>\u300d\u9019\u7a2e\u6307\u6578\u6642\u9593\u7684\u602a\u7378\u5b58\u5728\uff0c\u6240\u4ee5\u6211\u5011\u8aaaNP\u554f\u984c\u53ef\u80fd\u662f\u6975\u70ba\u56f0\u96e3\u7684\uff0c\u56e0\u70ba\u6211\u5011\u4e0d\u592a\u53ef\u80fd\u627e\u5230\u591a\u9805\u5f0f\u6642\u9593\u7684\u89e3\u6cd5\uff01<\/p>\n<figure id=\"attachment_3502\" aria-describedby=\"caption-attachment-3502\" style=\"width: 512px\" class=\"wp-caption alignnone\"><a href=\"http:\/\/case.ntu.edu.tw\/blog\/wp-content\/uploads\/2010\/06\/timecomplexity.png\"><img decoding=\"async\" class=\"size-full wp-image-3502  \" title=\"timecomplexity\" src=\"http:\/\/case.ntu.edu.tw\/blog\/wp-content\/uploads\/2010\/06\/timecomplexity.png\" alt=\"timecomplexity\" width=\"512\" height=\"340\" srcset=\"https:\/\/case.ntu.edu.tw\/blog\/wp-content\/uploads\/2010\/06\/timecomplexity.png 640w, https:\/\/case.ntu.edu.tw\/blog\/wp-content\/uploads\/2010\/06\/timecomplexity-600x398.png 600w\" sizes=\"(max-width: 512px) 100vw, 512px\" \/><\/a><figcaption id=\"caption-attachment-3502\" class=\"wp-caption-text\">\u4fc4\u7f85\u65af\u65b9\u584a\u7684\u6642\u9593\u8907\u96dc\u6027\uff08\u88fd\u5716\uff1a\u5f35\u8b7d\u9418\uff09<\/figcaption><\/figure>\n<p>\u73fe\u5728\u6211\u5011\u56de\u5230\u4fc4\u7f85\u65af\u65b9\u584a\u4e0a\uff0c\u4e5f\u8a31\u4f60\u5df2\u7d93\u731c\u5230\uff0c\u4fc4\u7f85\u65af\u65b9\u584a\u5df2\u88ab\u8b49\u660e\u662f\u4e00\u500bNP\u554f\u984c\uff08\u800c\u4e14\u9084\u662fNP\u554f\u984c\u88e1\u7279\u5225\u96e3\u7684<a href=\"http:\/\/zh.wikipedia.org\/zh-tw\/NP%E5%AE%8C%E5%85%A8\" target=\"_blank\">NP-Complete\u554f\u984c<\/a>\uff09\uff0c\u4e26\u4e14\u8b49\u660e\u7684\u79d1\u5b78\u5bb6\u9084\u662f\u4ee5\u8f03\u7c21\u55ae\u7684\u7248\u672c\uff0d\u2014\u6240\u6709\u6389\u843d\u65b9\u584a\u7684\u5148\u5f8c\u9806\u5e8f\u7686\u5df2\u5f97\u77e5\u7684\u72c0\u6cc1\u4e0b\u6c42\u8b49\u7684\uff0c\u6240\u4ee5\u5be6\u969b\u4e0a\u5a1b\u6a02\u7528\u7684\u7248\u672c\u53ea\u6709\u53ef\u80fd\u66f4\u96e3\u800c\u5df2\uff01<\/p>\n<p>\u4e0d\u904e\uff0c\u79d1\u5b78\u5bb6\u7684\u76ee\u6a19\u662f\u6975\u5927\u5316\u6d88\u53bb\u7684\u5217\uff0c\u800c\u4eba\u985e\u5728\u904a\u73a9\u7684\u6642\u5019\uff0c\u4e26\u4e0d\u662f\u4f9d\u7167\u6b64\u4e00\u6a19\u6e96\u9032\u884c\u7684\u3002\u6211\u5011\u501a\u9760\u555f\u767c\u5f0f\u7684\u6f14\u7b97\u6cd5\uff08Heuristic Algorithm\uff09\uff0c\u4e5f\u5c31\u662f\u8aaa\uff0c<strong>\u6211\u5011\u5c0b\u6c42\u7684\u4e26\u975e\u6700\u4f73\u89e3\u3002<\/strong>\u800c\u4e5f\u8a31\u5c31\u662f\u56e0\u70ba\u9019\u4e00\u9ede\uff0c\u6240\u4ee5\u4eba\u5011\u6703\u6301\u7e8c\u7684\u73a9\u4e0b\u53bb\uff08\u56e0\u70ba\u6c92\u6709\u5fc5\u52dd\u7684\u73a9\u6cd5\uff09\u3002<\/p>\n<p>\u53e6\u5916\u4e00\u9ede\u503c\u5f97\u6ce8\u610f\u7684\u662f\u6642\u9593\u6027\u3002\u8a31\u591a\u904a\u6232\u90fd\u6709\u6642\u9593\u7684\u9650\u5236\uff0c\u4fc4\u7f85\u65af\u65b9\u584a\u4e5f\u4e0d\u4f8b\u5916\uff0c\u73a9\u5bb6\u8981\u4e0d\u65b7\u5730\u62b5\u6297\u6642\u9593\u58d3\u529b\uff0c\u76e1\u53ef\u80fd\u907f\u514d\u904a\u6232\u7d50\u675f\u3002\u8a66\u60f3\uff0c\u82e5\u4f60\u53ef\u4ee5\u73a9\u4e00\u500b\u7121\u9650\u6162\u7684\u4fc4\u7f85\u65af\u65b9\u584a\u904a\u6232\uff0c\u751a\u81f3\u53ef\u4ee5\u62ff\u7d19\u7b46\u6216\u8005\u53e6\u5916\u8dd1\u500b\u7a0b\u5f0f\u4f86\u904b\u7b97\u4e0b\u4e00\u6b65\u600e\u9ebc\u505a\u624d\u300c\u6700\u6b63\u78ba\u300d\uff0c\u90a3\u9ebc\u60f3\u5fc5\u61c9\u8a72\u5f88\u7121\u804a\u5427\uff1f<\/p>\n<p>\u4e26\u975e\u6240\u6709\u5ee3\u53d7\u6b61\u8fce\u7684\u904a\u6232\u90fd\u662f\u56f0\u96e3\u7684\uff0c\u50cf\u662f\u6578\u7368\u5c31\u4e0d\u662f\u3002\u5f35\u6d77\u6f6e\u6559\u6388\u5728\u300a\u8aaa\u6578\u300b\u4e00\u66f8\u4e2d\u66fe\u7d93\u63d0\u5230\uff0c\u6578\u7368\u9019\u7a2e\u6771\u897f\uff0c\u5728\u6578\u5b78\u7684\u610f\u7fa9\u4e0a\u5c0d\u65bc\u4eba\u985e\u7684\u667a\u6167\u6c92\u6709\u8ca2\u737b\uff0c\u5145\u5176\u91cf\u662f\u6253\u767c\u6642\u9593\u7528\u7684\u3002\u4e5f\u8a31\u9019\u6709\u9ede\u4ee4\u4eba\u610f\u5916\uff0c\u5e7e\u5e74\u524d\u5927\u8857\u5c0f\u5df7\u90a3\u4e9b\u57cb\u9996\u5831\u7d19\u3001\u751a\u81f3\u71b1\u8877\u5230\u8cfc\u8cb7\u5c08\u9580\u51fa\u7248\u54c1\u7684\u4eba\u5011\u82b1\u8cbb\u90a3\u9ebc\u591a\u6642\u9593\u7684\u904a\u6232\uff0c\u8207\u5340\u5340\u7684\u4fc4\u7f85\u65af\u65b9\u584a\u76f8\u6bd4\uff0c\u7adf\u7136\u662f\u76f8\u5c0d\u7c21\u55ae\u7684\uff1f<\/p>\n<p>?<\/p>\n<pre><span style=\"color: #333333;\">\u5ef6\u4f38\u95b1\u8b80\uff1a<\/span><a href=\"http:\/\/www.liacs.nl\/~kosters\/tetris\/tetr.pdf\" target=\"_blank\"><span style=\"color: #333333;\">Tetris is Hard, Made Easy<\/span><\/a><span style=\"color: #333333;\">\uff08Ron Breukelaar, Hendrik Jan Hoogeboom, and Walter A. Kosters from Universiteit Leiden \u8377\u862d\u840a\u9813\u5927\u5b78\u96fb\u8166\u79d1\u5b78\u7814\u7a76\u4e2d\u5fc3\u8ad6\u6587\uff09<\/span><\/pre>\n<p><strong><span style=\"color: #003366;\">\u8cac\u4efb\u7de8\u8f2f\uff1aMissZoe<\/span><\/strong><br \/>\n<a href=\"http:\/\/www.facebook.com\/sharer.php\" type=\"box_count\" name=\"fb_share\">\u5206\u4eab\u5230facebook <\/a><\/p>\n<p><script src=\"http:\/\/static.ak.fbcdn.net\/connect.php\/js\/FB.Share\"><\/script><\/p>\n","protected":false},"excerpt":{"rendered":"<p>\u25a0 \u4fc4\u7f85\u65af\u65b9\u584a\u770b\u8d77\u4f86\u53ea\u662f\u4e00\u5806\u4e0d\u505c\u6389\u4e0b\u4f86\u7684<\/p>\n","protected":false},"author":20,"featured_media":0,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1023,3293,148],"tags":[345,2251,81,346,344],"aioseo_notices":[],"jetpack_featured_media_url":"","_links":{"self":[{"href":"https:\/\/case.ntu.edu.tw\/blog\/index.php?rest_route=\/wp\/v2\/posts\/3498"}],"collection":[{"href":"https:\/\/case.ntu.edu.tw\/blog\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/case.ntu.edu.tw\/blog\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/case.ntu.edu.tw\/blog\/index.php?rest_route=\/wp\/v2\/users\/20"}],"replies":[{"embeddable":true,"href":"https:\/\/case.ntu.edu.tw\/blog\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=3498"}],"version-history":[{"count":15,"href":"https:\/\/case.ntu.edu.tw\/blog\/index.php?rest_route=\/wp\/v2\/posts\/3498\/revisions"}],"predecessor-version":[{"id":18447,"href":"https:\/\/case.ntu.edu.tw\/blog\/index.php?rest_route=\/wp\/v2\/posts\/3498\/revisions\/18447"}],"wp:attachment":[{"href":"https:\/\/case.ntu.edu.tw\/blog\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=3498"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/case.ntu.edu.tw\/blog\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=3498"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/case.ntu.edu.tw\/blog\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=3498"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}