几种经典算法回顾 Java的数组的几种经典算法

\u51e0\u79cd\u5e38\u7528\u7684\u7b97\u6cd5\u7b80\u4ecb

1\u3001\u7a77\u4e3e\u6cd5\u7a77\u4e3e\u6cd5\u662f\u6700\u57fa\u672c\u7684\u7b97\u6cd5\u8bbe\u8ba1\u7b56\u7565\uff0c\u5176\u601d\u60f3\u662f\u5217\u4e3e\u51fa\u95ee\u9898\u6240\u6709\u7684\u53ef\u80fd\u89e3\uff0c\u9010\u4e00\u8fdb\u884c\u5224\u522b\uff0c\u627e\u51fa\u6ee1\u8db3\u6761\u4ef6\u7684\u89e3\u3002
\u7a77\u4e3e\u6cd5\u7684\u8fd0\u7528\u5173\u952e\u5728\u4e8e\u89e3\u51b3\u4e24\u4e2a\u95ee\u9898\uff1a
\u5728\u8fd0\u7528\u7a77\u4e3e\u6cd5\u65f6\uff0c\u5bb9\u6613\u51fa\u73b0\u7684\u95ee\u9898\u662f\u53ef\u80fd\u89e3\u8fc7\u591a\uff0c\u5bfc\u81f4\u7b97\u6cd5\u6548\u7387\u5f88\u4f4e\uff0c\u8fd9\u5c31\u9700\u8981\u5bf9\u5217\u4e3e\u53ef\u80fd\u89e3\u7684\u65b9\u6cd5\u8fdb\u884c\u4f18\u5316\u3002
\u4ee5\u98981041--\u7eaf\u7d20\u6570\u95ee\u9898\u4e3a\u4f8b\uff0c\u4ece1000\u52309999\u90fd\u53ef\u4ee5\u770b\u4f5c\u662f\u53ef\u80fd\u89e3\uff0c\u53ef\u4ee5\u901a\u8fc7\u5bf9\u6240\u6709\u8fd9\u4e9b\u53ef\u80fd\u89e3\u9010\u4e00\u8fdb\u884c\u5224\u522b\uff0c\u627e\u51fa\u5176\u4e2d\u7684\u7eaf\u7d20\u6570\uff0c\u4f46\u53ea\u8981\u7a0d\u4f5c\u5206\u6790\uff0c\u5c31\u4f1a\u53d1\u73b0\u5176\u5b9e\u53ef\u4ee5\u5927\u5e45\u5ea6\u5730\u964d\u4f4e\u53ef\u80fd\u89e3\u7684\u8303\u56f4\u3002\u6839\u636e\u9898\u610f\u6613\u77e5\uff0c\u4e2a\u4f4d\u53ea\u53ef\u80fd\u662f3\u30015\u30017\uff0c\u518d\u6839\u636e\u9898\u610f\u53ef\u77e5\uff0c\u53ef\u4ee5\u57283\u30015\u30017\u7684\u57fa\u7840\u4e0a\uff0c\u5148\u627e\u51fa\u6240\u6709\u7684\u4e8c\u4f4d\u7eaf\u7d20\u6570\uff0c\u518d\u5728\u4e8c\u4f4d\u7eaf\u7d20\u6570\u57fa\u7840\u4e0a\u627e\u51fa\u4e09\u4f4d\u7eaf\u7d20\u6570\uff0c\u6700\u540e\u5728\u4e09\u4f4d\u7eaf\u7d20\u6570\u7684\u57fa\u7840\u4e0a\u627e\u51fa\u6240\u6709\u7684\u56db\u4f4d\u7eaf\u7d20\u6570\u3002
2\u3001\u5206\u6cbb\u6cd5\u5206\u6cbb\u6cd5\u4e5f\u662f\u5e94\u7528\u975e\u5e38\u5e7f\u6cdb\u7684\u4e00\u79cd\u7b97\u6cd5\u8bbe\u8ba1\u7b56\u7565\uff0c\u5176\u601d\u60f3\u662f\u5c06\u95ee\u9898\u5206\u89e3\u4e3a\u82e5\u5e72\u5b50\u95ee\u9898\uff0c\u4ece\u800c\u53ef\u4ee5\u9012\u5f52\u5730\u6c42\u89e3\u5404\u5b50\u95ee\u9898\uff0c\u518d\u7efc\u5408\u51fa\u95ee\u9898\u7684\u89e3\u3002
\u5206\u6cbb\u6cd5\u7684\u8fd0\u7528\u5173\u952e\u5728\u4e8e\u89e3\u51b3\u4e09\u4e2a\u95ee\u9898\uff1a
\u6211\u4eec\u719f\u77e5\u7684\u5982\u6c49\u8bfa\u5854\u95ee\u9898\u3001\u6298\u534a\u67e5\u627e\u7b97\u6cd5\u3001\u5feb\u901f\u6392\u5e8f\u7b97\u6cd5\u7b49\u90fd\u662f\u5206\u6cbb\u6cd5\u8fd0\u7528\u7684\u5178\u578b\u6848\u4f8b\u3002
\u4ee5\u98981045--Square Coins\u4e3a\u4f8b\uff0c\u5148\u5bf9\u9898\u610f\u8fdb\u884c\u5206\u6790\uff0c\u53ef\u8bbe\u4e00\u4e2a\u51fd\u6570f(m, n)\u7b49\u4e8e\u7528\u9762\u503c\u4e0d\u8d85\u8fc7n2\u7684\u8d27\u5e01\u6784\u6210\u603b\u503c\u4e3am\u7684\u65b9\u6848\u6570\uff0c\u5219\u5bb9\u6613\u63a8\u5bfc\u51fa\uff1a
f(m, n) = f(m-0*n*n, n-1)+f(m-1*n*n, n-1)+f(m-2*n*n, n-1)+...+f(m-k*n*n, n-1)
\u8fd9\u91cc\u7684k\u662f\u5e01\u503c\u4e3an2\u7684\u8d27\u5e01\u6700\u591a\u53ef\u4ee5\u7528\u591a\u5c11\u679a\uff0c\u5373k=m/(n*n)\u3002
\u4e5f\u5f88\u5bb9\u6613\u5206\u6790\u51fa\uff0cf(m, 1) = f(1, n) = 1
\u5bf9\u4e8e\u8fd9\u6837\u7684\u9898\u76ee\uff0c\u4e00\u65e6\u5206\u6790\u51fa\u4e86\u9012\u63a8\u516c\u5f0f\uff0c\u7a0b\u5e8f\u5c31\u975e\u5e38\u597d\u5199\u4e86\u3002\u6240\u4ee5\u5728\u52a8\u624b\u5f00\u59cb\u5199\u7a0b\u5e8f\u4e4b\u524d\uff0c\u5206\u6790\u5de5\u4f5c\u505a\u5f97\u8d8a\u5f7b\u5e95\uff0c\u903b\u8f91\u63cf\u8ff0\u8d8a\u51c6\u786e\u3001\u7b80\u6d01\uff0c\u5199\u8d77\u7a0b\u5e8f\u6765\u5c31\u4f1a\u8d8a\u5bb9\u6613\u3002
3\u3001\u52a8\u6001\u89c4\u5212\u6cd5
\u52a8\u6001\u89c4\u5212\u6cd5\u591a\u7528\u6765\u8ba1\u7b97\u6700\u4f18\u95ee\u9898\uff0c\u52a8\u6001\u89c4\u5212\u6cd5\u4e0e\u5206\u6cbb\u6cd5\u7684\u57fa\u672c\u601d\u60f3\u662f\u4e00\u81f4\u7684\uff0c\u4f46\u5904\u7406\u7684\u624b\u6cd5\u4e0d\u540c\u3002\u52a8\u6001\u89c4\u5212\u6cd5\u5728\u8fd0\u7528\u65f6\uff0c\u8981\u5148\u5bf9\u95ee\u9898\u7684\u5206\u6cbb\u89c4\u5f8b\u8fdb\u884c\u5206\u6790\uff0c\u627e\u51fa\u7ec8\u7ed3\u5b50\u95ee\u9898\uff0c\u4ee5\u53ca\u5b50\u95ee\u9898\u5411\u7236\u95ee\u9898\u5f52\u7eb3\u7684\u89c4\u5219\uff0c\u800c\u7b97\u6cd5\u5219\u76f4\u63a5\u4ece\u7ec8\u7ed3\u5b50\u95ee\u9898\u5f00\u59cb\u6c42\u89e3\uff0c\u9010\u5c42\u5411\u4e0a\u5f52\u7eb3\uff0c\u76f4\u5230\u5f52\u7eb3\u51fa\u539f\u95ee\u9898\u7684\u89e3\u3002
\u52a8\u6001\u89c4\u5212\u6cd5\u591a\u7528\u4e8e\u5728\u5206\u6cbb\u8fc7\u7a0b\u4e2d\uff0c\u5b50\u95ee\u9898\u53ef\u80fd\u91cd\u590d\u51fa\u73b0\u7684\u60c5\u51b5\uff0c\u5728\u8fd9\u79cd\u60c5\u51b5\u4e0b\uff0c\u5982\u679c\u6309\u7167\u5e38\u89c4\u7684\u5206\u6cbb\u6cd5\uff0c\u81ea\u4e0a\u5411\u4e0b\u5206\u6cbb\u6c42\u89e3\uff0c\u5219\u91cd\u590d\u51fa\u73b0\u7684\u5b50\u95ee\u9898\u5c31\u4f1a\u88ab\u91cd\u590d\u5730\u6c42\u89e3\uff0c\u4ece\u800c\u589e\u5927\u4e86\u5197\u4f59\u8ba1\u7b97\u91cf\uff0c\u964d\u4f4e\u4e86\u6c42\u89e3\u6548\u7387\u3002\u800c\u91c7\u7528\u52a8\u6001\u89c4\u5212\u6cd5\uff0c\u81ea\u5e95\u5411\u4e0a\u6c42\u89e3\uff0c\u6bcf\u4e2a\u5b50\u95ee\u9898\u53ea\u8ba1\u7b97\u4e00\u6b21\uff0c\u5c31\u53ef\u4ee5\u907f\u514d\u8fd9\u79cd\u91cd\u590d\u7684\u6c42\u89e3\u4e86\u3002
\u52a8\u6001\u89c4\u5212\u6cd5\u8fd8\u6709\u53e6\u5916\u4e00\u79cd\u5b9e\u73b0\u5f62\u5f0f\uff0c\u5373\u5907\u5fd8\u5f55\u6cd5\u3002\u5907\u5fd8\u5f55\u7684\u57fa\u672c\u601d\u60f3\u662f\u8bbe\u7acb\u4e00\u4e2a\u79f0\u4e3a\u5907\u5fd8\u5f55\u7684\u5bb9\u5668\uff0c\u8bb0\u5f55\u5df2\u7ecf\u6c42\u5f97\u89e3\u7684\u5b50\u95ee\u9898\u53ca\u5176\u89e3\u3002\u4ecd\u7136\u91c7\u7528\u4e0e\u5206\u6cbb\u6cd5\u76f8\u540c\u7684\u81ea\u4e0a\u5411\u4e0b\u5206\u6cbb\u6c42\u89e3\u7684\u7b56\u7565\uff0c\u53ea\u662f\u5bf9\u6bcf\u4e00\u4e2a\u5206\u89e3\u51fa\u7684\u5b50\u95ee\u9898\uff0c\u5148\u5728\u5907\u5fd8\u5f55\u4e2d\u67e5\u627e\u8be5\u5b50\u95ee\u9898\uff0c\u5982\u679c\u5907\u5fd8\u5f55\u4e2d\u5df2\u7ecf\u5b58\u5728\u8be5\u5b50\u95ee\u9898\uff0c\u5219\u4e0d\u987b\u518d\u6c42\u89e3\uff0c\u53ef\u4ee5\u4ece\u5907\u5fd8\u5f55\u4e2d\u76f4\u63a5\u5f97\u5230\u89e3\uff0c\u5426\u5219\uff0c\u5bf9\u5b50\u95ee\u9898\u9012\u5f52\u6c42\u89e3\uff0c\u4e14\u6bcf\u6c42\u5f97\u4e00\u4e2a\u5b50\u95ee\u9898\u7684\u89e3\uff0c\u90fd\u5c06\u5b50\u95ee\u9898\u53ca\u89e3\u5b58\u5165\u5907\u5fd8\u5f55\u4e2d\u3002
\u4f8b\u5982\uff0c\u5728\u98981045--Square Coins\u4e2d\uff0c\u53ef\u4ee5\u91c7\u7528\u5206\u6cbb\u6cd5\u6c42\u89e3\uff0c\u4e5f\u53ef\u4ee5\u91c7\u7528\u52a8\u6001\u89c4\u5212\u6cd5\u6c42\u89e3\uff0c\u5373\u4ecef(m, 1)\u548cf(1, n)\u51fa\u53d1\uff0c\u9010\u5c42\u5411\u4e0a\u8ba1\u7b97\uff0c\u76f4\u5230\u6c42\u5f97f(m, n)\u3002
\u5728\u7ade\u8d5b\u4e2d\uff0c\u52a8\u6001\u89c4\u5212\u548c\u5907\u5fd8\u5f55\u7684\u601d\u60f3\u8fd8\u53ef\u4ee5\u6709\u53e6\u4e00\u79cd\u7528\u6cd5\u3002\u6709\u4e9b\u9898\u76ee\u4e2d\u7684\u53ef\u80fd\u95ee\u9898\u6570\u662f\u6709\u9650\u7684\uff0c\u800c\u5728\u4e00\u6b21\u8fd0\u884c\u4e2d\u53ef\u80fd\u9700\u8981\u8ba1\u7b97\u591a\u4e2a\u6d4b\u8bd5\u7528\u4f8b\uff0c\u53ef\u4ee5\u91c7\u7528\u5907\u5fd8\u5f55\u7684\u65b9\u6cd5\uff0c\u9884\u5148\u5c06\u6240\u6709\u7684\u95ee\u9898\u7684\u89e3\u8bb0\u5f55\u4e0b\u6765\uff0c\u7136\u540e\u8f93\u5165\u4e00\u4e2a\u6d4b\u8bd5\u7528\u4f8b\uff0c\u5c31\u67e5\u5907\u5fd8\u5f55\uff0c\u76f4\u63a5\u627e\u5230\u7b54\u6848\u8f93\u51fa\u3002\u8fd9\u5728\u5404\u95ee\u9898\u4e4b\u95f4\u5b58\u5728\u7236\u5b50\u5173\u7cfb\u7684\u60c5\u51b5\u4e0b\uff0c\u4f1a\u66f4\u6709\u6548\u3002\u4f8b\u5982\uff0c\u5728\u98981045--Square Coins\u4e2d\uff0c\u9898\u76ee\u4e2d\u5df2\u7ecf\u6307\u51fa\u4e86\u6700\u5927\u7684\u76ee\u6807\u5e01\u503c\u4e0d\u8d85\u8fc7300\uff0c\u4e5f\u5c31\u662f\u8bf4\u95ee\u9898\u6570\u53ea\u6709300\u4e2a\uff0c\u800c\u4e14\u5404\u95ee\u9898\u7684\u8ba1\u7b97\u4e2d\u5b58\u5728\u91cd\u53e0\u7684\u5b50\u95ee\u9898\uff0c\u53ef\u4ee5\u91c7\u7528\u52a8\u6001\u89c4\u5212\u6cd5\uff0c\u5c06\u6240\u6709\u95ee\u9898\u7684\u89e3\u5148\u5168\u90e8\u8ba1\u7b97\u51fa\u6765\uff0c\u518d\u4f9d\u6b21\u8f93\u5165\u6d4b\u8bd5\u7528\u4f8b\u6570\u636e\uff0c\u5e76\u76f4\u63a5\u8f93\u51fa\u7b54\u6848\u3002
4\u3001\u56de\u6eaf\u6cd5\u56de\u6eaf\u6cd5\u662f\u57fa\u4e8e\u95ee\u9898\u72b6\u6001\u6811\u641c\u7d22\u7684\u6c42\u89e3\u6cd5\uff0c\u5176\u53ef\u9002\u7528\u8303\u56f4\u5f88\u5e7f\u3002\u4ece\u67d0\u79cd\u89d2\u5ea6\u4e0a\u8bf4\uff0c\u53ef\u4ee5\u628a\u56de\u6eaf\u6cd5\u770b\u4f5c\u662f\u4f18\u5316\u4e86\u7684\u7a77\u4e3e\u6cd5\u3002\u56de\u6eaf\u6cd5\u7684\u57fa\u672c\u601d\u60f3\u662f\u9010\u6b65\u6784\u9020\u95ee\u9898\u7684\u53ef\u80fd\u89e3\uff0c\u4e00\u8fb9\u6784\u9020\uff0c\u4e00\u8fb9\u7528\u7ea6\u675f\u6761\u4ef6\u8fdb\u884c\u5224\u522b\uff0c\u4e00\u65e6\u53d1\u73b0\u5df2\u7ecf\u4e0d\u53ef\u80fd\u6784\u9020\u51fa\u6ee1\u8db3\u6761\u4ef6\u7684\u89e3\u4e86\uff0c\u5219\u9000\u56de\u4e0a\u4e00\u6b65\u6784\u9020\u8fc7\u7a0b\uff0c\u91cd\u65b0\u8fdb\u884c\u6784\u9020\u3002\u8fd9\u4e2a\u9000\u56de\u7684\u8fc7\u7a0b\uff0c\u5c31\u79f0\u4e4b\u4e3a\u56de\u6eaf\u3002
\u56de\u6eaf\u6cd5\u5728\u8fd0\u7528\u65f6\uff0c\u8981\u89e3\u51b3\u7684\u5173\u952e\u95ee\u9898\u5728\u4e8e\uff1a
\u56de\u6eaf\u6cd5\u7684\u7ecf\u5178\u6848\u4f8b\u4e5f\u5f88\u591a\uff0c\u4f8b\u5982\u5168\u6392\u5217\u95ee\u9898\u3001N\u540e\u95ee\u9898\u7b49\u3002
5\u3001\u8d2a\u5fc3\u6cd5\u8d2a\u5fc3\u6cd5\u4e5f\u662f\u6c42\u89e3\u6700\u4f18\u95ee\u9898\u7684\u5e38\u7528\u7b97\u6cd5\u7b56\u7565\uff0c\u5229\u7528\u8d2a\u5fc3\u6cd5\u7b56\u7565\u6240\u8bbe\u8ba1\u7684\u7b97\u6cd5\uff0c\u901a\u5e38\u6548\u7387\u8f83\u9ad8\uff0c\u7b97\u6cd5\u7b80\u5355\u3002\u8d2a\u5fc3\u6cd5\u7684\u57fa\u672c\u601d\u60f3\u662f\u5bf9\u95ee\u9898\u505a\u51fa\u76ee\u524d\u770b\u6765\u6700\u597d\u7684\u9009\u62e9\uff0c\u5373\u8d2a\u5fc3\u9009\u62e9\uff0c\u5e76\u4f7f\u95ee\u9898\u8f6c\u5316\u4e3a\u89c4\u6a21\u66f4\u5c0f\u7684\u5b50\u95ee\u9898\u3002\u5982\u6b64\u8fed\u4ee3\uff0c\u76f4\u5230\u5b50\u95ee\u9898\u53ef\u4ee5\u76f4\u63a5\u6c42\u89e3\u3002
\u57fa\u4e8e\u8d2a\u5fc3\u6cd5\u7684\u7ecf\u5178\u7b97\u6cd5\u4f8b\u5982\uff1a\u54c8\u592b\u66fc\u7b97\u6cd5\u3001\u6700\u5c0f\u751f\u6210\u6811\u7b97\u6cd5\u3001\u6700\u77ed\u8def\u5f84\u7b97\u6cd5\u7b49\u3002

