算
算法不懂
Unregistered / Unconfirmed
GUEST, unregistred user!
The maze we will look at is small, but has enough twists and turns to make it a little challenge for the A*.
The black lines are impassable, the red square denotes the start (0,0),and the green denotes the end (2,2).
Note that in the bottom-right corner there are two grey areas, one darker than the other. These are different
cost areas, the darker grey being a higher cost. This will help demonstration back-propagation of lower g-values
a bit later on.
Now, during the first couple of iterations we find the only the square that is open is the one directly beneath
us. We therefore have no choice but to travel there. In fact, this happens rightdo
wn the line - despite the
'fitness' of the node increasing and increasing (as distance increases).
Nevertheless, let us look at the calculations are are taken. For the first loop, only (1,0) is open, so we create
a node there - and the values are initialized:
G: 1 + board value (0) = 1
H: (2-0)*(2-0) + (2-0)*(2-0) = 8
F: G + H = 9
This is inserted on to the Open list (since we haven't explored any of its child nodes yet), and the process is
continued. Thing is, none of the other nodes are valid, so when we pick the best node off the Open list it is
this one. The process then
continuesdo
wn the line. Now, imagine that the algorithm continuesdo
wn the initial
line, from (0,0) to (0,19). Now, backtrack a little. When the algorithm assesses (0,18) which nodedo
you think
it would pick to move to next? (1,19) is the best since it is closer to the goal point than (0,19). It also
involves less tiles in the long run. So, we are now assessing (1,19). During this time, we assess (0,19) again,
since it is still an adjacent square. (0,19) is still on the Open list from when (0,18) assessed it. So, when
the algorithm comes to check for (0,19) it finds the node on the Open list, and then
adds it to its list of
children. It then
checks to see whether it would benefit by moving through (0,19) - itdo
esn't, so things are
left alone.
After (1,19) has been fully assessed, (2,18) is chosen as the next best node to move to. This generates another
scenario the algorithm needs to deals with. (2,18) assesses the nodes around it and finds that (1,19) is not on
the Open list, but is on the closed list (all (1,19)'s child nodes have been put on the open list). It therefore
adds it to its list of children and continues on its merry way since it would not benefit by going back through
(1,19).
We will allow the algorithm to run for a little while. Another scenario arises soon though, at (3,5). When the
algorithm assesses (3,5) it finds (4,4) on the closed stack. What it also finds is that its g-value is higher
than its predicted g-value would be if the path went via (3,5). In short, this means that either a high-cost
path had been explored, or simply more nodes were transversed to get to (4,4) than was necessary. We therefore
update the node accordingly, and then
propagate this changedo
wn its children. Luckily, in this case, none of
the children required propagation.
A case arises later on when a huge propagation is required - at (21,15) it is found that by going through (22,
16) a saving of 16 can be made (G(21,15) = 94, G(22,16) = 78). The intuitive reader can propagate the changes
backward if they wish!
Finally, the algorithm zooms around the squiggly area, up and over and reaches its goal. Notice that the
algorithm would chose to take the longer, but less costly route by going through the light grey area.
The black lines are impassable, the red square denotes the start (0,0),and the green denotes the end (2,2).
Note that in the bottom-right corner there are two grey areas, one darker than the other. These are different
cost areas, the darker grey being a higher cost. This will help demonstration back-propagation of lower g-values
a bit later on.
Now, during the first couple of iterations we find the only the square that is open is the one directly beneath
us. We therefore have no choice but to travel there. In fact, this happens rightdo
wn the line - despite the
'fitness' of the node increasing and increasing (as distance increases).
Nevertheless, let us look at the calculations are are taken. For the first loop, only (1,0) is open, so we create
a node there - and the values are initialized:
G: 1 + board value (0) = 1
H: (2-0)*(2-0) + (2-0)*(2-0) = 8
F: G + H = 9
This is inserted on to the Open list (since we haven't explored any of its child nodes yet), and the process is
continued. Thing is, none of the other nodes are valid, so when we pick the best node off the Open list it is
this one. The process then
continuesdo
wn the line. Now, imagine that the algorithm continuesdo
wn the initial
line, from (0,0) to (0,19). Now, backtrack a little. When the algorithm assesses (0,18) which nodedo
you think
it would pick to move to next? (1,19) is the best since it is closer to the goal point than (0,19). It also
involves less tiles in the long run. So, we are now assessing (1,19). During this time, we assess (0,19) again,
since it is still an adjacent square. (0,19) is still on the Open list from when (0,18) assessed it. So, when
the algorithm comes to check for (0,19) it finds the node on the Open list, and then
adds it to its list of
children. It then
checks to see whether it would benefit by moving through (0,19) - itdo
esn't, so things are
left alone.
After (1,19) has been fully assessed, (2,18) is chosen as the next best node to move to. This generates another
scenario the algorithm needs to deals with. (2,18) assesses the nodes around it and finds that (1,19) is not on
the Open list, but is on the closed list (all (1,19)'s child nodes have been put on the open list). It therefore
adds it to its list of children and continues on its merry way since it would not benefit by going back through
(1,19).
We will allow the algorithm to run for a little while. Another scenario arises soon though, at (3,5). When the
algorithm assesses (3,5) it finds (4,4) on the closed stack. What it also finds is that its g-value is higher
than its predicted g-value would be if the path went via (3,5). In short, this means that either a high-cost
path had been explored, or simply more nodes were transversed to get to (4,4) than was necessary. We therefore
update the node accordingly, and then
propagate this changedo
wn its children. Luckily, in this case, none of
the children required propagation.
A case arises later on when a huge propagation is required - at (21,15) it is found that by going through (22,
16) a saving of 16 can be made (G(21,15) = 94, G(22,16) = 78). The intuitive reader can propagate the changes
backward if they wish!
Finally, the algorithm zooms around the squiggly area, up and over and reaches its goal. Notice that the
algorithm would chose to take the longer, but less costly route by going through the light grey area.
][
][
= g