{"id":216,"date":"2021-07-22T10:38:28","date_gmt":"2021-07-22T02:38:28","guid":{"rendered":"https:\/\/aisumura.net\/blog\/?p=216"},"modified":"2021-09-20T23:26:11","modified_gmt":"2021-09-20T15:26:11","slug":"%e6%bc%94%e7%ae%97%e6%b3%952best-first-search","status":"publish","type":"post","link":"https:\/\/aisumura.net\/blog\/2021\/07\/22\/%e6%bc%94%e7%ae%97%e6%b3%952best-first-search\/","title":{"rendered":"\u6f14\u7b97\u6cd5(2)Best-First Search"},"content":{"rendered":"\n<p style=\"font-size:22px\">\u672c\u4eba\u65bc\u8a72blog\u7684\u5168\u90e8\u6587\u7ae0\u8f49\u79fb\u81f3<a href=\"https:\/\/blog.kkwtech.com\/uva\/11536-smallest-sub-array\"><a href=\"https:\/\/blog.kkwtech.com\/algorithm\/best-first-search\">[Algorithm] Best-First Search &#8211; 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<figure class=\"wp-block-image size-large is-style-default\"><img src=\"https:\/\/raw.githubusercontent.com\/Ghosts381937\/Best-First-Search\/master\/unknown%20(1).png\" alt=\"best-first search example\"\/><\/figure>\n\n\n\n<pre class=\"wp-block-preformatted\">\u4e0d\u540c\u65bcBFS\u3001DFS\u4ee5\u5ee3\u5ea6\u6216\u6df1\u5ea6\u9032\u884c\u641c\u5c0b\uff0cbest-first search\u5247\u662f\u4ee5\u8def\u5f91\u7684\u6b0a\u91cd\u512a\u5148\u505a\u641c\u5c0b\n\npseudocode:\n    <code>\u5efa\u7acb\u4e00\u500bPirority queue = pq\n  \u5c07\u8d77\u9ede\u653e\u5165pq\n    while(pq\u4e0d\u70ba\u7a7a)\n      \u5f9epq\u53d6\u51fa\u4e00\u500b\u7bc0\u9edenode\u4e26\u5f9epq\u522a\u9664\u8a72\u7bc0\u9ede\n      if(node\u662f\u7d42\u9ede)\n        \u7d50\u675f\u8ff4\u5708\n      else\n        for \u6bcf\u500bnode\u7684\u76f8\u9130\u7bc0\u9ede\n          if(\u76f8\u9130\u7bc0\u9ede\u672a\u8d70\u8a2a)\n            \u5c07\u76f8\u9130\u7bc0\u9ede\u8b93\u5165pq\n            \u76f8\u9130\u7bc0\u9ede\u8a2d\u70ba\u5df2\u8d70\u8a2a<\/code>\n\u7bc4\u4f8b:\n\u4ee5\u6587\u9996\u7684\u5716\u505a\u8209\u4f8b\nstart = A,goal = H,pq{A}\n1.node = A pq{}  =&gt;  pq{BCD}\n2.node = B pq{CD}  =&gt;  pq{CED}\n3.node = C pq{ED}  =&gt;  pq{EDF}\n4.node = E pq{DF}  =&gt;  pq{DFG}\n5.node = D pq{FG}  =&gt;  pq{FG}\n6.node = F pq{G}  =&gt; pq{HG}\n7.node = H pq{G}  =&gt; goal was found\n\nSource code:<a href=\"https:\/\/github.com\/Ghosts381937\/Best-First-Search\">Ghosts381937\/Best-First-Search (github.com)<\/a><\/pre>\n\n\n\n<p><\/p>\n","protected":false},"excerpt":{"rendered":"<p>\u672c\u4eba\u65bc\u8a72blog\u7684\u5168\u90e8\u6587\u7ae0\u8f49\u79fb\u81f3[Algorithm] Best-First Search &#8211; K [&hellip;]<\/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\/216"}],"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=216"}],"version-history":[{"count":7,"href":"https:\/\/aisumura.net\/blog\/wp-json\/wp\/v2\/posts\/216\/revisions"}],"predecessor-version":[{"id":346,"href":"https:\/\/aisumura.net\/blog\/wp-json\/wp\/v2\/posts\/216\/revisions\/346"}],"wp:attachment":[{"href":"https:\/\/aisumura.net\/blog\/wp-json\/wp\/v2\/media?parent=216"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/aisumura.net\/blog\/wp-json\/wp\/v2\/categories?post=216"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/aisumura.net\/blog\/wp-json\/wp\/v2\/tags?post=216"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}