[PDF][PDF] Constructing optimal binary decision trees is NP-complete
H Laurent, RL Rivest - Information processing letters, 1976 - people.csail.mit.edu
We demonstrate that constructing optimal binary decision trees is an NP-complete problem,
where an optimal tree is one which minimizes the expected num-ber of tests required to
identify the unknown object. Precise definitions of NP-complete problems are given in
refs.[1, 2, 4]. While the proof to be given is relatively simple, the importance of this result can
be measured in terms of the large amount of effort that has been put into find-ing efficient
algorithms for constructing optimal bi-nary decision trees (see [3, 5, 6] and their references) …
where an optimal tree is one which minimizes the expected num-ber of tests required to
identify the unknown object. Precise definitions of NP-complete problems are given in
refs.[1, 2, 4]. While the proof to be given is relatively simple, the importance of this result can
be measured in terms of the large amount of effort that has been put into find-ing efficient
algorithms for constructing optimal bi-nary decision trees (see [3, 5, 6] and their references) …
以上显示的是最相近的搜索结果。 查看全部搜索结果