{"id":180,"date":"2021-07-20T13:53:45","date_gmt":"2021-07-20T05:53:45","guid":{"rendered":"https:\/\/aisumura.net\/blog\/?p=180"},"modified":"2021-09-20T23:26:36","modified_gmt":"2021-09-20T15:26:36","slug":"%e6%bc%94%e7%ae%97%e6%b3%951a-search-algorithm","status":"publish","type":"post","link":"https:\/\/aisumura.net\/blog\/2021\/07\/20\/%e6%bc%94%e7%ae%97%e6%b3%951a-search-algorithm\/","title":{"rendered":"\u6f14\u7b97\u6cd5(1)A* Search Algorithm"},"content":{"rendered":"\n

\u672c\u4eba\u65bc\u8a72blog\u7684\u5168\u90e8\u6587\u7ae0\u8f49\u79fb\u81f3[Algorithm] A Star Search Algorithm – KKWBlog (kkwtech.com)<\/a><\/a>\u8a72\u7db2\u57df\u4e0b\uff0c\u5176\u5f8c\u6b64\u8655\u4e0d\u9032\u884c\u66f4\u65b0\uff0c\u4e00\u5f8b\u65bc\u65b0\u7ad9\u9ede\u66f4\u65b0\u3002<\/p>\n\n\n\n

\"\"\/<\/a><\/figure>\n\n\n\n

\u5e73\u9762\u5716\u578b\u4e0a\uff0c\u6709\u591a\u500b\u7bc0\u9ede\u7684\u8def\u5f91\uff0c\u6c42\u51fa\u6700\u4f4e\u901a\u904e\u6210\u672c\u7684\u6f14\u7b97\u6cd5\u3002\u5e38\u7528\u65bc\u904a\u6232\u4e2d\u7684NPC\u7684\u79fb\u52d5\u8a08\u7b97\u3002\u7d50\u5408Best-first search & Dijikstra\u7684\u512a\u9ede\uff0c\u9032\u884c\u555f\u767c\u5f0f\u641c\u5c0b\u63d0\u9ad8\u6f14\u7b97\u6cd5\u6548\u7387\u7684\u540c\u6642\uff0c\u53ef\u4ee5\u4fdd\u8b49\u627e\u5230\u4e00\u689d\u6700\u4f73\u8def\u5f91\uff08\u57fa\u65bc\u8a55\u4f30\u51fd\u5f0f\uff09\u3002(\u5716\u6587\u64f7\u53d6\u81eaA*\u641c\u5c0b\u6f14\u7b97\u6cd5 – \u7dad\u57fa\u767e\u79d1\uff0c\u81ea\u7531\u7684\u767e\u79d1\u5168\u66f8 (wikipedia.org)<\/a>)<\/p>\n\n\n\n

\u6f14\u7b97\u6cd5:\n    \u524d\u7f6e:\n        \u5c07\u6703\u67093\u500b\u8b8a\u6578\u63a7\u5236\u8457\u7bc0\u9ede\u79fb\u52d5:FGH\n        F:G+H\n        G:\u67d0\u7bc0\u9ede\u81f3\u8d77\u9ede\u7684\u8ddd\u96e2\n        H:\u67d0\u7bc0\u9ede\u81f3\u7d42\u9ede\u7684\u8ddd\u96e2\n\n    \u7c21\u8ff0:\u4ee5G+H\u5f97\u51fa\u7684\u6700\u77ed\u8ddd\u96e2\u5373F\u4f86\u78ba\u8a8d\u8def\u5f91\u70ba\u6700\u4f4ecost\u76f4\u5230\u6700\u7d42\u8d70\u8a2a\u81f3\u7d42\u9ede\u70ba\u6b62\u3002\n\n\u8a73\u7d30\u6b65\u9a5f:\n    1.\u5efa\u7acb\u4e00\u7dad\u7684Open List(\u5b58\u653e\u5373\u5c07\u8d70\u8a2a\u7684\u7bc0\u9ede\uff0c\u53ca\u5c0d\u61c9\u7684F)\u3001\u4e8c\u7dad\u7684Closed List\u77e9\u9663(\u5b58\u653e\u5c1a\u672a\u8d70\u8a2a\u7684\u7bc0\u9ede)\u3001\u53ca\u4e00\u500b\u4e8c\u7dad\u77e9\u9663Detail\u5b58\u653eFGH\u53ca\u8def\u5f91(parent_i,parent_j)\uff0c\u4e26\u4e14\u5c07\u8d77\u9ede\u653e\u5165Open List\u53caDetail\u4e26\u4e14\u5c07parent_i,parent_j\u6307\u5411\u81ea\u5df1\u3002\n    2.While(Open List\u4e0d\u70ba\u7a7a)\n        2.1\u5f9eOpen List\u524d\u7aef\u53d6\u51fa\u4e00\u500b\u7bc0\u9ede\u8a2d\u70baq\n        2.2\u65bcClosed List\u88e1\u5c07q\u8a2d\u70ba\u5df2\u8d70\u8a2a\n        2.3\u5f9eq\u5ef6\u4f38\u627e\u51fa8\u500b\u65b9\u5411\u7684\u7bc0\u9ede(\u4e0a\u3001\u4e0b\u3001\u5de6\u3001\u53f3\u3001\u4e0a\u5de6\u3001\u4e0a\u53f3\u3001\u4e0b\u5de6\u3001\u4e0b\u53f3)\n        2.4 for(8\u500b\u65b9\u5411\u7bc0\u9ede)\n            2.4.1 If\u82e5\u8a72\u7bc0\u9ede\u70ba\u7d42\u9ede\u5247\u5c07q\u8a2d\u70ba\u8a72\u7bc0\u9ede\u4e4bparent\u4e26\u4e14\u96e2\u958bWhile\n            2.4.2 Else if\u82e5\u8a72\u7bc0\u9ede\u53ef\u8d70\u8a2a\uff08\u4e5f\u8a31\u6709\u963b\u9694\uff09\u4e26\u4e14Closed List\u70ba\u672a\u8d70\u8a2a\u72c0\u614b\uff0c\u8a72\u7bc0\u9edeGtmp = q.G + \u8a72\u7bc0\u9ede\u81f3q\u7684\u8ddd\u96e2 \uff0ctmp = \u7d42\u9ede\u81f3\u8a72\u7bc0\u9ede\u7684\u8ddd\u96e2\uff08\u8a3b\uff11\uff09\uff0cFtmp = Gtmp + Htmp\n                2.4.2.1 If\u82e5\u65bcDetail\u88e1\u8a72\u7bc0\u9ede\u7684F\u70ba\u521d\u59cb\u503c\u6216\u662fF > Ftmp(\u5373\u65b0\u8def\u5f91\u9577\u8f03\u77ed)\uff0c\u5247\u5c07Gtmp\u3001Htmp\u3001Ftmp\u3001parent_i\u3001parent_j\u586b\u5165\uff0c\u4e26\u4e14\u5c07\u8a72\u7bc0\u9ede\u653e\u5165Open List\u5c3e\u7aef\n        end for\n    end While\n\u8a3b1:\u5e38\u898b\u4f7f\u75283\u7a2e\u8ddd\u96e2\u8a08\u7b97\u7684\u65b9\u5f0f:1.Manhattan Distance,2.Diagonal Distance,3.Euclidean Distance\n\nSource code:Ghosts381937\/A-Star-Search-Algorithm (github.com)<\/a>\n(A Star Search Algorithm\u8cc7\u6599\u593e\u5167\u7684Source.cpp)<\/pre>\n\n\n\n
\n
\n
<\/div>\n<\/div>\n<\/div><\/div>\n\n\n\n
<\/p>\n","protected":false},"excerpt":{"rendered":"
\u672c\u4eba\u65bc\u8a72blog\u7684\u5168\u90e8\u6587\u7ae0\u8f49\u79fb\u81f3[Algorithm] A Star Search Algorithm &#8 […]<\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":[],"categories":[9],"tags":[6],"_links":{"self":[{"href":"https:\/\/aisumura.net\/blog\/wp-json\/wp\/v2\/posts\/180"}],"collection":[{"href":"https:\/\/aisumura.net\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/aisumura.net\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/aisumura.net\/blog\/wp-json\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/aisumura.net\/blog\/wp-json\/wp\/v2\/comments?post=180"}],"version-history":[{"count":25,"href":"https:\/\/aisumura.net\/blog\/wp-json\/wp\/v2\/posts\/180\/revisions"}],"predecessor-version":[{"id":347,"href":"https:\/\/aisumura.net\/blog\/wp-json\/wp\/v2\/posts\/180\/revisions\/347"}],"wp:attachment":[{"href":"https:\/\/aisumura.net\/blog\/wp-json\/wp\/v2\/media?parent=180"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/aisumura.net\/blog\/wp-json\/wp\/v2\/categories?post=180"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/aisumura.net\/blog\/wp-json\/wp\/v2\/tags?post=180"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}