Talk:A* search algorithm
moving into a barrier position
How does a path move into a barrier position?
I see that none of the programming examples show a path (so far) that "moves into" a barrier,
else we'd be seeing a total cost for a path that exceeds 100.
Does there need to be a cost when "moving into" a barrier, since no path has (apparently) done that?
How would one show a path that moves into a barrier? -- Gerard Schildberger (talk) 16:42, 29 January 2017 (UTC)
- While A* does not evaluate every possible move, it does internally check the cost of moving into a barrier square. For this reason, the cost of moving into a barrier square is required. However, there is always a lower cost alternative while still moving in the correct general direction (according to the heuristic), it should never actually be part of the maze solution.
- As you pointed out, the method for showing a path that moves into a barrier is left undefined. However, it should not be part of the a* solution so any method would be fine.--TimSC (talk) 16:58, 29 January 2017 (UTC)
- 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? -- Gerard Schildberger (talk) 18:48, 29 January 2017 (UTC)
- Also (above), you mentioned that: A* doesn't evaluate every possible move.
However, in the Wikipedia article (link), it states:
A* is an informed search algorithm, or a best-first search, meaning that it solves problems by searching among all possible paths to the solution (goal) 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). -- Gerard Schildberger (talk) 18:59, 29 January 2017 (UTC)
- Also (above), you mentioned that: A* doesn't evaluate every possible move.
grid orientation
It would seem that some programming examples are using a non-standard orientation of the
grid display, with the (0,0) origin point in the top-left of the display area, with positive
values for X (columns) going downward, instead of going upward.
For me, it doesn't make me no never-mind no-how, but it took a wee bit of fixin' for my
programming example (not yet posted) to match the existing displayed grids. -- Gerard Schildberger (talk) 16:42, 29 January 2017 (UTC)
A more interesting example
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?--Nigel Galloway (talk) 10:33, 30 January 2017 (UTC)
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?--Nigel Galloway (talk) 10:33, 30 January 2017 (UTC)
- The algorithm 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. -- Gerard Schildberger (talk) 21:41, 30 January 2017 (UTC)