{"id":528,"date":"2011-03-09T23:53:17","date_gmt":"2011-03-09T22:53:17","guid":{"rendered":"http:\/\/cerezo.name\/blog\/?p=528"},"modified":"2024-10-14T14:24:55","modified_gmt":"2024-10-14T12:24:55","slug":"broken-folklore-heuristics","status":"publish","type":"post","link":"http:\/\/cerezo.name\/blog\/2011\/03\/09\/broken-folklore-heuristics\/","title":{"rendered":"(Broken) Folklore Heuristics"},"content":{"rendered":"<p style=\"text-align: justify;\"><a href=\"http:\/\/en.wikipedia.org\/wiki\/A*_search_algorithm\" target=\"_blank\" rel=\"http:\/\/en.wikipedia.org\/wiki\/A*_search_algorithm noopener\"><img loading=\"lazy\" class=\"aligncenter size-full wp-image-529\" title=\"Example of A* algorithm where nodes are cities connected with roads and h(x) is the straight-line distance to target point\" src=\"http:\/\/cerezo.name\/blog\/wp-content\/uploads\/2011\/03\/AstarExample.gif\" alt=\"Example of A* algorithm where nodes are cities connected with roads and h(x) is the straight-line distance to target point\" width=\"400\" height=\"283\" srcset=\"http:\/\/cerezo.name\/blog\/wp-content\/uploads\/2011\/03\/AstarExample.gif 400w, http:\/\/cerezo.name\/blog\/wp-content\/uploads\/2011\/03\/AstarExample-300x212.gif 300w\" sizes=\"(max-width: 400px) 100vw, 400px\"><\/a>It\u2019s funny how two of the most studied algorithms of a discipline, that are considered polynomially optimal for decades under a set of well-accepted assumptions, turn out not to be so great. That\u2019s the case of the famous A* and <span class=\"caps\">IDA<\/span>* algorithms, cornerstones in <span class=\"caps\">AI<\/span> and <strong>currently implemented in thousands of computer games<\/strong> because there were thought to be polynomial in the search space since 1968 under a set of broadly defined heuristics, even though nobody has found practical instances of them after hundreds of proposal and attempts.&nbsp;Their optimality is finally debunked in \u201c<a href=\"http:\/\/citeseerx.ist.psu.edu\/viewdoc\/summary?doi=10.1.1.144.1239\" target=\"_blank\" rel=\"noopener\">How Good is Almost Perfect<\/a>\u201d: general search algorithms such as A* must necessarily explore an exponential number of search nodes even under the most optimistic assumption of estimators with heuristic error bounded by a small additive constant. What is worse, other similar search techniques cannot perform better than&nbsp;A*.<\/p>\n<p style=\"text-align: justify;\">These are the kind of results that reminds you to always revisit assumptions, to search more closely where others may have obviated, no matter how well-accepted and reputed are the sources, in particular with folklore wisdom, beliefs and other uncanny heuristics.<\/p>\n<p style=\"text-align: justify;\">\n<\/p><div class=\"gde-error\"><span class=\"caps\">GDE<\/span> Error: Error retrieving file \u2014 if necessary turn off error checking (403:Forbidden)<\/div>\n\n","protected":false},"excerpt":{"rendered":"<p>It\u2019s funny how two of the most studied algorithms of a discipline, that are considered polynomially optimal for decades under a set of well-accepted assumptions, turn out not to be so great. That\u2019s the case of the famous A* and <span class=\"caps\">IDA<\/span>* algorithms, cornerstones in <span class=\"caps\">AI<\/span> and currently implemented in thousands of computer games because there&nbsp;[\u2026]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"wp_typography_post_enhancements_disabled":false,"ngg_post_thumbnail":0},"categories":[9],"tags":[],"_links":{"self":[{"href":"http:\/\/cerezo.name\/blog\/wp-json\/wp\/v2\/posts\/528"}],"collection":[{"href":"http:\/\/cerezo.name\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/cerezo.name\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/cerezo.name\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/cerezo.name\/blog\/wp-json\/wp\/v2\/comments?post=528"}],"version-history":[{"count":12,"href":"http:\/\/cerezo.name\/blog\/wp-json\/wp\/v2\/posts\/528\/revisions"}],"predecessor-version":[{"id":1662,"href":"http:\/\/cerezo.name\/blog\/wp-json\/wp\/v2\/posts\/528\/revisions\/1662"}],"wp:attachment":[{"href":"http:\/\/cerezo.name\/blog\/wp-json\/wp\/v2\/media?parent=528"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/cerezo.name\/blog\/wp-json\/wp\/v2\/categories?post=528"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/cerezo.name\/blog\/wp-json\/wp\/v2\/tags?post=528"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}