Totally optimal decision trees for Boolean functions
| Autor: | Igor Chikalov, Shahid Hussain, Mikhail Moshkov |
|---|---|
| Rok vydání: | 2016 |
| Předmět: |
Discrete mathematics
Mathematical optimization Applied Mathematics Decision tree Weight-balanced tree 02 engineering and technology Tree (graph theory) Dynamic programming Set (abstract data type) 020204 information systems 0202 electrical engineering electronic engineering information engineering Discrete Mathematics and Combinatorics 020201 artificial intelligence & image processing Boolean function Time complexity Optimal decision Mathematics |
| Zdroj: | Discrete Applied Mathematics. 215:1-13 |
| ISSN: | 0166-218X |
| DOI: | 10.1016/j.dam.2016.07.009 |
| Popis: | We study decision trees which are totally optimal relative to different sets of complexity parameters for Boolean functions. A totally optimal tree is an optimal tree relative to each parameter from the set simultaneously. We consider the parameters characterizing both time (in the worst- and average-case) and space complexity of decision trees, i.e., depth, total path length (average depth), and number of nodes. We have created tools based on extensions of dynamic programming to study totally optimal trees. These tools are applicable to both exact and approximate decision trees, and allow us to make multi-stage optimization of decision trees relative to different parameters and to count the number of optimal trees. Based on the experimental results we have formulated the following hypotheses (and subsequently proved): for almost all Boolean functions there exist totally optimal decision trees (i) relative to the depth and number of nodes, and (ii) relative to the depth and average depth. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect