Strategies to Fast Evaluation of Tree Networks - Basbous, Raed; Nagy, Benedek (Budapest Tech, 2015)
Special tree graphs could model Cognitive Infocommunication Networks. The various modalities of the network are represented by various types of vertices, e.g., additions, multiplications. Tree graphs/networks are widely used in several other theoretical and practical fields. Expression trees are well-known tools to visualize the syntactic structure of the expressions. They are helpful also in evaluations, e.g., decision trees are widely used. Games and game theory form an important field in Artificial Intelligence and it has several connections to Optimization, Business and Economy. Game trees are used to represent games. In this paper, certain types of tree networks are considered using various operations at their inner vertices, e.g., multiplication, (constrained) addition and the usual minimum and maximum (related to conjunction and disjunction of Boolean algebra). Evaluation techniques are presented, as well as, various pruning algorithms (related to short circuit evaluation in the Boolean case) that can quicken the evaluation in most cases. Based on the commutativity of the used operations, the evaluations can be more effective (faster) by reordering the branches of the tree. The presented techniques are useful to optimize (minimize) the size of the tree networks in various cases without affecting the final result/decision of the network.
Keywords: expression trees; game trees; short circuit evaluation; pruning of trees; decision making; reordered trees