Talk:A* search algorithm: Difference between revisions
m
→grid orientation
No edit summary |
|||
| (6 intermediate revisions by 5 users not shown) | |||
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 ==
Line 28 ⟶ 35:
For me, it doesn't make me no never-mind no-how, but it took a wee bit of fixin' for my
<br>programming example (not yet posted) to match the existing displayed grids. -- [[User:Gerard Schildberger|Gerard Schildberger]] ([[User talk:Gerard Schildberger|talk]]) 16:42, 29 January 2017 (UTC)
: In my experience, matrix representation typically has 0,0 in the upper left hand corner. Opengl typically puts 0,0 in the lower left corner or the center, depending on context. Presumably we also have other standards which might be relevant here. But unless we state which standard we're working with... "the nice thing about standards is that there's so many to choose from". --[[User:Rdm|Rdm]] ([[User talk:Rdm|talk]]) 16:09, 17 January 2022 (UTC)
==A more interesting example==
<br>
A barrier is created by setting a square's value effectively to infinity. How this is achieved by the algorithm should be implementation dependant. Some languages support the concept intrinsically, certainly 100 should not be a magic number. Would it not be more interesting if the squares had values other than 1 or infinity. Say randomly assigned?--[[User:Nigel Galloway|Nigel Galloway]] ([[User talk:Nigel Galloway|talk]]) 10:33, 30 January 2017 (UTC)
</br>▼
==Related Tasks==
How is this algorithm related to solving a Hidato Puzzle? or the others for that matter. Does anyone intend to produce a solution using this algorithm?--[[User:Nigel Galloway|Nigel Galloway]] ([[User talk:Nigel Galloway|talk]]) 10:33, 30 January 2017 (UTC)
: The <u>algorithm</u> used for the '''A*''' search isn't related to a Hidato puzzle, but parts of the (computer program) solution may be used, especially the presentation of the solution/answer(s), but that's not the reason I added those other tasks; they appear to me as related tasks in that quite a bit (at least my solution, as yet not included) had a lot of code in common. --- Not that everyone else may have had the same observation. I never intended to imply that the same algorithm (or a even a modified one) could/would/should be used (or even considered) for those other related tasks. In no way does a related task imply the same algorithm could or should be used or applied to another task. To answer your second question, no, I am not going to use this algorithm to solve ''any'' other Rosetta Code problem. That's not what a ''related task'' means to me. I also believe that ''related'' doesn't necessarily mean ''similar'' in this context. -- [[User:Gerard Schildberger|Gerard Schildberger]] ([[User talk:Gerard Schildberger|talk]]) 21:41, 30 January 2017 (UTC)
:Wherein lies the problem. Do you think that the Rexx (and some other) solutions implement the '''A*''' search algorithm? From Wikipedia:<br>
::Typical implementations of A* use a priority queue to perform the repeated selection of minimum (estimated) cost nodes to expand. This priority queue is known as the open set or fringe. At each step of the algorithm, the node with the lowest f(x) value is removed from the queue, the f and g values of its neighbors are updated accordingly, and these neighbors are added to the queue. The algorithm continues until a goal node has a lower f value than any node in the queue (or until the queue is empty).<br>
:Specifically, there is no back-tracking in '''A*'''. Of course the task description does not clearly specify what is meant by '''A*''' but if anything goes then I think '''A*''' should be removed from the task's title allowing any way to find this path. Alternatively the task description should be clear and some of the solutions marked incorrect.--[[User:Nigel Galloway|Nigel Galloway]] ([[User talk:Nigel Galloway|talk]]) 14:39, 21 November 2017 (UTC)
== Extra credit ==
While it is perfectly possible to solve an 8-puzzle with A*, and it is commonly used/taught, the fact that it is completely impractical for a 15-puzzle gives me serious doubts. Perhaps something more like the javascript demo, showing nodes actually examined would be better.
== Path cost ambiguity ==
After implementing this task and comparing my result to other results, I have noticed that some implementations give a path cost of 12 (which would suggest moving into the start square) while other implementations give a path cost of 11 (which would suggest not moving into that start square).
This seems like a minor issue, but we should probably think a little about what we want here. --[[User:Rdm|Rdm]] ([[User talk:Rdm|talk]]) 16:06, 17 January 2022 (UTC)
| |||