2021-11-14<\/p>\n
\u6587\u7ae0\u76ee\u5f55
\n \u524d\u8a00\u4e00\u3001\u4f20\u7edf\u8def\u5f84\u89c4\u5212\u7b97\u6cd51.Dijkstra\u7b97\u6cd52.A*\u7b97\u6cd53.D*\u7b97\u6cd54.\u4eba\u5de5\u52bf\u573a\u6cd5
\n \u4e8c\u3001\u57fa\u4e8e\u91c7\u6837\u8def\u5f84\u89c4\u5212\u7b97\u6cd51.PRM\u7b97\u6cd52.RRT\u7b97\u6cd5
\n \u4e09\u3001\u667a\u80fd\u4eff\u751f\u7b97\u6cd51.\u795e\u7ecf\u7f51\u7edc\u7b97\u6cd52.\u8681\u7fa4\u7b97\u6cd53.\u9057\u4f20\u7b97\u6cd5<\/p>\n
\u524d\u8a00
\n\u968f\u7740\u673a\u5668\u4eba\u6280\u672f\u3001\u667a\u80fd\u63a7\u5236\u6280\u672f\u3001\u786c\u4ef6\u4f20\u611f\u5668\u7684\u53d1\u5c55\uff0c\u673a\u5668\u4eba\u5728\u5de5\u4e1a\u751f\u4ea7\u3001\u519b\u4e8b\u56fd\u9632\u4ee5\u53ca\u65e5\u5e38\u751f\u6d3b\u7b49\u9886\u57df\u5f97\u5230\u4e86\u5e7f\u6cdb\u7684\u5e94\u7528\u3002\u800c\u4f5c\u4e3a\u673a\u5668\u4eba\u884c\u4e1a\u7684\u91cd\u8981\u7814\u7a76\u9886\u57df\u4e4b\u4e00\uff0c\u79fb\u52a8\u673a\u5668\u4eba\u884c\u4e1a\u8fd1\u5e74\u6765\u4e5f\u5230\u4e86\u8fc5\u901f\u7684\u53d1\u5c55\u3002\u79fb\u52a8\u673a\u5668\u4eba\u4e2d\u7684\u8def\u5f84\u89c4\u5212\u4fbf\u662f\u91cd\u8981\u7684\u7814\u7a76\u65b9\u5411\u3002\u79fb\u52a8\u673a\u5668\u4eba\u7684\u8def\u5f84\u89c4\u5212\u65b9\u6cd5\u4e3b\u8981\u5206\u4e3a\u4f20\u7edf\u7684\u8def\u5f84\u89c4\u5212\u7b97\u6cd5\u3001\u57fa\u4e8e\u91c7\u6837\u7684\u8def\u5f84\u89c4\u5212\u7b97\u6cd5\u3001\u667a\u80fd\u4eff\u751f\u7b97\u6cd5\u3002\u4f20\u7edf\u7684\u8def\u5f84\u89c4\u5212\u7b97\u6cd5\u4e3b\u8981\u6709A\u7b97\u6cd5\u3001Dijkstra\u7b97\u6cd5\u3001D\u7b97\u6cd5\u3001\u4eba\u5de5\u52bf\u573a\u6cd5\uff0c\u57fa\u4e8e\u91c7\u6837\u7684\u8def\u5f84\u89c4\u5212\u7b97\u6cd5\u6709PRM\u7b97\u6cd5\u3001RRT\u7b97\u6cd5\uff0c\u667a\u80fd\u4eff\u751f\u8def\u5f84\u89c4\u5212\u7b97\u6cd5\u6709\u795e\u7ecf\u7f51\u7edc\u7b97\u6cd5\u3001\u8681\u7fa4\u7b97\u6cd5\u3001\u9057\u4f20\u7b97\u6cd5\u7b49\u3002 <\/p>\n
\u4e00\u3001\u4f20\u7edf\u8def\u5f84\u89c4\u5212\u7b97\u6cd5
\n1.Dijkstra\u7b97\u6cd5
\nDijkstra\u7b97\u6cd5\u662fEdsger Wybe Dijkstra\u57281956\u5e74\u63d0\u51fa\u7684\u4e00\u79cd\u7528\u6765\u5bfb\u627e\u56fe\u5f62\u4e2d\u7ed3\u70b9\u4e4b\u95f4\u6700\u77ed\u8def\u5f84\u7684\u7b97\u6cd5\u3002Dijkstra\u7b97\u6cd5\u7684\u57fa\u672c\u601d\u60f3\u662f\u8d2a\u5fc3\u601d\u60f3\uff0c\u4e3b\u8981\u7279\u70b9\u662f\u4ee5\u8d77\u59cb\u70b9\u4e3a\u4e2d\u5fc3\u5411\u5916\u5c42\u5c42\u6269\u5c55\uff0c\u76f4\u5230\u6269\u5c55\u5230\u76ee\u6807\u70b9\u4e3a\u6b62\u3002Dijkstra\u7b97\u6cd5\u5728\u6269\u5c55\u7684\u8fc7\u7a0b\u4e2d\uff0c\u90fd\u662f\u53d6\u51fa\u672a\u8bbf\u95ee\u7ed3\u70b9\u4e2d\u8ddd\u79bb\u8be5\u70b9\u8ddd\u79bb\u6700\u5c0f\u7684\u7ed3\u70b9\uff0c\u7136\u540e\u5229\u7528\u8be5\u7ed3\u70b9\u53bb\u66f4\u65b0\u5176\u4ed6\u7ed3\u70b9\u7684\u8ddd\u79bb\u503c\u3002 Dijkstra\u7b97\u6cd5\u6d41\u7a0b\uff1a
\n1.\t\u5c06\u521d\u59cb\u70b9s\u653e\u5165\u5230\u96c6\u5408S\u4e2d\uff0c\u521d\u59cb\u65f6\u96c6\u5408S\u4e2d\u53ea\u6709s\uff1b
\n2.\t\u65e0\u81ea\u73af\u7684\u521d\u59cb\u70b9s\u5230\u81ea\u5df1\u7684\u6700\u77ed\u8def\u5f84\u4e3a0\uff1b
\n3.\tFor\uff08\u76ee\u6807\u70b9ei\u4e0d\u5728\u96c6\u5408S\u4e2d\uff09\uff1a
\n4.\t \u8ba1\u7b97\u96c6\u5408S\u4e2d\u4ee5\u5916\u7684\u6240\u6709\u7ed3\u70b9\u5230\u96c6\u5408S\u4e2d\u7ed3\u70b9\u7684\u6700\u77ed\u8ddd\u79bb\uff0c\u5373\u4eces\u51fa\u53d1\uff0c\u5230\u8fbe\u6240\u6709\u7ed3\u70b9\u4e14\u53ea\u5141\u8bb8\u901a\u8fc7\u521d\u59cb\u70b9s\u7684\u6700\u77ed\u8def\u5f84\u3002\u5982\u679c\u6ca1\u6709\u76f4\u8fbe\u7684\u901a\u8def\uff0c\u90a3\u4e48\u5c31\u8bbe\u7f6e\u4e3a\u65e0\u7a77\uff0c\u610f\u5473\u7740\u6682\u65f6\u5230\u8fbe\u4e0d\u4e86\u7684\u7ed3\u70b9\u3002
\n5.\tWhile\uff08\u96c6\u5408V-S\u4e0d\u662f\u7a7a\u96c6\uff09\uff1a
\n6.\t \u9009\u51fa\u7b2c\u4e00\u6b21for\u5faa\u73af\u4e4b\u540e\u5728\u96c6\u5408V-S\u4e2d\uff0c\u4e14\u76f8\u5bf9\u4e8e\u96c6\u5408S\u7684\u6700\u77ed\u8def\u5f84\u4e2d\u8ddd\u79bb\u6700\u77ed\u7684\u76ee\u6807\u70b9ej\u3002
\n7.\t \u5c06\u8be5\u76ee\u6807\u70b9ej\u5e76\u5165\u5230\u96c6\u5408S\u4e2d\u3002
\n8.\t \u5c06\u76ee\u6807\u70b9ej\u5e76\u5165\u96c6\u5408S\u4e4b\u540e\u4f1a\u5bf9V-S\u4ee5\u5916\u7684\u9876\u70b9\u76f8\u5bf9\u4e8e\u96c6\u5408S\u7684\u6700\u77ed\u8def\u5f84\u957f\u5ea6\u4ea7\u751f\u5f71\u54cd\u3002
\n9.\t For\uff08\u66f4\u65b0S\u4e2d\u7684\u7ed3\u70b9\u8def\u5f84\uff09
\n10.\t If\uff08dist[s,ej]+wj,i < dist[s,ei]\uff09\n11.\t dist[s,ei] = dist[s,ej]+wj,i\n1234567891011 \n\u6ce8\uff1a\u8be5\u7b97\u6cd5\u4e0d\u5141\u8bb8\u56fe\u4e2d\u5b58\u5728\u8d1f\u6743\u8fb9\u3002 \u4f18\u70b9\uff1a 1\uff09 \u5982\u679c\u6700\u4f18\u8def\u5f84\u5b58\u5728\uff0c\u90a3\u4e48\u4e00\u5b9a\u80fd\u627e\u5230\u6700\u4f18\u8def\u5f84 \u7f3a\u70b9\uff1a 1\uff09 \u6709\u6743\u56fe\u4e2d\u53ef\u80fd\u662f\u8d1f\u8fb9 2\uff09 \u6269\u5c55\u7684\u7ed3\u70b9\u5f88\u591a\uff0c\u6548\u7387\u4f4e \n2.A*\u7b97\u6cd5 \nA\u7b97\u6cd5\u53d1\u8868\u4e8e1968\u5e74\uff0cA\u7b97\u6cd5\u662f\u5c06Dijkstra\u7b97\u6cd5\u4e0e\u5e7f\u5ea6\u4f18\u5148\u641c\u7d22\u7b97\u6cd5\uff08BFS\uff09\u4e8c\u8005\u7ed3\u5408\u800c\u6210\uff0c\u901a\u8fc7\u501f\u52a9\u542f\u53d1\u5f0f\u51fd\u6570\u7684\u4f5c\u7528\uff0c\u80fd\u591f\u4f7f\u8be5\u7b97\u6cd5\u80fd\u591f\u66f4\u5feb\u7684\u627e\u5230\u6700\u4f18\u8def\u5f84\u3002A\u7b97\u6cd5\u662f\u9759\u6001\u8def\u7f51\u4e2d\u6c42\u89e3\u6700\u77ed\u8def\u5f84\u6700\u6709\u6548\u7684\u76f4\u63a5\u641c\u7d22\u65b9\u6cd5\u3002 A\u7b97\u6cd5\u7684\u542f\u53d1\u5f0f\u51fd\u6570\uff1af(n)=g(n)+h(n) f(n)\u8868\u793a\u7ed3\u70b9\u7684\u7efc\u5408\u4f18\u5148\u7ea7\uff0c\u5728\u9009\u62e9\u7ed3\u70b9\u65f6\u8003\u8651\u8be5\u7ed3\u70b9\u7684\u7efc\u5408\u4f18\u5148\u7ea7\uff1b g(n)\u8868\u793a\u8d77\u59cb\u70b9\u5230\u5f53\u524d\u7ed3\u70b9\u7684\u4ee3\u4ef7\u503c\uff1b h(n)\u8868\u793a\u5f53\u524d\u7ed3\u70b9\u5230\u76ee\u6807\u70b9\u7684\u4ee3\u4ef7\u4f30\u8ba1\u503c\uff0c\u542f\u53d1\u5f0f\u51fd\u6570\u3002 \u5f53h(n)\u8d8b\u8fd1\u4e8e0\u65f6\uff0c\u6b64\u65f6\u7b97\u6cd5\u9000\u5316\u4e3aDijkstra\u7b97\u6cd5\uff0c\u8def\u5f84\u4e00\u5b9a\u80fd\u627e\u5230\uff0c\u4f46\u901f\u5ea6\u6bd4\u8f83\u6162\uff1b\u5f53g(n)\u8d8b\u8fd1\u4e8e0\u65f6\uff0c\u7b97\u6cd5\u9000\u5316\u4e3aBFS\u7b97\u6cd5\uff0c\u4e0d\u80fd\u4fdd\u8bc1\u4e00\u5b9a\u627e\u5230\u8def\u5f84\uff0c\u4f46\u901f\u5ea6\u7279\u522b\u5feb\u3002\u6211\u4eec\u53ef\u4ee5\u901a\u8fc7\u8c03\u8282h(n)\u7684\u5927\u5c0f\u6765\u8c03\u6574\u7b97\u6cd5\u7684\u7cbe\u5ea6\u4e0e\u901f\u5ea6\u3002 \u5728A*\u7b97\u6cd5\u4e2d\uff0c\u91c7\u7528\u6700\u591a\u7684\u662f\u6b27\u51e0\u91cc\u5f97\u8ddd\u79bb\uff0c\u5373dist = srqt((y2-y1)2+(x2-x1)2)\u3002 \nA*\u7b97\u6cd5\u6d41\u7a0b\uff1a \n1.\t\u5c06\u8d77\u59cb\u70b9s\u52a0\u5165\u5230\u5f00\u542f\u5217\u8868openlist\u4e2d\n2.\t\u91cd\u590d\u4ee5\u4e0b\u8fc7\u7a0b\uff1a\na)\t\u904d\u5386\u5f00\u542f\u5217\u8868openlist\uff0c\u5bfb\u627eF\u503c\u6700\u5c0f\u7684\u7ed3\u70b9\uff0c\u5e76\u5c06\u5176\u4f5c\u4e3a\u5f53\u524d\u8981\u5904\u7406\u7684\u7ed3\u70b9\nb)\t\u5c06\u8981\u5904\u7406\u7684\u7ed3\u70b9\u79fb\u5230\u5173\u95ed\u5217\u8868closelist\nc)\t\u5bf9\u5f53\u524d\u7ed3\u70b9\u76848\u4e2a\u76f8\u90bb\u7ed3\u70b9\u7684\u6bcf\u4e2a\u7ed3\u70b9\uff1a\ni.\t\u5982\u679c\u4ed6\u662f\u4e0d\u53ef\u62b5\u8fbe\u7684\u6216\u8005\u5df2\u7ecf\u5728\u5173\u95ed\u5217\u8868closelist\u4e2d\uff0c\u5ffd\u7565\uff1b \nii.\t\u5982\u679c\u4ed6\u4e0d\u5728\u5f00\u542f\u5217\u8868openlist\u4e2d\uff0c\u5c06\u5176\u52a0\u5165openlist\uff0c\u5e76\u628a\u5f53\u524d\u7ed3\u70b9\u8bbe\u7f6e\u4e3a\u5176\u7236\u8282\u70b9\uff0c\u8bb0\u5f55\u5f53\u524d\u7ed3\u70b9\u7684F\u3001G\u3001H\u503c\uff1b\niii.\t\u5982\u679c\u4ed6\u5df2\u7ecf\u5728\u5f00\u542f\u5217\u8868openlist\u4e2d\uff0c\u68c0\u67e5\u8fd9\u6761\u8def\u5f84\uff08\u5373\u7ecf\u7531\u5f53\u524d\u7ed3\u70b9\u5230\u8fbe\u76f8\u90bb\u7ed3\u70b9\uff09\u662f\u5426\u66f4\u597d\uff0c\u7528G\u503c\u505a\u53c2\u8003\uff0c\u66f4\u5c0f\u7684G\u503c\u8868\u793a\u8fd9\u4e2a\u66f4\u597d\u7684\u8def\u5f84\uff0c\u5982\u679c\u662f\u8fd9\u6837\uff0c\u5c06\u5176\u7236\u8282\u70b9\u8bbe\u7f6e\u4e3a\u5f53\u524d\u7ed3\u70b9\uff0c\u5e76\u91cd\u65b0\u8ba1\u7b97\u4ed6\u7684G\u503c\u548cF\u503c\uff0c\u5982\u679c\u5f00\u542f\u5217\u8868openlist\u662f\u6309F\u503c\u8fdb\u884c\u6392\u5e8f\uff0c\u6539\u53d8\u540e\u9700\u8981\u91cd\u65b0\u6392\u5e8f\u3002\nd)\t\u505c\u6b62\uff0c\u5f53\ni.\t\u7ec8\u70b9\u52a0\u5165\u5230\u4e86\u5f00\u542f\u5217\u8868openlist\u4e2d\uff0c\u6b64\u65f6\u8def\u5f84\u5df2\u7ecf\u627e\u5230\nii.\t\u67e5\u627e\u91cd\u70b9\u5931\u8d25\uff0c\u5e76\u4e14\u5f00\u542f\u5217\u8868openlist\u4e2d\u662f\u7a7a\u7684\uff0c\u6b64\u65f6\u6ca1\u6709\u8def\u5f84\n3.\t\u4fdd\u5b58\u8def\u5f84\uff0c\u4ece\u7ec8\u70b9\u5f00\u59cb\uff0c\u6bcf\u4e2a\u7ed3\u70b9\u6cbf\u7740\u5176\u7236\u8282\u70b9\u79fb\u52a8\u76f4\u5230\u8d77\u70b9\u3002\n123456789101112 \n \n \u4f18\u70b9\uff1a 1\uff09 \u5229\u7528\u542f\u53d1\u5f0f\u51fd\u6570\uff0c\u641c\u7d22\u8303\u56f4\u5c0f\uff0c\u63d0\u9ad8\u4e86\u641c\u7d22\u6548\u7387 2\uff09 \u5982\u679c\u6700\u4f18\u8def\u5f84\u5b58\u5728\uff0c\u90a3\u4e48\u4e00\u5b9a\u80fd\u627e\u5230\u6700\u4f18\u8def\u5f84 \u7f3a\u70b9\uff1a 1\uff09 A\u7b97\u6cd5\u4e0d\u9002\u7528\u4e8e\u52a8\u6001\u73af\u5883 2\uff09 A\u7b97\u6cd5\u4e0d\u592a\u9002\u5408\u4e8e\u9ad8\u7ef4\u7a7a\u95f4\uff0c\u8ba1\u7b97\u91cf\u5927 3\uff09 \u76ee\u6807\u70b9\u4e0d\u53ef\u8fbe\u65f6\u4f1a\u9020\u6210\u5927\u91cf\u6027\u80fd\u6d88\u8017 \n3.D*\u7b97\u6cd5 \nD\u7b97\u6cd5\u662f\u5361\u8010\u57fa\u6885\u9686\u673a\u5668\u4eba\u4e2d\u5fc3\u7684Stentz\u57281994\u5e74\u63d0\u51fa\u7684\u4e3b\u8981\u7528\u4e8e\u673a\u5668\u4eba\u63a2\u8def\uff0c\u5e76\u4e14\u7f8e\u56fd\u706b\u661f\u63a2\u6d4b\u5668\u4e0a\u5c31\u662f\u5e94\u7528\u7684D\u8def\u5f84\u89c4\u5212\u7b97\u6cd5\u3002A\u7b97\u6cd5\u9002\u7528\u4e8e\u5728\u9759\u6001\u8def\u7f51\u4e2d\u5bfb\u8def\uff0c\u5728\u73af\u5883\u53d8\u5316\u540e\uff0c\u5f80\u5f80\u9700\u8981replan\uff0c\u7531\u4e8eA\u4e0d\u80fd\u6709\u6548\u5229\u7528\u4e0a\u6b21\u8ba1\u7b97\u7684\u4fe1\u606f\uff0c\u6545\u8ba1\u7b97\u6548\u7387\u8f83\u4f4e\u3002D\u7b97\u6cd5\u7531\u4e8e\u50a8\u5b58\u4e86\u7a7a\u95f4\u4e2d\u6bcf\u4e2a\u70b9\u5230\u7ec8\u70b9\u7684\u6700\u77ed\u8def\u5f84\u4fe1\u606f\uff0c\u6545\u5728\u91cd\u89c4\u5212\u65f6\u6548\u7387\u5927\u5927\u63d0\u5347\u3002A\u662f\u6b63\u5411\u641c\u7d22\uff0c\u800cD\u7279\u70b9\u662f\u53cd\u5411\u641c\u7d22\uff0c\u5373\u4ece\u76ee\u6807\u70b9\u5f00\u59cb\u641c\u7d22\u8fc7\u7a0b\u3002\u5728\u521d\u6b21\u904d\u5386\u65f6\u5019\uff0c\u4e0eDijkstra\u7b97\u6cd5\u4e00\u81f4\uff0c\u5b83\u5c06\u6bcf\u4e2a\u8282\u70b9\u7684\u4fe1\u606f\u90fd\u4fdd\u5b58\u4e0b\u6765\u3002 D*\u7b97\u6cd5\u6d41\u7a0b\uff1a \n1.\t\u5148\u7528Dijkstra\u7b97\u6cd5\u4ece\u76ee\u6807\u8282\u70b9G\u5411\u8d77\u59cb\u8282\u70b9\u641c\u7d22\u3002\u50a8\u5b58\u8def\u7f51\u4e2d\u76ee\u6807\u70b9\u5230\u5404\u4e2a\u8282\u70b9\u7684\u6700\u77ed\u8def\u548c\u8be5\u4f4d\u7f6e\u5230\u76ee\u6807\u70b9\u7684\u5b9e\u9645\u503ch\uff0ck\uff08k\u4e3a\u6240\u6709\u53d8\u5316h\u4e4b\u4e2d\u6700\u5c0f\u7684\u503c\uff0c\u5f53\u524d\u4e3ak=h\uff09\u539fOPEN\u548cCLOSE\u4e2d\u8282\u70b9\u4fe1\u606f\u4fdd\u5b58\u3002\n2.\t\u673a\u5668\u4eba\u6cbf\u6700\u77ed\u8def\u5f00\u59cb\u79fb\u52a8\uff0c\u5728\u79fb\u52a8\u7684\u4e0b\u4e00\u8282\u70b9\u6ca1\u6709\u53d8\u5316\u65f6\uff0c\u65e0\u9700\u8ba1\u7b97\uff0c\u5229\u7528\u4e0a\u4e00\u6b65Dijkstra\u8ba1\u7b97\u51fa\u7684\u6700\u77ed\u8def\u4fe1\u606f\u4ece\u51fa\u53d1\u70b9\u5411\u540e\u8ffd\u8ff0\u5373\u53ef\uff0c\u5f53\u5728Y\u70b9\u63a2\u6d4b\u5230\u4e0b\u4e00\u8282\u70b9X\u72b6\u6001\u53d1\u751f\u6539\u53d8\uff0c\u5982\u5835\u585e\u3002\u673a\u5668\u4eba\u9996\u5148\u8c03\u6574\u81ea\u5df1\u5728\u5f53\u524d\u4f4d\u7f6eY\u5230\u76ee\u6807\u70b9G\u7684\u5b9e\u9645\u503ch\uff08Y\uff09\uff0ch\uff08Y\uff09=X\u5230Y\u7684\u65b0\u6743\u503cC\uff08X\uff0cY\uff09+X\u7684\u539f\u5b9e\u9645\u503ch\uff08X\uff09\u3002X\u4e3a\u4e0b\u4e00\u8282\u70b9\uff08\u5230\u76ee\u6807\u70b9\u65b9\u5411Y->X->G\uff09\uff0cY\u662f\u5f53\u524d\u70b9\u3002K\u503c\u53bbh\u503c\u53d8\u5316\u524d\u540e\u7684\u6700\u5c0f\u3002
\n3.\t\u7528A*\u6216\u5176\u4ed6\u7b97\u6cd5\u8ba1\u7b97\uff0c\u8fd9\u91cc\u5047\u8bbe\u7528A*\u7b97\u6cd5\uff0c\u904d\u5386Y\u7684\u5b50\u8282\u70b9\uff0c\u653e\u5165CLOSE\uff0c\u8c03\u6574Y\u7684\u5b50\u8282\u70b9a\u7684h\u503c\uff0ch\uff08a\uff09=h\uff08Y\uff09+Y\u5230\u5b50\u8282\u70b9a\u7684\u6743\u91cdC\uff08Y\uff0ca\uff09\uff0c\u6bd4\u8f83a\u70b9\u662f\u5426\u5b58\u5728\u4e8eOPEN\u548cCLOSE\u4e2d\uff0c\u65b9\u6cd5\u5982\u4e0b\uff1a\u7528A*\u6216\u8005\u5176\u4ed6\u7b97\u6cd5\u8ba1\u7b97\uff0c\u8fd9\u91cc\u5047\u8bbe\u7528A*\u7b97\u6cd5\uff0c\u904d\u5386Y\u7684\u5b50\u8282\u70b9\uff0c\u653e\u5165CLOSE\uff0c\u8c03\u6574Y\u7684\u5b50\u8282\u70b9a\u7684h\u503c\uff0ch\uff08a\uff09=h\uff08Y\uff09+Y\u5230\u5b50\u8282\u70b9a\u7684\u6743\u91cdC\uff08Y\uff0ca\uff09\uff0c\u6bd4\u8f83a\u70b9\u662f\u5426\u5b58\u5728\u4e8eOPEN\u548cCLOSE\u4e2d\uff0c\u65b9\u6cd5\u5982\u4e0b\uff1a
\nwhile()
\n{
\n\u4eceOPEN\u8868\u4e2d\u53d6k\u503c\u6700\u5c0f\u7684\u8282\u70b9Y;
\n\u904d\u5386Y\u7684\u5b50\u8282\u70b9a,\u8ba1\u7b97a\u7684h\u503c h(a)=h(Y)+Y\u5230\u5b50\u8282\u70b9a\u7684\u6743\u91cdC(Y,a)
\n{
\n if(a in OPEN) \u6bd4\u8f83\u4e24\u4e2aa\u7684h\u503c
\n if( a\u7684h\u503c\u5c0f\u4e8eOPEN\u8868a\u7684h\u503c )
\n {
\n\u66f4\u65b0OPEN\u8868\u4e2da\u7684h\u503c;k\u503c\u53d6\u6700\u5c0f\u7684h\u503c
\n \u6709\u672a\u53d7\u5f71\u54cd\u7684\u6700\u77ed\u8def\u7ecf\u5b58\u5728
\n break;
\n }
\n if(a in CLOSE) \u6bd4\u8f83\u4e24\u4e2aa\u7684h\u503c \/\/\u6ce8\u610f\u662f\u540c\u4e00\u4e2a\u8282\u70b9\u7684\u4e24\u4e2a\u4e0d\u540c\u8def\u5f84\u7684\u4f30\u4ef7\u503c
\n if( a\u7684h\u503c\u5c0f\u4e8eCLOSE\u8868\u7684h\u503c )
\n {
\n\u66f4\u65b0CLOSE\u8868\u4e2da\u7684h\u503c; k\u503c\u53d6\u6700\u5c0f\u7684h\u503c;\u5c06a\u8282\u70b9\u653e\u5165OPEN\u8868
\n \u6709\u672a\u53d7\u5f71\u54cd\u7684\u6700\u77ed\u8def\u7ecf\u5b58\u5728
\n break;
\n }
\n if(a not in both)
\n \u5c06a\u63d2\u5165OPEN\u8868\u4e2d;\u3000\/\/\u8fd8\u6ca1\u6709\u6392\u5e8f
\n}
\n\u653eY\u5230CLOSE\u8868\uff1b
\nOPEN\u8868\u6bd4\u8f83k\u503c\u5927\u5c0f\u8fdb\u884c\u6392\u5e8f\uff1b
\n}
\n12345678910111213141516171819202122232425262728
\n \u4f18\u70b9\uff1a 1\uff09\u9002\u7528\u4e8e\u52a8\u6001\u73af\u5883\u7684\u8def\u5f84\u89c4\u5212\uff0c\u641c\u7d22\u6548\u7387\u9ad8 \u7f3a\u70b9\uff1a 1\uff09 \u4e0d\u9002\u7528\u4e8e\u9ad8\u7ef4\u7a7a\u95f4\uff0c\u8ba1\u7b97\u91cf\u5927 2\uff09 \u4e0d\u592a\u9002\u7528\u4e8e\u5728\u8ddd\u79bb\u8f83\u8fdc\u7684\u6700\u77ed\u8def\u5f84\u4e0a\u53d1\u751f\u53d8\u5316\u7684\u573a\u666f
\n4.\u4eba\u5de5\u52bf\u573a\u6cd5
\n\u4eba\u5de5\u52bf\u573a\u6cd5\u662f\u7531Khatib\u57281985\u5e74\u63d0\u51fa\u7684\u4e00\u79cd\u57fa\u4e8e\u865a\u62df\u529b\u573a\u7684\u5c40\u90e8\u8def\u5f84\u89c4\u5212\u7b97\u6cd5\uff0c\u8be5\u7b97\u6cd5\u7684\u57fa\u672c\u601d\u60f3\u662f\u5f53\u673a\u5668\u4eba\u5728\u5468\u56f4\u73af\u5883\u4e2d\u8fd0\u52a8\u65f6\uff0c\u5c06\u73af\u5883\u8bbe\u8ba1\u6210\u4e00\u79cd\u62bd\u8c61\u7684\u4eba\u9020\u5f15\u529b\u573a\uff0c\u76ee\u6807\u70b9\u5bf9\u79fb\u52a8\u673a\u5668\u4eba\u4ea7\u751f\u201c\u5f15\u529b\u201d\uff0c\u969c\u788d\u7269\u5bf9\u79fb\u52a8\u673a\u5668\u4eba\u4ea7\u751f\u201c\u65a5\u529b\u201d\uff0c\u6700\u540e\u901a\u8fc7\u4e8c\u8005\u7684\u5408\u529b\u6765\u63a7\u5236\u79fb\u52a8\u673a\u5668\u4eba\u7684\u8fd0\u52a8\u3002\u5e94\u7528\u4eba\u5de5\u52bf\u573a\u6cd5\u89c4\u5212\u51fa\u6765\u7684\u8def\u5f84\u4e00\u822c\u662f\u6bd4\u8f83\u5e73\u6ed1\u5e76\u4e14\u5b89\u5168\u7684\uff0c\u4f46\u662f\u5b58\u5728\u7740\u5c40\u90e8\u6700\u4f18\u7684\u95ee\u9898\u3002 \u5229\u7528\u52bf\u573a\u51fd\u6570U\u6765\u5efa\u7acb\u4eba\u5de5\u52bf\u573a\uff0c\u52bf\u573a\u51fd\u6570\u662f\u4e00\u79cd\u53ef\u5fae\u51fd\u6570\uff0c\u7a7a\u95f4\u4e2d\u67d0\u70b9\u5904\u52bf\u573a\u51fd\u6570\u503c\u7684\u5927\u5c0f\uff0c\u4ee3\u8868\u4e86\u8be5\u70b9\u7684\u52bf\u573a\u5f3a\u5ea6\u3002\u6211\u4eec\u91c7\u7528\u5f15\u529b\u52bf\u573a\u51fd\u6570\u4e0e\u65a5\u529b\u52bf\u573a\u51fd\u6570\uff0c\u7528U\uff08q\uff09\u8868\u793a\u4e8c\u8005\u4e4b\u548c\u3002 \u5f15\u529b\u52bf\u573a\u51fd\u6570\uff1a e\u8868\u793a\u5f15\u529b\u589e\u76ca\uff0cp(q,qgoal)\u8868\u793a\u5f53\u524d\u70b9\u5230\u76ee\u6807\u70b9\u7684\u8ddd\u79bb\uff1b \u65a5\u529b\u52bf\u573a\u51fd\u6570\uff1a n\u8868\u793a\u65a5\u529b\u589e\u76ca\uff0cp(q,qgoal)\u8868\u793a\u5f53\u524d\u70b9\u5230\u969c\u788d\u7269\u7684\u8ddd\u79bb\uff0cp0\u8868\u793a\u969c\u788d\u7269\u4f5c\u7528\u8ddd\u79bb\u9608\u503c\u3002 \u4f18\u70b9\uff1a 1\uff09 \u89c4\u5212\u51fa\u7684\u8def\u5f84\u4e00\u822c\u662f\u6bd4\u8f83\u5e73\u6ed1\u4e14\u5b89\u5168 2\uff09 \u4eba\u5de5\u52bf\u573a\u6cd5\u662f\u4e00\u79cd\u53cd\u9988\u63a7\u5236\u7b56\u7565\uff0c\u5177\u6709\u4e00\u5b9a\u7684\u9c81\u68d2\u6027 \u7f3a\u70b9\uff1a 1\uff09 \u5bb9\u6613\u9677\u5165\u5c40\u90e8\u6700\u4f18\u7684\u95ee\u9898 2\uff09 \u8ddd\u79bb\u76ee\u6807\u70b9\u8f83\u8fdc\u65f6\uff0c\u5f15\u529b\u7279\u522b\u5927\uff0c\u65a5\u529b\u76f8\u5bf9\u8f83\u5c0f\uff0c\u53ef\u80fd\u4f1a\u53d1\u751f\u78b0\u649e 3\uff09 \u5f53\u76ee\u6807\u70b9\u9644\u8fd1\u6709\u969c\u788d\u7269\u65f6\uff0c\u65a5\u529b\u975e\u5e38\u5927\uff0c\u5f15\u529b\u8f83\u5c0f\uff0c\u5f88\u96be\u5230\u8fbe\u76ee\u6807\u70b9
\n\u4e8c\u3001\u57fa\u4e8e\u91c7\u6837\u8def\u5f84\u89c4\u5212\u7b97\u6cd5
\n1.PRM\u7b97\u6cd5
\n\u968f\u673a\u8def\u7ebf\u56fe\uff08PRM\uff09\u7b97\u6cd5\u662f\u4e00\u79cd\u57fa\u4e8e\u56fe\u641c\u7d22\u7684\u7b97\u6cd5\uff0c\u53ef\u4ee5\u5c06\u8fde\u7eed\u72b6\u6001\u7a7a\u95f4\u8f6c\u6362\u6210\u79bb\u6563\u72b6\u6001\u7a7a\u95f4\uff0c\u5728\u5229\u7528A\uff0a\u7b49\u641c\u7d22\u7b97\u6cd5\u5728\u8def\u7ebf\u56fe\u4e0a\u5bfb\u627e\u8def\u5f84\uff0c\u63d0\u9ad8\u641c\u7d22\u6548\u7387\u3002PRM\u7b97\u6cd5\u662f\u6982\u7387\u5b8c\u5907\u4e14\u4e0d\u662f\u6700\u4f18\u7684\u7b97\u6cd5\u3002 PRM\u7b97\u6cd5\u6d41\u7a0b\uff1a
\n1.\t\u521d\u59cb\u5316\uff0c\u8bbeG\uff08V\uff0cE\uff09\u4e3a\u4e00\u4e2a\u65e0\u5411\u56fe\uff0c\u5176\u4e2d\u9876\u70b9\u96c6V\u4ee3\u8868\u65e0\u78b0\u649e\u7684\u72b6\u6001\u70b9\uff0c\u8fde\u7ebf\u96c6E\u4ee3\u8868\u65e0\u78b0\u649e\u7684\u8def\u5f84\u3002\u521d\u59cb\u72b6\u6001\u4e3a\u7a7a\u3002
\n2.\t\u72b6\u6001\u70b9\u91c7\u6837\uff0c\u5728\u72b6\u6001\u7a7a\u95f4\u4e2d\u91c7\u6837\u65e0\u78b0\u649e\u7684\u72b6\u6001\u70b9\u52a0\u5165\u5230\u65e0\u78b0\u649e\u7684\u72b6\u6001\u70b9V\u4e2d\u3002
\n3.\t\u90bb\u57df\u8ba1\u7b97\uff0c\u5b9a\u4e49\u8ddd\u79bbp\uff0c\u5bf9\u4e8e\u5df2\u7ecf\u5b58\u5728\u4e8e\u65e0\u78b0\u649e\u7684\u72b6\u6001\u70b9V\u4e2d\u7684\u70b9\uff0c\u5982\u679c\u4ed6\u4e0e\u65e0\u78b0\u649e\u7684\u70b9\u7684\u8ddd\u79bb\u5c0f\u4e8ep\uff0c\u5219\u5c06\u5176\u79f0\u4f5c\u65e0\u78b0\u649e\u72b6\u6001\u70b9\u7684\u90bb\u57df\u70b9\u3002
\n4.\t\u8fb9\u7ebf\u8fde\u63a5\uff0c\u5c06\u65e0\u78b0\u649e\u7684\u72b6\u6001\u70b9\u4e0e\u5176\u90bb\u57df\u76f8\u8fde\uff0c\u751f\u6210\u8fde\u7ebf\u3002
\n5.\t\u78b0\u649e\u68c0\u6d4b\uff0c\u68c0\u6d4b\u8fde\u7ebf\u662f\u5426\u4e0e\u969c\u788d\u7269\u53d1\u751f\u78b0\u649e\uff0c\u5982\u679c\u65e0\u78b0\u649e\uff0c\u5219\u5c06\u5176\u52a0\u5165\u5230\u8fde\u7ebf\u96c6E\u4e2d\u3002
\n6.\t\u7ed3\u675f\u6761\u4ef6\uff0c\u5f53\u6240\u6709\u91c7\u6837\u70b9\u5747\u5df2\u5b8c\u6210\u4e0a\u8ff0\u6b65\u9aa4\u540e\u7ed3\u675f\uff0c\u5426\u5219\u91cd\u590d2~5\u3002
\n7.\t\u6700\u540e\u4f7f\u7528A*\u7b97\u6cd5\u5728\u8def\u7ebf\u56fe\u4e0a\u5bfb\u627e\u6700\u4f18\u8def\u5f84\u3002
\n1234567
\n \u4f18\u70b9\uff1a 1\uff09 \u9002\u7528\u4e8e\u9ad8\u7ef4\u7a7a\u95f4\u548c\u590d\u6742\u7ea6\u675f\u7684\u8def\u5f84\u89c4\u5212\u95ee\u9898 2\uff09 \u641c\u7d22\u6548\u7387\u9ad8\uff0c\u641c\u7d22\u901f\u5ea6\u5feb \u7f3a\u70b9\uff1a 1\uff09\u6982\u7387\u5b8c\u5907\u4f46\u4e0d\u662f\u6700\u4f18
\n2.RRT\u7b97\u6cd5
\nRRT\u7b97\u6cd5\u662f\u9002\u7528\u4e8e\u9ad8\u7ef4\u7a7a\u95f4\uff0c\u901a\u8fc7\u5bf9\u72b6\u6001\u7a7a\u95f4\u4e2d\u7684\u91c7\u6837\u70b9\u8fdb\u884c\u78b0\u649e\u68c0\u6d4b\uff0c\u907f\u514d\u4e86\u5bf9\u7a7a\u95f4\u7684\u5efa\u6a21\uff0c\u8f83\u597d\u7684\u5904\u7406\u5e26\u6709\u975e\u5b8c\u6574\u7ea6\u675f\u7684\u8def\u5f84\u89c4\u5212\u95ee\u9898\uff0c\u6709\u6548\u7684\u89e3\u51b3\u4e86\u9ad8\u7ef4\u7a7a\u95f4\u548c\u590d\u6742\u7ea6\u675f\u7684\u8def\u5f84\u89c4\u5212\u95ee\u9898\u3002\u8be5\u7b97\u6cd5\u662f\u6982\u7387\u5b8c\u5907\u4f46\u4e0d\u662f\u6700\u4f18\u7684\u7b97\u6cd5\u3002 RRT\u7b97\u6cd5\u4ee5\u521d\u59cb\u70b9qinit\u4f5c\u4e3a\u6839\u8282\u70b9\uff0c\u901a\u8fc7\u968f\u673a\u91c7\u6837\u589e\u52a0\u53f6\u5b50\u8282\u70b9\u7684\u65b9\u5f0f\uff0c\u751f\u6210\u4e00\u4e2a\u968f\u673a\u6269\u5c55\u6811\uff0c\u5f53\u76ee\u6807\u70b9\u4f4d\u4e8e\u968f\u673a\u6269\u5c55\u6811\u4e0a\u65f6\uff0c\u80fd\u591f\u627e\u5230\u4e00\u5929\u521d\u59cb\u70b9\u5230\u76ee\u6807\u70b9\u7684\u8def\u5f84\u3002\u9996\u5148\uff0c\u9700\u8981\u4ece\u72b6\u6001\u7a7a\u95f4\u4e2d\u968f\u673a\u9009\u62e9\u4e00\u4e2a\u91c7\u6837\u70b9qrand\uff0c\u7136\u540e\u4ece\u968f\u673a\u6811\u4e2d\u9009\u62e9\u4e00\u4e2a\u8ddd\u79bbqrand\u6700\u8fd1\u7684\u7ed3\u70b9qnearest\uff0c\u4eceqnearest\u5411qrand\u6269\u5c55\u4e00\u4e2a\u6b65\u957f\u7684\u8ddd\u79bb\uff0c\u5f97\u5230\u4e00\u4e2a\u65b0\u7684\u7ed3\u70b9qnew\uff0c\u5982\u679cqnew\u4e0e\u969c\u788d\u7269\u53d1\u751f\u78b0\u649e\uff0c\u5219\u8fd4\u56de\u7a7a\uff1b\u5426\u5219\uff0c\u5c06qnew\u52a0\u5165\u5230\u968f\u673a\u6811\u4e2d\uff0c\u91cd\u590d\u4e0a\u8ff0\u6b65\u9aa4\u76f4\u5230qnearest\u548cqgoal\u8ddd\u79bb\u5c0f\u4e8e\u4e00\u4e2a\u9608\u503c\u3002 \u4f18\u70b9\uff1a 1\uff09 \u641c\u7d22\u6548\u7387\u6bd4\u8f83\u9ad8\uff0c\u641c\u7d22\u901f\u5ea6\u6bd4\u8f83\u5feb 2\uff09 \u9002\u7528\u4e8e\u9ad8\u7ef4\u7a7a\u95f4\uff0c\u4e0d\u4f1a\u4ea7\u751f\u7ef4\u5ea6\u707e\u96be\u7684\u95ee\u9898 3\uff09 \u53ea\u9700\u5bf9\u72b6\u6001\u7a7a\u95f4\u91c7\u6837\u70b9\u8fdb\u884c\u78b0\u649e\u68c0\u6d4b\uff0c\u907f\u514d\u4e86\u5bf9\u7a7a\u95f4\u7684\u5efa\u6a21 \u7f3a\u70b9\uff1a 1\uff09 \u89c4\u5212\u51fa\u7684\u8def\u5f84\u8d28\u91cf\u4e00\u822c\uff0c\u53ef\u80fd\u5b58\u5728\u68f1\u89d2\u3001\u4e0d\u591f\u5149\u6ed1 2\uff09 RRT\u7b97\u6cd5\u4e0d\u592a\u9002\u7528\u4e8e\u5b58\u5728\u72ed\u957f\u7a7a\u95f4\u7684\u73af\u5883 3\uff09 \u89c4\u5212\u51fa\u7684\u8def\u5f84\u53ef\u80fd\u4e0d\u662f\u6700\u4f18\u8def\u5f84 4\uff09 \u4e0d\u9002\u7528\u4e8e\u52a8\u6001\u73af\u5883\u7684\u8def\u5f84\u89c4\u5212
\n\u4e09\u3001\u667a\u80fd\u4eff\u751f\u7b97\u6cd5
\n1.\u795e\u7ecf\u7f51\u7edc\u7b97\u6cd5
\n\u968f\u7740\u673a\u5668\u4eba\u81ea\u4e3b\u6027\u7684\u4e0d\u65ad\u63d0\u9ad8\uff0c\u4f7f\u5176\u5177\u6709\u73af\u5883\u611f\u77e5\u4ee5\u53ca\u73af\u5883\u5b66\u4e60\u7684\u80fd\u529b\uff0c\u8bb8\u591a\u5b66\u8005\u63d0\u51fa\u4e86\u6df1\u5ea6\u5f3a\u5316\u5b66\u4e60\u7b97\u6cd5\u6765\u89e3\u51b3\u79fb\u52a8\u673a\u5668\u4eba\u5904\u4e8e\u52a8\u6001\u590d\u6742\u73af\u5883\u4e2d\u8def\u5f84\u89c4\u5212\u7684\u95ee\u9898\u3002\u6df1\u5ea6\u5f3a\u5316\u5b66\u4e60\u7b97\u6cd5\u5145\u5206\u5229\u7528\u4e86\u6df1\u5ea6\u5b66\u4e60\u7684\u611f\u77e5\u80fd\u529b\u4e0e\u5f3a\u5316\u5b66\u4e60\u7684\u51b3\u7b56\u80fd\u529b\uff0c\u901a\u8fc7\u673a\u5668\u4eba\u4e0e\u73af\u5883\u7684\u4ea4\u4e92\u8fc7\u7a0b\u4e0d\u65ad\u8bd5\u9519\uff0c\u901a\u8fc7\u73af\u5883\u8bc4\u4ef7\u6027\u7684\u53cd\u9988\uff0c\u5b9e\u73b0\u7cfb\u7edf\u66f4\u52a0\u667a\u80fd\u7684\u51b3\u7b56\u63a7\u5236\uff0c\u5e2e\u52a9\u79fb\u52a8\u673a\u5668\u4eba\u5728\u67d0\u4e9b\u590d\u6742\u672a\u77e5\u7684\u73af\u5883\u4e2d\u5b9e\u73b0\u4e00\u5b9a\u7a0b\u5ea6\u7684\u81ea\u4e3b\u5316\u4e0e\u667a\u80fd\u5316\u3002 \u8def\u5f84\u89c4\u5212\u5c31\u662f\u4e00\u4e2a\u6807\u51c6\u7684MDP\u95ee\u9898\uff0c\u5f3a\u5316\u5b66\u4e60\u53ef\u4ee5\u901a\u8fc7\u503c\u8fed\u4ee3\u7b49\u65b9\u6cd5\u5efa\u7acb\u4e00\u4e2a\u8868\u683c\uff0c\u7528\u4ee5\u5b58\u50a8\u72b6\u6001s\u5230\u52a8\u4f5ca\u7684\u6620\u5c04\u3002\u4f46\u662f\u5728\u590d\u6742\u73af\u5883\u4e2d\u4f1a\u4ea7\u751f\u7ef4\u5ea6\u707e\u96be\u7684\u95ee\u9898\uff0c\u56e0\u6b64\u795e\u7ecf\u7f51\u7edc\u53ef\u4ee5\u89e3\u51b3\u7ef4\u5ea6\u707e\u96be\u7684\u95ee\u9898\u3002\u4ee5DQN\u7b97\u6cd5\u4e3a\u4f8b\uff0c\u6765\u8bb2\u89e3\u795e\u7ecf\u7f51\u7edc\u7b97\u6cd5\u5728\u8def\u5f84\u89c4\u5212\u4e2d\u7684\u5e94\u7528\u3002DQN\u7b97\u6cd5\u662fQ-Learning\u7b97\u6cd5\u4e0e\u5377\u79ef\u795e\u7ecf\u7f51\u7edc\uff08CNN\uff09\u4e8c\u8005\u8fdb\u884c\u7ed3\u5408\u3002DQN\u7b97\u6cd5\u662f\u7531\u4e24\u4e2a\u7f51\u7edc\u7ed3\u6784\u3001\u521d\u59cb\u53c2\u6570\u76f8\u540c\u7684\u7ed3\u6784\u7ec4\u6210\uff0c\u4e00\u4e2a\u662f\u4f30\u8ba1\u7f51\u7edc\uff0c\u7528\u6765\u8f93\u51fa\u4f30\u8ba1\u503c\u51fd\u6570\uff1b\u53e6\u4e00\u4e2a\u662f\u76ee\u6807\u7f51\u7edc\uff0c\u7528\u6765\u8f93\u51fa\u76ee\u6807\u503c\u51fd\u6570\u3002\u901a\u8fc7\u5f3a\u5316\u5b66\u4e60\u4f7f\u673a\u5668\u4eba\u4e0e\u73af\u5883\u8fdb\u884c\u4ea4\u4e92\u5f97\u5230\u6837\u672c\uff08s,a,r,s\u2019\uff09\uff0c\u5c06\u6240\u6709\u7684\u6837\u672c\u96c6\u653e\u5165\u5230\u7ecf\u9a8c\u56de\u653e\u6c60\u4e2d\u3002\u795e\u7ecf\u7f51\u7edc\u8fdb\u884c\u8bad\u7ec3\u65f6\uff0c\u968f\u673a\u7684\u4ece\u7ecf\u9a8c\u56de\u653e\u6c60\u4e2d\u62bd\u53d6batchsz\u6570\u91cf\u7684\u6837\u672c\uff0c\u5c06\u6837\u672c\u8f93\u5165\u8fdb\u795e\u7ecf\u7f51\u7edc\uff0c\u5229\u7528\u795e\u7ecf\u7f51\u7edc\u7684\u975e\u7ebf\u6027\u62df\u5408\u80fd\u529b\uff0c\u62df\u5408\u51fa\u975e\u7ebf\u6027\u51fd\u6570\u6765\u8868\u8fbe\u6211\u4eec\u7684Q\u503c\uff0c\u5229\u7528e-greedy\u7b56\u7565\u6765\u8fdb\u884c\u9009\u62e9\u667a\u80fd\u4f53\u7684\u52a8\u4f5c\u3002\u667a\u80fd\u4f53\u6267\u884c\u5b8c\u76f8\u5e94\u7684\u52a8\u4f5c\u4e4b\u540e\uff0c\u73af\u5883\u4f1a\u53cd\u9988\u4e00\u4e2a\u72b6\u6001\u548c\u5956\u52b1\u503c\uff0c\u6700\u540e\u7ecf\u8fc7\u795e\u7ecf\u7f51\u7edc\u6a21\u578b\u7684\u8bad\u7ec3\u548c\u4f18\u5316\u5f97\u5230\u7f51\u7edc\u7684\u8bad\u7ec3\u53c2\u6570\uff0c\u5f97\u5230\u76f8\u5bf9\u51c6\u786e\u7684\u52a8\u4f5c\u8f93\u51fa\u3002 \u5176\u4e2dw\u8868\u793a\u4f30\u8ba1\u7f51\u7edc\u7684\u53c2\u6570\uff0c w-\u8868\u793a\u76ee\u6807\u7f51\u7edc\u7684\u53c2\u6570\u3002
\n\u4f18\u70b9\uff1a 1\uff09 \u9002\u5408\u4e8e\u52a8\u6001\u590d\u6742\u73af\u5883 2\uff09 \u9002\u7528\u4e8e\u9ad8\u7ef4\u7a7a\u95f4\uff0c\u907f\u514d\u7ef4\u5ea6\u707e\u96be\u7684\u95ee\u9898 \u7f3a\u70b9\uff1a 1\uff09 \u5bf9\u786c\u4ef6\u7684\u8981\u6c42\u6bd4\u8f83\u9ad8 2\uff09 \u53c2\u6570\u8c03\u8282\u6bd4\u8f83\u56f0\u96be
\n2.\u8681\u7fa4\u7b97\u6cd5
\n\u8681\u7fa4\u7b97\u6cd5\uff08Ant Colony Optimization\uff0cACO\uff09\u662fDorigo\u57281992\u5e74\u63d0\u51fa\u7684\u4e00\u79cd\u7528\u6765\u5bfb\u627e\u4f18\u5316\u8def\u5f84\u7684\u6982\u7387\u578b\u7b97\u6cd5\uff0c\u662f\u7531\u4e00\u7fa4\u65e0\u667a\u80fd\u6216\u6709\u8f7b\u5fae\u667a\u80fd\u7684\u4e2a\u4f53\u901a\u8fc7\u76f8\u4e92\u5199\u4f5c\u800c\u8868\u73b0\u51fa\u667a\u80fd\u884c\u4e3a\uff0c\u4e3a\u6c42\u89e3\u590d\u6742\u95ee\u9898\u63d0\u4f9b\u4e86\u4e00\u4e2a\u65b0\u7684\u53ef\u80fd\u6027\u3002\u8be5\u7b97\u6cd5\u7684\u4e3b\u8981\u601d\u60f3\u662f\u8682\u8681\u5728\u5bfb\u627e\u98df\u7269\u8fc7\u7a0b\u4e2d\u53d1\u73b0\u8def\u5f84\u7684\u884c\u4e3a\u3002\u8be5\u7b97\u6cd5\u5177\u6709\u5206\u5e03\u8ba1\u7b97\u3001\u4fe1\u606f\u6b63\u53cd\u9988\u548c\u542f\u53d1\u5f0f\u641c\u7d22\u7684\u7279\u5f81\uff0c\u672c\u8d28\u4e0a\u662f\u8fdb\u5316\u7b97\u6cd5\u4e2d\u7684\u4e00\u79cd\u542f\u53d1\u5f0f\u5168\u5c40\u4f18\u5316\u7b97\u6cd5\u3002 \u8681\u7fa4\u7b97\u6cd5\u7684\u57fa\u672c\u539f\u7406\u662f\u5229\u7528\u8682\u8681\u5728\u89c5\u98df\u8fc7\u7a0b\u4e2d\u4f1a\u91ca\u653e\u4fe1\u606f\u7d20\u3002
\n1.\t\u521d\u59cb\u65f6\u523b\uff0c\u8def\u5f84\u6ca1\u6709\u4efb\u4f55\u4fe1\u606f\u7d20\uff0c\u8682\u8681\u4f1a\u4ee5\u4e00\u5b9a\u7684\u968f\u673a\u6027\u9009\u62e9\u4efb\u610f\u65b9\u5411
\n2.\t\u66f4\u65b0\u4fe1\u606f\u7d20\u77e9\u9635\uff0c\u5f53\u6709\u4fe1\u606f\u7d20\u65f6\uff0c\u8682\u8681\u4f1a\u4f18\u5148\u9009\u62e9\u4fe1\u606f\u7d20\u6d53\u5ea6\u9ad8\u7684\u8def\u5f84
\n3.\t\u90a3\u4e48\u5728\u76f8\u540c\u65f6\u95f4\u5185\uff0c\u4fe1\u606f\u7d20\u7684\u6d53\u5ea6\u4e0e\u8def\u5f84\u957f\u5ea6\u6210\u53cd\u6bd4\uff0c\u8d8a\u77ed\u7684\u8def\u5f84\u4f1a\u6709\u66f4\u591a\u7684\u4fe1\u606f\u7d20\uff0c\u90a3\u4e48\u540e\u7eed\u7684\u8682\u8681\u4f1a\u9009\u62e9\u4fe1\u606f\u7d20\u6d53\u5ea6\u9ad8\u7684\u8def\u5f84\uff0c\u6700\u4f18\u8def\u5f84\u4e0a\u7684\u4fe1\u606f\u7d20\u6d53\u5ea6\u4f1a\u8d8a\u6765\u8d8a\u9ad8
\n4.\t\u968f\u7740\u65f6\u95f4\u7684\u63a8\u79fb\uff0c\u4fe1\u606f\u7d20\u4f1a\u81ea\u884c\u6325\u53d1
\n5.\t\u6700\u7ec8\uff0c\u80fd\u9009\u62e9\u51fa\u4e00\u6761\u6700\u4f18\u8def\u5f84\u5373\u4fe1\u606f\u7d20\u6d53\u5ea6\u9ad8\u7684\u8def\u5f84
\n12345
\n\u5f71\u54cd\u8681\u7fa4\u7b97\u6cd5\u7684\u56e0\u7d20\uff1a 1\uff09 \u4fe1\u606f\u7d20\u5982\u4f55\u6492\u64ad 2\uff09 \u4fe1\u606f\u7d20\u5982\u4f55\u6325\u53d1 3\uff09 \u4ee5\u4f55\u79cd\u65b9\u5f0f\u8ba9\u8682\u8681\u9009\u62e9\u8fd0\u52a8\u65b9\u5411\uff0c\u51cf\u5c11\u76f2\u76ee\u6027\u548c\u4e0d\u5fc5\u8981\u6027 4\uff09 \u7ed9\u4e88\u8682\u8681\u548c\u73af\u5883\u4e00\u5b9a\u7684\u8bb0\u5fc6\u80fd\u529b\u80fd\u591f\u5e2e\u52a9\u51cf\u5c11\u641c\u7d22\u7a7a\u95f4 \u4e2a\u4f53\u5206\u5e03\u8d8a\u5747\u5300\uff0c\u79cd\u7fa4\u591a\u6837\u6027\u5c31\u8d8a\u597d\uff0c\u5f97\u5230\u5168\u5c40\u6700\u4f18\u89e3\u7684\u6982\u7387\u5c31\u8d8a\u5927\uff0c\u4f46\u662f\u5bfb\u4f18\u65f6\u95f4\u5c31\u8d8a\u957f\uff1b\u4e2a\u4f53\u5206\u5e03\u8d8a\u96c6\u4e2d\uff0c\u79cd\u7fa4\u591a\u6837\u6027\u5c31\u8d8a\u5dee\uff0c\u4e0d\u5229\u4e8e\u53d1\u6325\u7b97\u6cd5\u7684\u63a2\u7d22\u80fd\u529b\u3002\u6b63\u53cd\u9988\u52a0\u5feb\u4e86\u8681\u7fa4\u7b97\u6cd5\u7684\u6536\u655b\u901f\u5ea6\uff0c\u5374\u4f7f\u7b97\u6cd5\u8f83\u65e9\u5730\u96c6\u4e2d\u4e8e\u90e8\u5206\u5019\u9009\u89e3\uff0c\u56e0\u6b64\u6b63\u53cd\u9988\u964d\u4f4e\u4e86\u79cd\u7fa4\u7684\u591a\u6837\u6027\uff0c\u4e5f\u4e0d\u5229\u4e8e\u63d0\u9ad8\u7b97\u6cd5\u7684\u5168\u5c40\u5bfb\u4f18\u80fd\u529b\u3002 \u4f18\u70b9\uff1a 1\uff09 \u8681\u7fa4\u7b97\u6cd5\u7684\u9c81\u68d2\u6027\u5f3a 2\uff09 \u91c7\u7528\u6b63\u53cd\u9988\u673a\u5236\uff0c\u80fd\u591f\u903c\u8fd1\u6700\u4f18\u89e3 3\uff09 \u6613\u4e0e\u5176\u4ed6\u7b97\u6cd5\u8fdb\u884c\u7ed3\u5408 \u7f3a\u70b9\uff1a 1\uff09 \u76f2\u76ee\u7684\u968f\u673a\u641c\u7d22\uff0c\u641c\u7d22\u65f6\u95f4\u8f83\u957f\uff0c\u641c\u7d22\u901f\u5ea6\u6162 2\uff09 \u8681\u7fa4\u7b97\u6cd5\u5bb9\u6613\u9677\u5165\u5c40\u90e8\u6700\u4f18 3\uff09 \u8681\u7fa4\u7b97\u6cd5\u53c2\u6570\u7684\u9009\u62e9\u4f9d\u8d56\u4e8e\u7ecf\u9a8c\u6216\u8bd5\u9519
\n3.\u9057\u4f20\u7b97\u6cd5
\n\u9057\u4f20\u7b97\u6cd5\uff08Genetic Algorithm\uff0cGA\uff09\u662f\u7531John Holland\u4e8e20\u4e16\u7eaa70\u5e74\u4ee3\u63d0\u51fa\uff0c\u8be5\u7b97\u6cd5\u662f\u6839\u636e\u5927\u81ea\u7136\u4e2d\u751f\u7269\u4f53\u8fdb\u5316\u89c4\u5f8b\u800c\u8bbe\u8ba1\u63d0\u51fa\u7684\uff0c\u6765\u6a21\u62df\u8fbe\u5c14\u6587\u751f\u7269\u8fdb\u5316\u8bba\u7684\u81ea\u7136\u9009\u62e9\u548c\u9057\u4f20\u5b66\u673a\u7406\u7684\u751f\u7269\u8fdb\u5316\u8fc7\u7a0b\u7684\u8ba1\u7b97\u6a21\u578b\uff0c\u662f\u4e00\u79cd\u901a\u8fc7\u6a21\u62df\u81ea\u7136\u8fdb\u5316\u8fc7\u7a0b\u641c\u7d22\u6700\u4f18\u89e3\u7684\u65b9\u6cd5\u3002\u5176\u672c\u8d28\u662f\u4e00\u79cd\u9ad8\u6548\u3001\u5e76\u884c\u3001\u5168\u5c40\u641c\u7d22\u7684\u65b9\u6cd5\uff0c\u80fd\u5728\u641c\u7d22\u8fc7\u7a0b\u4e2d\u81ea\u52a8\u83b7\u53d6\u548c\u79ef\u7d2f\u6709\u5173\u641c\u7d22\u7a7a\u95f4\u7684\u77e5\u8bc6\uff0c\u5e76\u81ea\u9002\u5e94\u5730\u63a7\u5236\u641c\u7d22\u8fc7\u7a0b\u4ee5\u6c42\u5f97\u6700\u4f73\u89e3\u3002 \u9057\u4f20\u7b97\u6cd5\u7684\u6d41\u7a0b\uff1a
\n1.\u8bc4\u4f30\u6bcf\u6761\u67d3\u8272\u4f53\u6240\u5bf9\u5e94\u4e2a\u4f53\u7684\u9002\u5e94\u5ea6
\nWhile\uff08\u672a\u627e\u5230\u6ee1\u610f\u7684\u89e3\uff09\uff1a
\n2.\u9075\u7167\u9002\u5e94\u5ea6\u8d8a\u9ad8\uff0c\u9009\u62e9\u6982\u7387\u8d8a\u5927\u7684\u539f\u5219\uff0c\u4ece\u79cd\u7fa4\u4e2d\u9009\u62e9\u4e24\u4e2a\u4e2a\u4f53\u4f5c\u4e3a\u7236\u65b9\u548c\u6bcd\u65b9
\n3.\u62bd\u53d6\u7236\u6bcd\u53cc\u65b9\u7684\u67d3\u8272\u4f53\uff0c\u8fdb\u884c\u4ea4\u53c9\uff0c\u4ea7\u751f\u5b50\u4ee3
\n4.\u5bf9\u5b50\u4ee3\u7684\u67d3\u8272\u4f53\u8fdb\u884c\u53d8\u5f02
\n12345
\n\u4f18\u70b9\uff1a 1\uff09 \u9057\u4f20\u7b97\u6cd5\u5177\u6709\u5e7f\u6cdb\u7684\u5e94\u7528\u9886\u57df 2\uff09 \u9057\u4f20\u7b97\u6cd5\u5177\u6709\u7fa4\u4f53\u641c\u7d22\u7684\u7279\u6027 3\uff09 \u9057\u4f20\u7b97\u6cd5\u57fa\u4e8e\u6982\u7387\u89c4\u5219\uff0c\u641c\u7d22\u66f4\u4e3a\u7075\u6d3b 4\uff09 \u9057\u4f20\u7b97\u6cd5\u76f4\u63a5\u4ee5\u76ee\u6807\u51fd\u6570\u4f5c\u4e3a\u641c\u7d22\u4fe1\u606f\uff0c\u4e0d\u6d89\u53ca\u76ee\u6807\u51fd\u6570\u503c\u6c42\u5fae\u5206\u7684\u8fc7\u7a0b \u7f3a\u70b9\uff1a 1\uff09 \u9057\u4f20\u7b97\u6cd5\u6548\u7387\u6bd4\u8f83\u4f4e 2\uff09 \u9057\u4f20\u7b97\u6cd5\u5bb9\u6613\u8fc7\u65e9\u6536\u655b 3\uff09 \u9057\u4f20\u7b97\u6cd5\u5728\u7f16\u7801\u65f6\u5bb9\u6613\u51fa\u73b0\u4e0d\u89c4\u8303\u4e0d\u51c6\u786e\u7684\u95ee\u9898
\n \u66f4\u591a\u5185\u5bb9\u8bf7\u5173\u6ce8\u5fae\u4fe1\u516c\u4f17\u53f7\uff1a\u6df1\u5ea6\u5b66\u4e60\u4e0e\u8def\u5f84\u89c4\u5212<\/p>\n","protected":false},"excerpt":{"rendered":"
2021-11-14 \u6587\u7ae0\u76ee\u5f55 \u524d\u8a00\u4e00\u3001\u4f20\u7edf\u8def […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[3,1],"tags":[],"class_list":["post-320","post","type-post","status-publish","format-standard","hentry","category-technology-frontier","category-home"],"views":2,"_links":{"self":[{"href":"http:\/\/222.128.65.89:18086\/index.php\/wp-json\/wp\/v2\/posts\/320"}],"collection":[{"href":"http:\/\/222.128.65.89:18086\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/222.128.65.89:18086\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/222.128.65.89:18086\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/222.128.65.89:18086\/index.php\/wp-json\/wp\/v2\/comments?post=320"}],"version-history":[{"count":1,"href":"http:\/\/222.128.65.89:18086\/index.php\/wp-json\/wp\/v2\/posts\/320\/revisions"}],"predecessor-version":[{"id":326,"href":"http:\/\/222.128.65.89:18086\/index.php\/wp-json\/wp\/v2\/posts\/320\/revisions\/326"}],"wp:attachment":[{"href":"http:\/\/222.128.65.89:18086\/index.php\/wp-json\/wp\/v2\/media?parent=320"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/222.128.65.89:18086\/index.php\/wp-json\/wp\/v2\/categories?post=320"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/222.128.65.89:18086\/index.php\/wp-json\/wp\/v2\/tags?post=320"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}