Anonymous user
Talk:A* search algorithm: Difference between revisions
→moving into a barrier position
No edit summary |
|||
Line 15:
:: So if a "move into" a barrier is never shown (because there is always a lower cost solution), why have a cost (for moving into a barrier) at all? -- [[User:Gerard Schildberger|Gerard Schildberger]] ([[User talk:Gerard Schildberger|talk]]) 18:48, 29 January 2017 (UTC)
::: In terms of understanding, there are two approaches where the "move into barrier" may lead:
::::# The barrier is a '''soft''' restriction. This means one '''may''' consider the barrier to find the path, and it will be considered when there are no paths without barrier move. In terms of coding, this places the barrier move in the queue with the least priority by assigning a huge cost. Then, at the first time a path successfully is found, the high cost will indicate a barrier was crossed.
::::# The barrier is a '''hard''' restriction. This means when there are no valid paths, the algorithm will return an '''empty path'''. In terms of coding, when the move puts a barrier, the move '''will not be added to the queue'''. Then, as the priority queue is popped, if there aren't any valid paths, the queue will empty and the A* shall raise the problem.
<br>
-----
Line 20 ⟶ 23:
:: Also (above), you mentioned that: ''A* doesn't evaluate every possible move''. <br><br>However, in the Wikipedia article (link), it states: <br><br>''A* is an informed search algorithm, or a best-first search, meaning that <u>it solves problems by searching among all possible paths to the solution (goal)</u> for the one that incurs the smallest cost (least distance travelled'' (sic), ''shortest time, etc.), and among these paths it first considers the ones that appear to lead most quickly to the solution.'' ... (underscoring and italics added by me). -- [[User:Gerard Schildberger|Gerard Schildberger]] ([[User talk:Gerard Schildberger|talk]]) 18:59, 29 January 2017 (UTC)
::: A* does not ''need'' to evaluate every possible move if two things happen:
::::# h(x) is always lower than the actual remaining cost.
::::# h(x_1) < h(x_2) + d(x_1, x_2).
:::
== grid orientation ==
| |||