efforts are also useful to know. We have been describing similar parameters for our
“desperation” approach. A* uses so-called cost plus heuristics function f that
includes for each node the past cost function g(x) and future cost function which is
acceptable estimate also called “heuristic estimate”.
g(x) is dealing with past cost of the walk for the node x from a destination, while
h(x) is dealing with an estimation—we stress here, an acceptable value—of future
costs to the destination. A* therefore estimates each and every node (x) of the graph
using a function:
f ðxÞ ¼ gðxÞ þ hðxÞ
ð 19:13Þ
At each iteration “g” part of this function is updated and all potential “clients”
are analyzed in terms of least cost. Further formal details of this algorithm can be
found in [12].
19.8 Result of Comparative Simulation
Further simulation of network using the same principle with generated 20 nodes
100 links graph demonstrate that probability of weighted links gives very good
advantage in comparison with A*. Initial setting of weights and heuristics is presented in Fig. 19.6 (Table 19.3).
The way A* works is demonstrated by red node marking at each iteration, until it
reaches a destination node. For this particular layout we observe 22 iterations at cost
of each defined by an amount of adjacent links to the current active node.
Let us consider now how Desperation Control Algorithm works on the same
layout. Immediately it becomes visible that amount of iterations shrinks and,
therefore an estimation of path finding that network is doing after every 200 ms
synchronization of links length (using network service protocol) becomes several
times shorter: QED (Table 19.4).
19.9 We Have More: A Vector Heuristic
Using a diameter of graph that we consider a matrix and adjusting weights relatively as di/L with multiplication along the paths and balancing as above attempting
to find almost equal contribution of each path to the journey to destination. At the
same time, we were using a heuristic that gave us estimation how long journey we
still have ahead. But this is not the whole story.
Network can be considered as a matrix and in this sense, we are having
two-dimensional space with heuristic at each path that give us an indication “how
19.7 Comparative Analysis of Proposed Algorithm and A*
283
“desperation” approach. A* uses so-called cost plus heuristics function f that
includes for each node the past cost function g(x) and future cost function which is
acceptable estimate also called “heuristic estimate”.
g(x) is dealing with past cost of the walk for the node x from a destination, while
h(x) is dealing with an estimation—we stress here, an acceptable value—of future
costs to the destination. A* therefore estimates each and every node (x) of the graph
using a function:
f ðxÞ ¼ gðxÞ þ hðxÞ
ð 19:13Þ
At each iteration “g” part of this function is updated and all potential “clients”
are analyzed in terms of least cost. Further formal details of this algorithm can be
found in [12].
19.8 Result of Comparative Simulation
Further simulation of network using the same principle with generated 20 nodes
100 links graph demonstrate that probability of weighted links gives very good
advantage in comparison with A*. Initial setting of weights and heuristics is presented in Fig. 19.6 (Table 19.3).
The way A* works is demonstrated by red node marking at each iteration, until it
reaches a destination node. For this particular layout we observe 22 iterations at cost
of each defined by an amount of adjacent links to the current active node.
Let us consider now how Desperation Control Algorithm works on the same
layout. Immediately it becomes visible that amount of iterations shrinks and,
therefore an estimation of path finding that network is doing after every 200 ms
synchronization of links length (using network service protocol) becomes several
times shorter: QED (Table 19.4).
19.9 We Have More: A Vector Heuristic
Using a diameter of graph that we consider a matrix and adjusting weights relatively as di/L with multiplication along the paths and balancing as above attempting
to find almost equal contribution of each path to the journey to destination. At the
same time, we were using a heuristic that gave us estimation how long journey we
still have ahead. But this is not the whole story.
Network can be considered as a matrix and in this sense, we are having
two-dimensional space with heuristic at each path that give us an indication “how
19.7 Comparative Analysis of Proposed Algorithm and A*
283