\u6f14\u7b97\u6cd5\u8a2d\u8a08\u65b9\u6cd5
\u9010\u6b65\u6539\u826f\u6cd5:\u53ea\u4f7f\u7528\u5faa\u5e8f,\u9078\u64c7,\u91cd\u8986\u4e09\u6b65\u9a5f\u8a2d\u8a08
\u5207\u5272\u5f81\u670d\u6cd5:\u5c07\u554f\u984c\u5207\u5272,\u5728\u4ee5\u76f8\u540c\u65b9\u5f0f\u8655\u7406,\u5728\u628a\u5404\u7d50\u679c\u5408\u4f75,\u9069\u7528\u5728\u905e\u8ff4
\u8caa\u5a6a\u6cd5:\u4e00\u7a2e\u968e\u6bb5\u6027\u65b9\u6cd5,\u4e3b\u8981\u6838\u5fc3\u70ba\u9078\u64c7\u7a0b\u5e8f,\u9069\u7528\u5728\u6709\u9650\u5236\u689d\u4ef6\u6700\u4f73\u5316\u7684\u7c21\u55ae\u554f\u984c
\u52d5\u614b\u898f\u756b\u6cd5\uff1a\u4e3b\u8981\u6838\u5fc3\u662f\u905e\u8ff4\u95dc\u4fc2\u5f0f\u548c\u6700\u4f73\u5316\u539f\u5247\uff0c\u9069\u7528\u5728\u6709\u9650\u5236\u689d\u4ef6\u6700\u4f73\u5316\u7684\u8907\u96dc\u554f\u984c
\u56de\u6eaf\u6cd5:\u63a1depth first search(\u6df1\u5ea6\u512a\u5148\u641c\u5c0b)\u5167\u542b\u905e\u8ff4\u7d50\u69cb\u53castate space tree(\u72c0\u614b\u7a7a\u9593\u6a39),\u9069\u7528\u5728\u6392\u5217\u6216\u90e8\u4efd\u96c6\u5408\u554f\u984c
\u5206\u679d\u9650\u5236\u6cd5:\u63a1breadth first search(\u5ee3\u5ea6\u512a\u5148\u641c\u5c0b)\u5167\u542b\u8ff4\u5708\u7d50\u69cb\u53castate space tree\u548cbounding(\u908a\u754c) function,\u9069\u7528\u5728\u6392\u5217\u6216\u90e8\u4efd\u96c6\u5408\u554f\u984c<\/p>\n\n\n\n
……………………………………………………..<\/p>\n\n\n\n
greedy method(\u8caa\u5a6a\u6cd5)<\/strong> \u5e38\u898b: optimal storage on tapes(\u6700\u4f73\u5316\u78c1\u5e36\u5132\u5b58\u554f\u984c):<\/strong> \u6700\u4f73\u5316\u4e2d\u592e\u8655\u7406\u5668\u898f\u5283\u554f\u984c:<\/strong> knapsack problem(\u80cc\u5305\u554f\u984c):<\/strong> job sequencing with deadline(\u6700\u5f8c\u671f\u9650\u5de5\u4f5c\u898f\u756b\u554f\u984c):<\/strong> minimum cost spanning tree(\u6700\u5c0f\u6210\u672c\u64f4\u5f35\u6a39):<\/strong> shortest path(\u6700\u77ed\u8ddd\u96e2\u8def\u5f91):<\/strong> ………………………………………………………..<\/p>\n\n\n\n dynamic programming(\u52d5\u614b\u898f\u5283\u6cd5)<\/strong> \u5e38\u898b: multistage graphs(\u591a\u968e\u5716\u5f62):<\/strong> all pairs of shortest path(\u4efb\u610f\u5169\u9ede\u6700\u77ed\u8ddd\u96e2\u8def\u5f91):<\/strong> 0\/1\u80cc\u5305\u554f\u984c:<\/strong> optiomal binary search tree(\u6700\u4f73\u4e8c\u5143\u641c\u5c0b\u6a39):<\/strong> the traveling saleperson problem(\u65c5\u884c\u63a8\u92b7\u54e1\u554f\u984c):<\/strong> backtracking(\u56de\u6eaf\u6cd5)<\/strong> \u61c9\u7528: ……………………………………………………………………………….<\/p>\n\n\n\n branch and bound(\u5206\u652f\u9650\u5236\u6cd5)<\/strong> \u61c9\u7528: \u6f14\u7b97\u6cd5\u8a2d\u8a08\u65b9\u6cd5\u9010\u6b65\u6539\u826f\u6cd5:\u53ea\u4f7f\u7528\u5faa\u5e8f,\u9078\u64c7,\u91cd\u8986\u4e09\u6b65\u9a5f\u8a2d\u8a08\u5207 …<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"fifu_image_url":"","fifu_image_alt":"","_jetpack_memberships_contains_paid_content":false,"footnotes":"","jetpack_publicize_message":"","jetpack_publicize_feature_enabled":true,"jetpack_social_post_already_shared":false,"jetpack_social_options":{"image_generator_settings":{"template":"highway","default_image_id":0,"font":"","enabled":false},"version":2}},"categories":[15],"tags":[],"class_list":["post-554","post","type-post","status-publish","format-standard","hentry","category-algorithm"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/systw.net\/note\/wp-json\/wp\/v2\/posts\/554","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/systw.net\/note\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/systw.net\/note\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/systw.net\/note\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/systw.net\/note\/wp-json\/wp\/v2\/comments?post=554"}],"version-history":[{"count":0,"href":"https:\/\/systw.net\/note\/wp-json\/wp\/v2\/posts\/554\/revisions"}],"wp:attachment":[{"href":"https:\/\/systw.net\/note\/wp-json\/wp\/v2\/media?parent=554"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/systw.net\/note\/wp-json\/wp\/v2\/categories?post=554"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/systw.net\/note\/wp-json\/wp\/v2\/tags?post=554"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}
\u8aaa\u660e:\u4e00\u7a2e\u968e\u6bb5\u6027\u65b9\u6cd5,\u5728\u5404\u968e\u6bb5\u9010\u4e00\u6aa2\u67e5\u4e00\u500b\u8f38\u5165\u662f\u5426\u9069\u5408\u52a0\u5165\u7b54\u6848\u4e2d,\u91cd\u8907\u7d93\u904e\u591a\u500b\u968e\u6bb5\u5f8c,\u5373\u53ef\u9806\u5229\u7372\u5f97\u6700\u4f73\u89e3
\u9069\u7528:\u5177\u6709\u9650\u5236\u689d\u4ef6\u7684\u6700\u4f73\u5316\u554f\u984c\u7684\u6f14\u7b97\u6cd5
\u5177\u6709\u9650\u5236\u689d\u4ef6\u7684\u6700\u4f73\u5316\u554f\u984c:\u53ef\u5c07\u554f\u984c\u6210\u70ba\u4e00\u500bobjective function(\u76ee\u6a19\u51fd\u6578)\u8207\u4e00\u4e9bconstraint(\u9650\u5236) function\u7684\u5f0f\u5b50
\u6838\u5fc3:stages(\u968e\u6bb5\u6027)\u7684\u8a2d\u8a08\u904e\u7a0b\uff0cselection procedure(\u9078\u64c7\u7a0b\u5e8f)
\u505a\u6cd5:\u6839\u64da\u554f\u984c\u7684\u76ee\u6a19\u51fd\u6578\u627e\u51fa\u4e00\u500b\u9078\u64c7\u7a0b\u5e8f,\u518d\u6839\u64da\u9019\u500b\u7a0b\u5e8f\u9078\u53d6\u6700\u4f73\u7684\u8f38\u5165,\u82e5\u53ef\u7b26\u5408\u9650\u5236\u5bd2\u6578\u5247\u52a0\u5165\u6b64\u8f38\u5165.\u5404\u968e\u6bb5\u53ef\u91cd\u8986\u4e0a\u8ff0\u4e26\u6700\u5f8c\u5f97\u5230\u6700\u4f73\u89e3<\/p>\n\n\n\n
optimal merge pattern(\u6700\u4f73\u5316\u5408\u4f75\u554f\u984c)<\/strong>
\u5c07n\u500b\u5df1\u6392\u5e8f\u8cc7\u6599\u6bb5run,\u5408\u4f75\u6210\u4e00\u500b\u5df1\u6392\u5e8f\u597d\u7684\u8cc7\u6599\u6bb5,\u540c\u6642\u9700\u8981\u8b93\u5408\u4f75\u6210\u672c\u6700\u5c0f<\/p>\n\n\n\n
\u5c07n\u500b\u7a0b\u5f0f\u5132\u5b58\u5230\u4e00\u500b\u78c1\u5e36\u4e0a,\u8b93\u5f80\u5f8c\u6bcf\u500b\u7a0b\u5f0f\u7684\u5e73\u5747\u5b58\u53d6\u6642\u9593\u80fd\u5920\u6700\u5c0f
\u524d\u9762\u7684\u7a0b\u5f0f\u9577\uff1d\u5f8c\u9762\u7a0b\u5f0f\u548c\u78c1\u5e36\u8b80\u5beb\u982d\u4e4b\u9593\u8ddd\u96e2,\u56e0\u6b64\u628a\u9577\u5ea6\u5c0f\u7684\u7a0b\u5f0f\u653e\u5728\u524d\u9762\u5373\u53ef\u8b93\u5e73\u5747\u5b58\u53d6\u6642\u9593\u6700\u5c0f(\u5c31\u662f\u7531\u5c0f\u5230\u5927\u6392\u5e8f)<\/p>\n\n\n\n
\u5982\u4f55\u5206\u914d\u4e2d\u592e\u8655\u7406\u5668\u7d66\u591a\u500b\u6b63\u7b49\u5f85\u57f7\u884c\u7684process\u5de5\u4f5c\u5143,\u8b93\u6240\u6709\u5de5\u4f5c\u5143\u7684\u5e73\u5747\u7b49\u5f85\u6642\u9593\u6700\u4f73
\u524d\u9762\u7684\u5de5\u4f5c\u5143\u57f7\u884c\u6642\u9593\uff1d\u5f8c\u9762\u5de5\u4f5c\u5143\u7684\u7b49\u5f85\u6642\u9593,\u56e0\u6b64\u5148\u57f7\u884c\u6642\u9593\u6700\u77ed\u7684\u5de5\u4f5c\u5143\u5373\u53ef\u8b93\u5e73\u5747\u7b49\u5f85\u6642\u9593\u6700\u5c0f(\u5c31\u662f\u7531\u5c0f\u5230\u5927\u6392\u5e8f)<\/p>\n\n\n\n
n\u500b\u7269\u54c1\u548c\u6709\u9650\u5236\u91cd\u91cf\u7684\u80cc\u5305,\u5404\u7269\u54c1\u6709\u91cd\u91cf\u548c\u5229\u6f64,\u627e\u51fa\u4e0d\u8d85\u904e\u80cc\u5305\u9650\u91cd\u4e0b\u653e\u5165\u7269\u54c1\u7684\u6700\u5927\u5229\u6f64(\u7269\u54c1\u53ef\u88ab\u5207\u5272)
\u5c07\u5229\u6f64\u91cd\u91cf\u6bd4\u6700\u5927\u7684\u9010\u4e00\u653e\u5165\u80cc\u5305,\u4f46\u4e0d\u8981\u8d85\u904e\u9650\u91cd\u5373\u53ef,\u8907\u96dc\u5ea6\u70baO(n*2\u5e95log n)<\/p>\n\n\n\n
n\u500b\u6709\u6700\u7d42\u671f\u9650\u548c\u5229\u6f64\u7684\u5de5\u4f5c,\u5728\u6700\u7d42\u671f\u9650\u4e0b,\u5b89\u6392\u5de5\u4f5c\u7684\u57f7\u884c\u9806\u5e8f\u4ee5\u7372\u5f97\u6700\u5927\u5229\u6f64<\/p>\n\n\n\n
\u627e\u51fa\u4e00\u5f35\u52a0\u6b0a\u5716\u88e1\u6240\u6709\u908a\u7684\u52a0\u6b0a\u7e3d\u548c\u662f\u6700\u5c0f\u7684\u64f4\u5f35\u6a39
kruskal\u65b9\u6cd5:
\u30001\u53d6\u6700\u5c0f\u52a0\u6b0a\u7684\u908a,\u82e5\u6b64\u908a\u4e0d\u6703\u5f62\u6210\u8ff4\u8def\u5247\u52a0\u5165\u7576\u6a39\u908a(2\u5e95log(e))
\u30002\u4e00\u76f4\u5230\u908a\u90fd\u53d6\u5b8c(e),\u6574\u500b\u8907\u96dc\u5ea6\u7b49\u7d1a\u70baO(e*2\u5e95log(e)),(\u4ee5\u908a\u70ba\u8655\u7406\u5c0d\u8c61)
\u3000\u7528\u5806\u7a4d\u7d50\u69cb\u8868\u793a\u908a\u7684\u52a0\u6b0a,\u53d6\u51fa\u6700\u5c0f\u52a0\u6b0a\u908a\u7684\u8907\u96dc\u5ea6\u70baO(2\u5e95log(e)),\u6700\u5dee\u60c5\u6cc1\u662f\u908a\u7684\u500b\u6578\u70ban*(n-1)\/2,\u4e5f\u5c31\u662f\u4efb\u5169\u9ede\u90fd\u6709\u4e00\u500b\u908a
prim\u65b9\u6cd5:\u5c07\u7b2c\u4e00\u9ede\u8996\u70ba\u6a39
\u30001\u6a39\u958b\u59cb\u9078\u9130\u8fd1\u6700\u5c0f\u52a0\u6b0a\u908a\u52a0\u5165\u5f62\u6210\u9ede\u591a\u4e00\u9ede\u7684\u6a39(n)
\u30002\u91cd\u8986\u6b65\u9a5f1\u76f4\u5230\u6210\u70ba\u5177\u6709N\u500b\u9ede\u7684\u6a39(n-1),(\u4ee5\u9ede\u70ba\u8655\u7406\u5c0d\u8c61)
sollin\u65b9\u6cd5:\u5404\u9ede\u8996\u70ba\u4e00\u6a39
\u30001\u5c0d\u6bcf\u9846\u6a39\u627e\u51fa\u8207\u5176\u5b83\u6a39\u9593\u6700\u5c0f\u52a0\u6b0a\u7684\u908a\u52a0\u5165\u7576\u6210\u6a39\u908a,\u5169\u6a39\u627e\u51fa\u7684\u908a\u76f8\u540c\u5247\u53bb\u9664\u5176\u4e2d\u4e00\u908a(e)
\u30002\u91cd\u8986\u6b65\u9a5f1\u5230\u53ea\u6709\u4e00\u68f5\u6a39(2\u5e95log(n))<\/p>\n\n\n\n
\u4e00\u9ede\u5230\u5176\u4ed6\u6240\u6709\u9ede\u4e4b\u9593\u7684\u6700\u77ed\u8def\u5f91\u8207\u8ddd\u96e2
dijkstra\u65b9\u6cd5\uff1a
\u30001………….
\u30002\u91cd\u8986\u6b65\u9a5f1(n-1),\u8907\u96dc\u5ea6\u70baO(N^2)
\u3000\u53ea\u9069\u7528\u908a\u4e0a\u52a0\u6b0a\u70ba\u6b63\u7684\u5716\u5f62
bellman-ford\u65b9\u6cd5(\u52d5\u614b\u898f\u756b\u6cd5)\uff1a
\u30001……….\u8003\u616e\u6240\u6709\u7684\u908a(E)
\u30002\u91cd\u8986\u6b65\u9a5f1(n-1),\u8907\u96dc\u5ea6\u70baO(n*e)
\u3000\u53ef\u9069\u7528\u908a\u4e0a\u52a0\u6b0a\u662f\u8ca0\u7684\u6240\u6709\u60c5\u6cc1<\/p>\n\n\n\n
\u9069\u7528:\u7121\u6cd5\u627e\u5230\u9078\u64c7\u7a0b\u5e8f\u7684\u8907\u96dc\u6700\u4f73\u5316\u554f\u984c
\u8aaa\u660e:\u9700\u8981\u5c07\u6700\u4f73\u5316\u554f\u984c\u7684\u76ee\u6a19\u5bd2\u6578\u8868\u793a\u6210\u70ba\u4e00\u500b\u905e\u8ff4\u95dc\u4fc2\u5f0f,\u4e26\u63a1forward approach(\u524d\u9032\u9806\u5e8f)\u6216backward approach\u8a08\u7b97
\u6703\u4f7f\u7528\u8868\u683c\u5c07\u5b50\u554f\u984c\u7684\u8a08\u7b97\u7d50\u679c\u52a0\u4ee5\u5132\u5b58,\u5728\u5f8c\u9762\u968e\u6bb5\u82e5\u8981\u7528\u5728\u5f9e\u8868\u683c\u4e2d\u53d6\u51fa\u4f7f\u7528
\u9700\u9075\u5b88\u6700\u4f73\u5316\u539f\u5247,\u4e5f\u5c31\u662f\u5404\u8f38\u5165\u7684\u8a08\u7b97\u90fd\u5fc5\u9808\u662f\u6839\u64da\u5176\u9918\u8f38\u5165\u7684\u6700\u4f73\u7d50\u679c\u518d\u9032\u4e00\u6b65\u8a08\u7b97
\u6838\u5fc3:principle of optimality(\u6700\u4f73\u5316\u539f\u5247),recurrence relation(\u905e\u8ff4\u95dc\u4fc2\u5f0f)<\/p>\n\n\n\n
longest common subsequence problem(\u6700\u9577\u5171\u540c\u5b50\u5b57\u4e32):<\/strong>
\u627e\u51fa\u5169\u500b\u5b57\u4e32\u4e2d\u5177\u6709\u6700\u5927\u9577\u5ea6\u7684\u5b50\u5b57\u4e32
\u505a\u6cd5:\u627e\u51fa\u905e\u8ff4\u95dc\u4fc2\u5f0f\u8207\u6700\u4f73\u5316\u539f\u5247,\u518d\u7528\u5f8c\u9000\u9806\u5e8f\u8a08\u7b97\u5373\u5f97\u6700\u4f73\u89e3
\u5047\u8a2dx=(x1,x2,…xm),y=(y1,y2,….yn)\u8868\u793a\u5169\u500b\u9577\u5ea6\u5206\u5225\u662fm\u8207n\u7684\u5b57\u4e32,len=\u5b57\u4e32x\u8207y\u6700\u9577\u5171\u540c\u5b50\u5b57\u4e32\u7684\u9577\u5ea6
\u905e\u8ff4\u95dc\u4fc2\u5f0f:len={
\u30000,if m=0 or n=o
\u3000len+1 , if m,n>0 and x_m=y_m
\u3000max(len,len) , if m,n>0 and x_m != y_m
\u57f7\u884c\u904e\u7a0b\u7684\u905e\u8ff4\u6a39\u6df1\u5ea6\u70baO(m+n)
\u5b50\u554f\u984c\u500b\u6578\u70baO(m*n),\u56e0\u57f7\u884c\u904e\u7a0b\u8981\u8003\u616e\u5169\u500b\u5b57\u4e32\u6240\u6709\u4e0d\u540c\u7684\u9577\u5ea6
\u6f14\u7b97\u6cd5\uff1a…..<\/p>\n\n\n\n
\u5728\u9802\u9ede\u5206\u70bak\u500b\u968e\u6bb5\u7684\u6709\u5411\u52a0\u6b0a\u5716\u4e2d,\u627e\u51fa\u7b2c\u4e00\u968e\u6bb5\u7684\u8d77\u59cb\u9ede\u5230\u7b2ck\u968e\u6bb5\u7684\u76ee\u7684\u9ede\u6700\u77ed\u8def\u5f91<\/p>\n\n\n\n
\u5728\u6709\u5411\u52a0\u6b0a\u5716\u4e2d,\u627e\u51fa\u4efb\u610f\u5169\u9ede\u9593\u7684\u6700\u77ed\u8ddd\u96e2\u8def\u5f91<\/p>\n\n\n\n
\u540c\u80cc\u5305\u554f\u984c,\u4f46\u7269\u54c1\u4e0d\u53ef\u88ab\u5207\u5272,\u5c6c\u65bc\u90e8\u4efd\u96c6\u5408\u554f\u984c
\u905e\u8ff4\u95dc\u4fc2\u5f0f:f_n(m)=maximum{f_n-1(m),f_n-1(m-weight_n)+profit_n},n=\u7b2cn\u500b\u7269\u54c1,m=\u6700\u5927\u9650\u91cd,f_n(m)=n\u500b\u7269\u54c1\u5728m\u4e0b\u5177\u6709\u6700\u5927\u5229\u6f64
\u6f14\u7b97\u6cd5\u5247:(\u8907\u96dc\u5ea6=O(2^n),\u905e\u8ff4\u95dc\u4fc2\u5f0f=t(n)=2t(n-1)+c,if n>0)
#define limit \u91cd\u91cf\u9650\u5236;
#define n \u500b\u6578;
int p[n]=\u5229\u6f64,w[n]=\u91cd\u91cf;
int choose[n]=\u662f\u5426\u9078\u53d6; \/\/\u521d\u59cb\u503c\u70ba0
int f(int n,int weight,int profit){
\u3000int no,yes;
\u3000if(n==0&&weight>limit<\/strong>)return(0); \/\/\u8d85\u904e\u91cd\u91cf\uff0c\u5229\u6f64\u70ba0
\u3000\u3000else if(n==0)return(profit); \/\/\u7d42\u6b62\u689d\u4ef6\uff0c\u56de\u50b3\u5229\u6f64
\u3000else{
\u3000\u3000no=f(n-1,weight,profit); \/\/\u4e0d\u9078\u7b2cn\u4ef6\u7269\u54c1\u7684\u5229\u6f64
\u3000\u3000yes=f(n-1,weight+w[n]<\/strong>,profit+p[n]<\/strong>); \/\/\u9078\u7684\u5229\u6f64
\u3000\u3000if(no>yes){ \/\/\u56de\u50b3\u8f03\u5927\u7684\u5229\u6f64
\u3000\u3000\u3000choose[n]<\/strong>=0;
\u3000\u3000\u3000return(no);
\u3000\u3000}else{
\u3000\u3000\u3000choose[n]<\/strong>=1;
\u3000\u3000\u3000return(yes);
\u3000\u3000}
\u3000}
}<\/p>\n\n\n\n
…….?<\/p>\n\n\n\n
\u4e00\u63a8\u92b7\u54e1\u5f9e\u57ce\u5e02\u51fa\u767c,\u5c07\u5404\u57ce\u5e02\u8d70\u8a2a\u4e00\u6b21\u6700\u5f8c\u56de\u5230\u539f\u57ce\u5e02(\u627e\u51fa\u4e00\u500b\u6700\u5c0f\u6210\u672c\u7684\u8ff4\u8def)
n=n\u500b\u9802\u9ede,cost=\u7531\u7de8\u865fi\u7684\u9ede\u7d93\u904e\u9ede\u96c6\u5408v\u4e2d\u6240\u6709\u9ede,\u518d\u5230\u9054\u51fa\u767c\u9ede\u7684\u6700\u77ed\u8ddd\u96e2
\u905e\u8ff4\u95dc\u4fc2\u5f0f:cost=minimum{weight+cost},j\u5c6c\u65bcv
cost=(weight)\u9edei\u5230\u9054\u6240\u6709\u53ef\u80fd\u7684\u9802\u9edej\u4e4b\u9593\u7684\u8ddd\u96e2+(cost)\u9edej \u5230\u9054\u51fa\u767c\u9ede\u7684\u6700\u77ed\u8ddd\u96e2\u8def\u5f91,\u9078\u64c7\u5176\u4e2d\u6700\u5c0f\u8005\u5f97\u5230\u6700\u77ed\u8ddd\u96e2\u8def\u5f91
……………………………………………………………………………….<\/p>\n\n\n\n
\u9069\u7528:\u88ab\u6b78\u5217\u70ba\u6392\u5217\u554f\u984c\u6216\u662f\u90e8\u4efd\u96c6\u5408\u554f\u984c\uff0c\u6216\u662f\u5177\u9650\u5236\u689d\u4ef6\u7684\u6700\u4f73\u5316\u554f\u984c
\u6838\u5fc3:\u5c07\u554f\u984c\u8868\u793a\u6210\u4e00\u500bstate space tree(\u72c0\u614b\u7a7a\u9593\u6a39)\u8207\u6df1\u5ea6\u512a\u5148\u641c\u5c0b
\u8aaa\u660e:\u554f\u984c\u7684\u89e3\u7b54\u53ef\u8868\u793a\u6210\u70ba\u4e00\u500b\u5177\u6709n\u500b\u9805\u7684\u5411\u91cf(x1,x2,…xn),\u540c\u6642\u5c07\u554f\u984c\u8868\u793a\u6210\u4e00\u500b\u72c0\u614b\u7a7a\u9593\u6a39\uff0c
\u5404\u7bc0\u9ede\u8868\u793a\u554f\u984c\u7684\u5404\u72c0\u614b,\u6a39\u6839\u8868\u8d77\u59cb\u72c0\u614b,\u6a39\u8449\u8868\u6700\u7d42\u72c0\u614b,\u5206\u652f\u5ea6\u8868\u793a\u89e3\u7b54\u4e2d\u7684\u67d0\u500b\u9805xi,1<=i<=n\u53ef\u80fd\u5177\u6709\u7684\u7bc4\u570d,
\u518d\u5c0d\u72c0\u614b\u7a7a\u9593\u6a39\u7531\u6a39\u6839\u958b\u59cb\u9032\u884c\u6df1\u5ea6\u512a\u5148\u641c\u5c0b,\u5f9e\u53ef\u80fd\u7b54\u6848\u4e2d\u627e\u51fa\u7b26\u5408\u689d\u4ef6\u7684\u89e3<\/p>\n\n\n\n
8queen problem(\u516b\u500b\u7687\u540e\u554f\u984c):\u5c07\u516b\u9846\u897f\u6d0b\u68cb\u7687\u540e\u68cb\u5b50\u653e\u5728\u68cb\u76e4\u4e2d,\u4f46\u5f7c\u6b64\u4e0d\u80fd\u5728\u540c\u5c0d\u89d2\u7dda\u8207\u540c\u884c\u540c\u5217,\u67098!\u7a2e\u53ef\u80fd\u7684\u72c0\u614b\u7a7a\u9593
sum of subset(\u90e8\u4efd\u96c6\u5408\u4e4b\u554f\u984c):\u5728n\u500b\u6574\u6578\u4e2d,\u627e\u51fa\u52a0\u8d77\u4f86=m\u7684\u90e8\u4efd\u7d44\u5408,\u67092^n\u7a2e\u53ef\u80fd\u7684\u72c0\u614b\u7a7a\u9593
0\/1\u80cc\u5305\u554f\u984c:\u540c\u4e0a
hamiltonian cycles(\u6f22\u7c73\u723e\u6566\u8ff4\u8def\u554f\u984c):\u5728n\u500b\u9ede\u7684\u6709\u5411\u5716\u4e2d,\u5f9e\u67d0\u9ede\u51fa\u767c\u7d93\u904e\u5404\u9ede\u4e00\u6b21\u5728\u56de\u5230\u8d77\u9ede\u7684\u8ff4\u8def,\u6709n!\u7a2e\u53ef\u80fd\u7684\u72c0\u614b\u7a7a\u9593
graph coloring(\u5716\u5f62\u8457\u8272\u554f\u984c):\u5728n\u500b\u5716\u5f62\u4e2d\u627e\u51fa\u4e00\u7a2e\u8457\u8272\u65b9\u6cd5,\u8b93\u5716\u5f62\u4e2d\u4efb\u5169\u76f8\u9130\u9ede\u90fd\u5177\u6709\u4e0d\u540c\u7684\u984f\u8272<\/p>\n\n\n\n
\u6838\u5fc3:\u72c0\u614b\u7a7a\u9593\u6a39,\u5ee3\u5ea6\u512a\u5148\u641c\u5c0b
\u8aaa\u660e:\u5c07\u554f\u984c\u8868\u793a\u6210\u72c0\u614b\u7a7a\u9593\u4e26\u4f7f\u7528\u5ee3\u5ea6\u512a\u5148\u641c\u5c0b\u5c0d\u6b64\u6a39\u4e2d\u5404\u7bc0\u9ede\u9032\u884c\u6aa2\u67e5,\u4e26\u7528bounding function(\u908a\u754c\u51fd\u6578)\u7528\u4f86\u522a\u9664\u4e00\u4e9b\u4e0d\u5fc5\u8981\u7684\u5b50\u6a39\u641c\u5c0b
\u4e26\u6839\u64da\u4f7f\u7528\u4f47\u5217\u6216\u5806\u758a\u5354\u52a9\u5132\u5b58\u7bc0\u9ede,\u53ef\u5206\u6210FIFO search(\u5148\u9032\u5148\u51fa\u641c\u5c0b)\u8207LIFO search(\u5f8c\u9032\u5148\u51fa\u641c\u5c0b),\u82e5\u52a0\u5165\u6210\u672c\u5bd2\u6578\u5247\u7a31\u70baLC search(\u6700\u5c0f\u6210\u672c\u641c\u5c0b)
best-first search with branch-and-bound pruning:\u5728\u5206\u652f\u9650\u5236\u6cd5\u4e2d\u7d66\u8207\u72c0\u614b\u7a7a\u9593\u6a39\u5404\u9ede\u4e00\u500b\u8a55\u4f30\u503c,\u7236\u7bc0\u9ede\u53ef\u4f9d\u503c\u6c7a\u5b9a\u90a3\u500b\u5b50\u7bc0\u9ede\u5148\u8d70\u8a2a
breadth-first search with branch-and-bound pruning:\u5728\u5206\u652f\u9650\u5236\u6cd5\u4e2d\u4f7f\u7528\u5ee3\u5148\u641c\u5c0b\u9806\u5e8f\u8d70\u8a2a\u72c0\u614b\u7a7a\u9593\u6a39\u5404\u9ede,\u56e0\u6c92\u7528\u8a55\u4f30\u503c\u6c7a\u5b9a\u8d70\u8a2a\u9806\u5e8f\u6240\u4ee5\u6548\u7387\u8f03\u5dee<\/p>\n\n\n\n
puzzle problem(\u6578\u5b57\u9375\u76e4\u554f\u984c):\u5728x*y\u7684\u65b9\u6846\u4e2d,\u5c07\u6578\u5b57\u4f9d\u5e8f\u6392\u5217,\u53ef\u80fd\u72c0\u614b\u6709x*y!\u500b
\u6700\u5f8c\u671f\u9650\u5de5\u4f5c\u898f\u756b\u554f\u984c:\u540c\u4e0a,\u53ef\u80fd\u72c0\u614b\u67092^n\u500b,\u5c6c\u90e8\u5206\u96c6\u5408\u554f\u984c
game tree(\u904a\u6232\u6a39):\u53ef\u5c07\u4e00\u904a\u6232\u90e8\u4efd\u72c0\u614b\u8868\u793a\u51fa\u4f86\u7684\u6a39,\u518d\u7531\u5176\u4e2d\u6c7a\u5b9a\u4e0b\u4e00\u6b65\u8a72\u5982\u4f55\u8d70\u624d\u80fd\u7372\u52dd,\u5c6c\u65bc\u56de\u6eaf\u6cd5\u548c\u5206\u652f\u9650\u5236\u6cd5\u8f03\u8907\u96dc\u7684\u61c9\u7528<\/p>\n","protected":false},"excerpt":{"rendered":"