Decision trees with minimum average depth for sorting eight elements
| Autor: | Hassan AbouEisha, Igor Chikalov, Mikhail Moshkov |
|---|---|
| Rok vydání: | 2016 |
| Předmět: |
Discrete mathematics
021103 operations research Applied Mathematics 0211 other engineering and technologies Decision tree Sorting 0102 computer and information sciences 02 engineering and technology 01 natural sciences Dynamic programming 010201 computation theory & mathematics Discrete Mathematics and Combinatorics Pairwise comparison Algorithm Sequential optimization Mathematics |
| Zdroj: | Discrete Applied Mathematics. 204:203-207 |
| ISSN: | 0166-218X |
| Popis: | We prove that the minimum average depth of a decision tree for sorting 8 pairwise different elements is equal to 620160 / 8 ! . We show also that each decision tree for sorting 8 elements, which has minimum average depth (the number of such trees is approximately equal to 8.548 × 10 326365 ), has also minimum depth. Both problems were considered by Knuth (1998). To obtain these results, we use tools based on extensions of dynamic programming which allow us to make sequential optimization of decision trees relative to depth and average depth, and to count the number of decision trees with minimum average depth. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect