Information Technology Reference
In-Depth Information
The Poly-tree Sequence approach has strong connections with the Markov Chain
Models. In the Markov Chain Model each state is an item and in the transition matrix,
each P(i,j) is the probability of moving from state i to state j in one step. This
approach, like the Markov Chain Models, also presents a global view since all the
items are taken into consideration. In our approach instead of the relative frequencies,
the absolute frequencies are used. Another difference between this approach, using
poly-trees and the Markov Chain is that it can handle cyclic graphs while the Markov
Chain deals only with acyclic ones. As has already been mentioned, we use heuristics
based on the Prim algorithm in order to reach a good scalability.
3.2 Searching Heuristics
In this paper, two heuristics are shown: The Forward Heuristic, that generates a tree
of items, and the Back-and-Forward Heuristic that is able to create poly-trees.
In our approach, we can find an identical tree by using the Forward Heuristic,
Algorithm 2, based on the Prim algorithm.
Algorithm 2. Forward Heuristic
Input: Network G;
Output: Tree S;
Initialize S;
For each vertex in G
For each edge in G
x = arg_max(weighted forward-vertex not visited in G and connected with S)
End-for;
Update solution S with x;
End-for;
For the Back-and-Forward mode, Algorithm 3, we developed the following
heuristic also based on the Prim algorithm.
Algorithm 3 . Back-and-Forward Heuristic
Input: Network G;
Output: Poly-tree S;
Initialize S;
For each vertex in G
For each edge in G
x = arg_max(weighted forward-vertex not visited in G and connected with S;
weighted back-vertex not visited in G and connected with S)
End-for;
Update solution S with x;
End-for;
Search WWH ::




Custom Search