JAVA\u4e2d\u5728\u8fd0\u7528\u6570\u7ec4\u8fdb\u884c\u6392\u5e8f\u529f\u80fd\u65f6\uff0c\u4e00\u822c\u6709\u56db\u79cd\u65b9\u6cd5\uff1a\u5feb\u901f\u6392\u5e8f\u6cd5\u3001\u5192\u6ce1\u6cd5\u3001\u9009\u62e9\u6392\u5e8f\u6cd5\u3001\u63d2\u5165\u6392\u5e8f\u6cd5\u3002
\u5feb\u901f\u6392\u5e8f\u6cd5\u4e3b\u8981\u662f\u8fd0\u7528\u4e86Arrays\u4e2d\u7684\u4e00\u4e2a\u65b9\u6cd5Arrays.sort\uff08\uff09\u5b9e\u73b0\u3002
\u5192\u6ce1\u6cd5\u662f\u8fd0\u7528\u904d\u5386\u6570\u7ec4\u8fdb\u884c\u6bd4\u8f83\uff0c\u901a\u8fc7\u4e0d\u65ad\u7684\u6bd4\u8f83\u5c06\u6700\u5c0f\u503c\u6216\u8005\u6700\u5927\u503c\u4e00\u4e2a\u4e00\u4e2a\u7684\u904d\u5386\u51fa\u6765\u3002
\u9009\u62e9\u6392\u5e8f\u6cd5\u662f\u5c06\u6570\u7ec4\u7684\u7b2c\u4e00\u4e2a\u6570\u636e\u4f5c\u4e3a\u6700\u5927\u6216\u8005\u6700\u5c0f\u7684\u503c\uff0c\u7136\u540e\u901a\u8fc7\u6bd4\u8f83\u5faa\u73af\uff0c\u8f93\u51fa\u6709\u5e8f\u7684\u6570\u7ec4\u3002
\u63d2\u5165\u6392\u5e8f\u662f\u9009\u62e9\u4e00\u4e2a\u6570\u7ec4\u4e2d\u7684\u6570\u636e\uff0c\u901a\u8fc7\u4e0d\u65ad\u7684\u63d2\u5165\u6bd4\u8f83\u6700\u540e\u8fdb\u884c\u6392\u5e8f\u3002\u4e0b\u9762\u6211\u5c31\u5c06\u4ed6\u4eec\u7684\u5b9e\u73b0\u65b9\u6cd5\u4e00\u4e00\u8be6\u89e3\u4f9b\u5927\u5bb6\u53c2\u8003\u3002
\u5229\u7528Arrays\u5e26\u6709\u7684\u6392\u5e8f\u65b9\u6cd5\u5feb\u901f\u6392\u5e8f


