在课堂上，我们得到了一个简单的决策树，用于对 3 个元素（a、b、c）进行排序。
（来源：brpreiss.com）
当我看到这一点时，我觉得这是有道理的。我能够跟上它。
然而，我现在必须为 4 个元素（a、b、c、d）制作一个决策树，并且叶子的数量刚刚增加到 24 个。
我正在努力以有条理的方式接近决策树，以帮助我跟踪以及我应该在每个分支进行比较的元素。
构建更大的决策树的系统方法是什么？如果我知道如何的话，我什至愿意编写一个程序来吐出可能的叶子结构。
In class we were given a simple decision tree for sorting 3 elements (a,b,c).
(source: brpreiss.com)
While looking at this, it makes sense to me. I was able to follow it.
However, I now have to make a decision tree for 4 elements (a,b,c,d) and the number of leafs just shot up to 24.
I'm struggling approaching the decision tree in a methodical way that helps me keep track and of the elements I'm suppose to be comparing at each branch.
What is a methodical way of approaching the construction of a larger decision tree? I'd even be willing to write a program to spit out the possible leafs-structure if I knew how to.
发布评论
评论（3）
您可能想研究排序网络。我认为应该可以将给定数量的输入的最佳排序网络转换为决策树。
或者，您可以采用给定的排序算法并逐步执行它，在每次比较时创建一个新分支。
最后，您可以反向执行此操作 - 例如，通过采用合并排序类型的方法：将所有 24 种可能的排序顺序放在树的底部。选择一个比较，并根据结果将叶子分为两组。对每个分支递归重复，直到每个分支只有一片叶子。
You might want to look into Sorting Networks. It should be possible to convert the optimal sorting network for a given number of inputs into a decision tree, I think.
Alternately, you could take a given sorting algorithm and step through it, creating a new branch at each comparison.
Finally, you could do this in reverse - for example, by taking a merge-sort type approach: Lay out all 24 possible sort orders at the bottom of the tree. Pick a comparison, and partition the leaves into two sets based on the outcome. Repeat recursively for each branch until you only have one leaf per branch.
Charles Forgy 描述了这种算法：请参阅 Rete 算法。 （抱歉，WP 中的文章当然不是一个快速答案，但它可能是一个好的开始）
The kind of algorithm has been described by Charles Forgy: see the Rete algorithm. (I'm sorry, the article in WP is certainly not a quick answer but it might be a good start)
在本例中，一种简单的方法是扩展现有的树。深度 3 树最多可以排序
2^3=8个不同的结果，这足以对 3 个元素进行排序，因为3! = 6和6 <= 8。要对 4 个元素进行排序，您至少需要深度 5：4！ <= 2^5。考虑到a、b和cdcode> 已按您现有的网络排序。假设
x、y和z已排序，因此x你可以使用这个网络在正确的位置添加新元素 d：因此，您基本上可以将现有的树复制 4 次，然后用上面的子树替换每个当前叶子，在每种情况下替换
x、y和z的顺序为a、b和c在当前叶子中。请注意，虽然这适用于您的特定情况，并生成最小树，但附加子树以插入“下一个元素”将不会为其他情况生成最小高度排序树。例如，要对
a,b,c,d,e进行排序，最小高度将为 7，如5！ = 120 和7^2 = 128。然而，将e放入已排序的 4 个元素列表中的子树本身至少需要深度 3（因为有 5 个可能的插入位置） - 因此我们可以轻松构建一个5+3 = 8深度树，但需要另一种方法来构建有效的深度 7 树。对于一般性讨论，Nick's answer 中有关排序网络的链接非常相关：您可以从网络构建排序树通过从左到右读取网络，为每个连接创建一个节点，然后将网络的两个变体视为子节点：其中一个已进行交换（例如，
a是 false，所以现在 a和b被交换），以及另一个不需要的地方（因为a）。排序决策树的深度是其排序网络的深度，根据该页面，虽然有一种生成对数深度树/网络（AKS）的算法，但它绝不是简单的。 A simple way, in this case, is to extend the existing tree. A depth-3 tree can sort for up to
2^3=8different outcomes, which is enough to sort 3 elements, since3! = 6and6 <= 8. To sort 4 elements you need at least depth 5:4! <= 2^5. We can structure the two new, lowest levels to decide where to insert thed, given thata,bandcare already sorted by your existing net.Assuming that
x,yandzare sorted, so thatx<y<zyou can use this net to add a new elementdat its correct position:So you can essentially take your existing tree, replicate it 4 times, and replace each current leaf with the above sub-tree, in each case replacing
x,yandzwith the order ofa,bandcin the current leaf.Note that, while this works for your particular case, and yields a minimal tree, appending subtrees to insert "the next element" will not yield minimal-height sorting trees for other cases. For example, to sort
a,b,c,d,e, the minimal height would be 7, as5! = 120and7^2 = 128. However, a subtree to place aneinto an already-sorted list of 4 elements would need, by itself, at least depth 3 (as there are 5 possible insertion positions) - so we can easily build a5+3 = 8-depth tree, but would need another approach to build a valid depth-7 tree.For a general discussion, the link on sorting networks in Nick's answer is very relevant: you can build a sorting tree from a network by reading the network from left to right, creating a node for each connection, and at that point, considering two variants of the network as children: one where the swap has been made (say,
a<bis false, so nowaandbget swapped), and another where it is not needed (becausea<b). The depth of the sorting decision tree is that of its sorting network, and according to that page, while there is an algorithm to generate logarithmic-depth trees/networks (AKS), it is by no means simple.