returns the element with highest probability and removes it from the queue. This
node is then updated with the function “increase” by the adjacent nodes.
Initially, the first tracing node s is the active node. Inside the tracing loop, for
every node, the probabilities for all possible paths are calculated. The highest
probability for the traces defines the start for the next step of the algorithm; the node
along the highest probable trace is assigned as active and deleted from the queue.
Therefore, the probabilities of all the adjacent nodes (minor to major (i.e., high
risk)) with active node are calculated.
To avoid looping during tracing analysis, the adjacent nodes that have already
been visited are excluded from further tracing (line 17) during each particular
analysis of the matrix. When a loop is detected, a production
Q
(p i,j ) is calculated
excluding the last probability. All the remaining nodes will be traced; probabilities
along their paths (from starting node) are updated (line 20, 21).
As already mentioned, tracing terminates when the probabilities
Q
(p i,j ) of
reaching the remaining nodes are less than ɛ. To summarize, starting from the
“suspected” element all possible paths and their probabilities are traced, their
cumulative probabilities are calculated, and their sequences are ranked according to
their relative probabilities.
Relating to standard algorithm and data structure theory, this algorithm is
basically a modified version of a breadth-first search.
Fig. 5.3 Forward tracing algorithm
54
5 GAFT Generalization: A Principle and Model of Active System…
node is then updated with the function “increase” by the adjacent nodes.
Initially, the first tracing node s is the active node. Inside the tracing loop, for
every node, the probabilities for all possible paths are calculated. The highest
probability for the traces defines the start for the next step of the algorithm; the node
along the highest probable trace is assigned as active and deleted from the queue.
Therefore, the probabilities of all the adjacent nodes (minor to major (i.e., high
risk)) with active node are calculated.
To avoid looping during tracing analysis, the adjacent nodes that have already
been visited are excluded from further tracing (line 17) during each particular
analysis of the matrix. When a loop is detected, a production
Q
(p i,j ) is calculated
excluding the last probability. All the remaining nodes will be traced; probabilities
along their paths (from starting node) are updated (line 20, 21).
As already mentioned, tracing terminates when the probabilities
Q
(p i,j ) of
reaching the remaining nodes are less than ɛ. To summarize, starting from the
“suspected” element all possible paths and their probabilities are traced, their
cumulative probabilities are calculated, and their sequences are ranked according to
their relative probabilities.
Relating to standard algorithm and data structure theory, this algorithm is
basically a modified version of a breadth-first search.
Fig. 5.3 Forward tracing algorithm
54
5 GAFT Generalization: A Principle and Model of Active System…