public class Test2{ public static void main(String[] args){ int[] a={5,4,2,4,9,1}; Arrays.sort(a); //\u8fdb\u884c\u6392\u5e8f for(int i: a){ System.out.print(i); } } }


\u5192\u6ce1\u6392\u5e8f\u7b97\u6cd5




public static int[] bubbleSort(int[] args){//\u5192\u6ce1\u6392\u5e8f\u7b97\u6cd5 for(int i=0;iargs[j]){ int temp=args[i]; args[i]=args[j]; args[j]=temp; } } } return args; }


\u9009\u62e9\u6392\u5e8f\u7b97\u6cd5


public static int[] selectSort(int[] args){//\u9009\u62e9\u6392\u5e8f\u7b97\u6cd5 for (int i=0;iargs[j]){ min=j; } } if (min!=i){ int temp=args[i]; args[i]=args[min]; args[min]=temp; } } return args; }


\u63d2\u5165\u6392\u5e8f\u7b97\u6cd5

public static int[] insertSort(int[] args){//\u63d2\u5165\u6392\u5e8f\u7b97\u6cd5 for(int i=1;i0;j--){ if (args[j]<args[j-1]){ int temp=args[j-1]; args[j-1]=args[j]; args[j]=temp; }else break; } } return args; }

今天无意中从箱子里发现了大学时学算法的教材《算法设计与分析》，虽然工作这么几年没在什么地方用过算法，但算法的思想还是影响深刻的，可以在系统设计时提供一些思路。大致翻了翻，重温了一下几种几种经典的算法，做一下小结。分治法动态规划贪心算法回溯法分支限界法分治法1）基本思想将一个问题分解为多个规模较小的子问题，这些子问题互相独立并与原问题解决方法相同。递归解这些子问题，然后将这各子问题的解合并得到原问题的解。2）适用问题的特征该问题的规模缩小到一定的程度就可以容易地解决该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题3）关键如何将问题分解为规模较小并且解决方法相同的问题分解的粒度4）步骤分解->递归求解->合并 divide-and-conquer(P) { if ( | P | <= n0) adhoc(P); //解决小规模的问题 divide P into smaller subinstances P1,P2,...,Pk；//分解问题 for (i=1,i<=k,i++) yi=divide-and-conquer(Pi); //递归的解各子问题 return merge(y1,...,yk); //将各子问题的解合并为原问题的解 }google的核心算法MapReduce其实就是分治法的衍生5）分治法例子：合并排序规约过程：动态规划1）基本思想将待求解问题分解成若干个子问题，但是经分解得到的子问题往往不是互相独立的，如果能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，就可以避免大量重复计算2）适用问题的特征最优子结构在递归计算中，许多子问题被重复计算多次3）步骤找出最优解的性质，并刻划其结构特征。递归地定义最优值。以自底向上的方式计算出最优值。根据计算最优值时得到的信息，构造最优解。贪心算法1）基本思想贪心算法总是作出在当前看来最好的选择。也就是说贪心算法并不从整体最优考虑，它所作出的选择只是在某种意义上的局部最优选择2）适用问题的特征贪心选择性质，即所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到。最优子结构性质3）步骤：不断寻找局部最优解4）例子：找硬币，哈夫曼编码，单源最短路径，最小生成树（Prim和Kruskal） 最小生成树图示：回溯法1）基本思想在问题的解空间树中，按深度优先策略，从根结点出发搜索解空间树。算法搜索至解空间树的任意一点时，先判断该结点是否包含问题的解。如果肯定不包含，则跳过对该结点为根的子树的搜索，逐层向其祖先结点回溯；否则，进入该子树，继续按深度优先策略搜索2）适用问题的特征：容易构建所解问题的解空间3）步骤定义问题的解空间 确定易于搜索的解空间结构以深度优先方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索 4）回溯法例子：N皇后问题分支限界法1）基本思想分支限界法常以广度优先或以最小耗费（最大效益）优先的方式搜索问题的解空间树。 在分支限界法中，每一个活结点只有一次机会成为扩展结点。活结点一旦成为扩展结点，就一次性产生其所有儿子结点。在这些儿子结点中，导致不可行解或导致非最优解的儿子结点被舍弃，其余儿子结点被加入活结点表中。此后，从活结点表中取下一结点成为当前扩展结点，并重复上述结点扩展过程。这个过程一直持续到找到所需的解或活结点表为空时为止。2）分支限界法例子：单源最短路径问题问题描述：在下图所给的有向图G中，每一边都有一个非负边权。

CEF鎶鏈矾鐢卞櫒浜ゆ崲绠楁硶鐨勭畝鍗鍥為【
绛旓細濡傞绻佺殑缃戠粶鎷撴墤鍙樺寲鍜岃矾鐢辫皟鏁达紝鍏堕珮閫熺紦瀛橀噸寤烘垚鏈珮涓旀晥鐜囦綆涓嬶紝鏃犳硶婊¤冻瀹炴椂鏁版嵁娴佸闀跨殑闇姹傘備负瑙ｅ喅杩欎簺闂锛孋EF鐗瑰揩浜ゆ崲鎶鏈簲杩愯岀敓銆傚畠閽堝鍔ㄦ佽矾鐢辩幆澧冨拰瀹炴椂鏁版嵁娴侀噺鐨勭壒鎬э紝璁捐鍑轰竴绉嶆洿涓洪珮鏁堢殑浜ゆ崲绛栫暐锛屾棬鍦ㄥ厠鏈嶅揩閫熶氦鎹㈠湪鍔ㄦ佹у拰瀹炴椂鎬ф柟闈㈢殑涓嶈冻锛屼粠鑰屾彁楂樿矾鐢卞櫒鐨勬暣浣撴ц兘銆

濡備綍鏈绠鍗曘侀氫織鍦扮悊瑙ｉ昏緫鍥炲綊绠楁硶?
绛旓細鐒惰岋紝褰撻潰瀵归潪杩炵画鐨勭被鍒彉閲忥紝濡"澶"涓"灏"锛"榛"涓"鐧"锛屾垜浠渶瑕佸皢杩欑闈炵嚎鎬ч棶棰樿浆鎹负姒傜巼闂銆備簬鏄紝鎴戜滑寮曞叆姒傜巼姒傚康锛屽皢绾挎у洖褰掔殑杈撳嚭鍊兼槧灏勫埌姒傜巼鍖洪棿锛屾瘮濡傞氳繃Sigmoid鍑芥暟锛屽皢绾挎у兼槧灏勫埌(0, 1)涔嬮棿锛岃繖灏辨槸閫昏緫鍥炲綊鐨勮捣鐐广傞昏緫鐨勯瓍鍔涳細鏄犲皠鍑芥暟鐨勯夋嫨 鏈鍑犵甯歌鐨勬槧灏勫嚱鏁板彲渚涢夋嫨...

鐩爣妫娴绠楁硶---faster rcnn 鐭ヨ瘑绠瑕鍥為【(娴嬭瘯绡)
绛旓細2.RPN锛圧egion Proposal Network锛夛細鐢ㄤ簬浜х敓鍊欓夋锛屼富瑕佸仛涓浜涚矖绯欑殑鍒嗙被鍜屽洖褰掓搷浣滐紱3.RoI Pooling锛氫富瑕佹槸涓轰簡瑙ｅ喅鍏ㄨ繛鎺ュ眰闇瑕佸浐瀹氬昂瀵歌緭鍏ワ紝鑰屽疄闄呰緭鍏ュぇ灏忎笉涓鐨勯棶棰橈紱4.Classification and Regression锛氱簿缁嗗寲鍒嗙被鍜屽洖褰掋俧aster rcnn绠楁硶澶ц嚧娴佺▼濡備笅锛氬僵鑹插浘鍍忛氳繃backbone杩涜鐗瑰緛鎻愬彇锛岃緭鍑烘渶鍚庝竴灞傜殑...

銆绠楁硶 - 鍔ㄦ佽鍒掋戞壘闆堕挶闂鈪
绛旓細鍔ㄦ佽鍒掔殑绮鹃珦鍦ㄤ簬琛ㄤ緷璧栧拰璁板繂鍖栵紝瀹冨阀濡欏湴灏嗗鏉傞棶棰樿浆鍖栦负瀛愰棶棰樼殑缁勫悎銆傚湪杩欎釜鎵鹃浂閽遍棶棰樹腑锛岄氳繃涓ユ牸閬靛畧鐘舵佽浆绉绘柟绋嬶紝鎴戜滑涓嶄粎娑堥櫎浜嗗浣欑殑for寰幆锛岃繕鎻愬崌浜嗕唬鐮佺殑鏁堢巼鍜屽彲璇绘с傛帉鎻″姩鎬佽鍒掔殑杩欎簺鎶宸э紝灏卞鍚屼负绠楁硶澶у帵濂犲畾鍧氬浐鐨勫熀纭锛鍥為【杩囧幓鐨勭瘒绔狅紝浣犲皢鍙戠幇姣忎竴涓ā鍨嬮兘鍦ㄤ负瑙ｅ喅鏂伴棶棰樻彁渚...

鎺ㄨ崘绠楁硶涔嬧擣M
绛旓細鍦ㄥ睍绀篎M绠楁硶涔嬪墠锛屾垜浠厛鍥為【涓涓嬫渶甯歌鐨勭嚎鎬ц〃杈惧紡锛氬叾涓璠鍥剧墖涓婁紶澶辫触W0涓哄垵濮嬫潈閲嶅硷紝鎴栬呯悊瑙ｄ负鍋忕疆椤癸紝Wi涓烘瘡涓壒寰 xi 瀵瑰簲鐨勬潈閲嶅硷紝鍙互鐪嬪埌锛岃繖绉嶇嚎鎬ц〃杈惧紡鍙弿杩颁簡姣忎釜鐗瑰緛鍜岃緭鍑虹殑鍏崇郴銆侳M鐨勮〃杈惧紡濡備笅锛屽彲瑙傚療鍒帮紝鍙槸鍦ㄧ嚎鎬ц〃杈惧紡鍚庨潰鍔犲叆浜嗘柊鐨勪氦鍙夐」鐗瑰緛鍙婂搴旂殑鏉冨笺1锛夊鎵句氦鍙夐」 FM...

绠楁硶浜ゆ槗鍘嗗彶鍥為【
绛旓細鐒惰岋紝杩欎簺绛栫暐锛岀粺绉颁负鈥滅▼搴忓寲浜ゆ槗鈥濓紝鏇捐鎵硅瘎涓1987骞磋偂甯傚嵄鏈虹殑鍙兘鍘熷洜涔嬩竴銆傝繘鍏90骞翠唬锛岄殢鐫鐢典俊缃戠粶鐨勯閫熷彂灞曪紝閲戣瀺甯傚満鍏ㄩ潰鐢靛瓙鍖栵紝缇庡浗瀹炴柦浜嗙櫨鍒嗕綅鎶ヤ环鏀归潻锛岄檷浣庝簡浜ゆ槗鎴愭湰锛屼絾鍚屾椂涔熸帹鍔ㄤ簡绠楁硶浜ゆ槗鐨勫彂灞曪紝浠ラ傚簲闄嶄綆鐨勬祦鍔ㄦс備负浼樺寲浜ゆ槗锛屾満鏋勬姇璧勮呭紑濮嬪皢浜ゆ槗鎸囦护鎷嗗垎涓虹畻娉曪紝濡傚湪TWAP鎴朧WAP...

6. Actor-Critic绠楁硶
绛旓細鏈枃涓昏浠嬬粛濡備笅鍑犱釜鍐呭锛氶鍏堟垜浠繕鏄鍥為【涓涓嬩箣鍓嶆彁鍒扮殑REINFORCE绠楁硶锛氬湪杩欎釜绠楁硶鐨勭浜屾楠ら噷闈㈡垜浠紩鍏ヤ簡鈥渞eward to go鈥濊繖涓椤癸紝璇 琛ㄧず浜嗕粠褰撳墠鐨勬椂闂存t寮濮嬶紝鎵鏈夌殑reward鐨勬湡鏈涗箣鍜屻傛垜浠彲浠ユ妸杩欎釜鐢眂asuality寮曞嚭鐨勬湡鏈涚О涔嬩负鈥渢rue expected reward-to-go鈥濓紝 涔嬫墍浠ユ垜浠繖閲岃冭檻鐨勬槸鏈熸湜...

鍗″皵鏇兼护娉:鍩烘湰鍘熺悊銆绠楁硶鎺ㄥ銆佸疄璺靛簲鐢ㄤ笌鍓嶆部杩涘睍
绛旓細鏁翠釜绾挎у崱灏旀浖婊ゆ尝鐨勫疄鐜帮紝渚濊禆浜庝簲涓叧閿柟绋嬶紝鍒嗕负鏃堕棿鏇存柊鍜岄噺娴嬫洿鏂颁袱涓樁娈碉紝閫氳繃(A, B, H)鍜屽櫔澹扮煩闃(Q, R)杩涜杩唬澶勭悊銆傝鎴戜滑鍥為【涓涓疄闄呭簲鐢ㄦ渚嬶細鍒╃敤纾佸己璁★紙mag锛夊拰鎯ф祴閲忓崟鍏冿紙IMU锛夎繘琛岀粍鍚堝鑸椂锛屽崱灏旀浖婊ゆ尝鍙戞尌浜嗘樉钁椾綔鐢ㄣ傚垵濮嬫椂锛屽畠琚涓洪粦绠绠楁硶锛屼絾娣卞叆鍒嗘瀽鍚庯紝鎴戜滑鍙戠幇鍏...

绁炵粡缃戠粶绠楁硶
绛旓細鎴戜滑鍥為【涓涓嬬缁忕綉缁滃彂灞曠殑鍘嗙▼銆傜缁忕綉缁滅殑鍙戝睍鍘嗗彶鏇叉姌鑽℃季,鏃㈡湁琚汉鎹т笂澶╃殑鏃跺埢,涔熸湁鎽旇惤鍦ㄨ澶存棤浜洪棶娲ョ殑鏃舵,涓棿缁忓巻浜嗘暟娆″ぇ璧峰ぇ钀姐 浠庡崟灞傜缁忕綉缁(鎰熺煡鏈)寮濮,鍒板寘鍚竴涓殣钘忓眰鐨勪袱灞傜缁忕綉缁,鍐嶅埌澶氬眰鐨勬繁搴︾缁忕綉缁,涓鍏辨湁涓夋鍏磋捣杩囩▼銆傝瑙佷笅鍥俱 鎴戜滑甯屾湜鏈⼀涓绠楁硶,鑳借鎴戜滑鎵惧埌鏉冮噸鍜屽亸缃...

鎷撳睍娆у嚑閲屽緱绠楁硶(Extended Euclidean)
绛旓細鑰屽湪澶у悕榧庨紟鐨凴SA绠楁硶涓氨鏈夎繖鏍蜂竴姝ラ渶瑕佹眰鍊掓暟鐨勬ā锛屽苟涓旇繕澶氬姞浜嗕竴涓檺鍒舵潯浠跺嵆a涓巒浜掕川銆傛嫇灞曟鍑犻噷寰(绠绉癊EA) 浜哄鍏跺悕鏄熀浜庢鍑犻噷寰楃畻娉(EA) 鐨勶紝閭ｄ箞鎴戜滑鏉鍥為【涓嬪皬瀛︽墍瀛︽庝箞姹備袱涓暟m,n鐨勬渶灏忓叕绾︽暟 濡傛灉杩欎釜鍏紡杩樻病鍕捐捣浣犵殑鍥炲繂锛岄偅涔堟垜浠潵涓娈佃绠楄繃绋嬪惂銆傝繖閲屾垜浠眰39鍜69鐨勬渶...

扩展阅读：人工智能十大经典算法 ... 计算机五大经典算法 ... 几种常见的排序算法 ... 十大经典优化算法 ... 数据挖掘十大算法 ... 十大基本算法 ... 几种基本算法 ... 算法工程师老了怎么办 ... 双重∑∑求和用法 ...