Page 51 - Intelligent Communication Systems

CHAPTER 4/ADVANCES IN COMMUNICATION NETWORKS 3S
Consider the shortest path from S to G. A heuristic search method is applied
to solve the problem. First of all, an anticipated value is assigned to each node
except S. The value AV(N,—>G) is an anticipated value from a node N i to goal
G, where AV is equal to or smaller than the exact minimum value V(N i,-G). In
Figure 4.20, an anticipated value is assigned to each node as follows: AV(A G)
is 7. AV(B G) is 4. AV(C G) is 2. The processing is performed as follows: The
nodes linked by directed branches from S are A and B. The anticipated value of
{S A G} is 12, where a value of S to A is 5 and an anticipated value of A to
G is 7. Similarly, the anticipated value of {S B G} is 8, where the value of S to
B is 4 and the value of B to G is 4. Then the shortest path {S B G} is chosen.
Then the nodes linked by directed branches from B are C and G. The value of
{S B C G} is 8, where the value of S to B is 4, the value of B to C is 2, and
the anticipated value of C to G is 2. Similarly, the value of {S B G} is 10, where
the value of S to B is 4 and value of B to G is 6. Then the path {S B C G} is
chosen. Finally the value of {S B C G} is calculated and the value is obtained.
The shortest path from S to G is {S B C G} and the value is 9.