4

在课堂上，我们得到了一个简单的决策树，用于对 3 个元素（a、b、c）进行排序。

替代文字
（来源：brpreiss.com）

看着这个，对我来说很有意义。我能够跟随它。

但是，我现在必须为 4 个元素（a、b、c、d）制作一个决策树，并且叶子的数量刚刚上升到 24 个。

我正在努力以一种有条不紊的方式接近决策树，这有助于我跟踪我想在每个分支上比较的元素。

什么是构建更大决策树的有条不紊的方法？如果我知道怎么做，我什至愿意编写一个程序来吐出可能的叶子结构。

4

3 回答 3

2

您可能想查看 S orting Networks。我认为应该可以将给定数量的输入的最佳排序网络转换为决策树。

或者，您可以采用给定的排序算法并逐步执行它，在每次比较时创建一个新分支。

最后，您可以反过来执行此操作 - 例如，采用合并排序类型的方法：在树的底部布置所有 24 个可能的排序顺序。选择一个比较，并根据结果将叶子分成两组。对每个分支递归重复，直到每个分支只有一个叶子。

于 2009-09-22T11:52:33.283 回答
0

Charles Forgy 已经描述了这种算法：请参阅Rete 算法。（对不起，WP中的文章当然不是一个快速的答案，但它可能是一个好的开始）

于 2009-09-22T10:20:56.053 回答
0

在这种情况下，一种简单的方法是扩展现有树。深度 3 树最多可以对2^3=8不同的结果进行排序，这足以对 3 个元素进行排序，因为3! = 6和6 <= 8。要对 4 个元素进行排序，您至少需要深度 5: 4! <= 2^5。我们可以构建两个新的最低级别来决定在哪里插入d，假设a，b并且c已经按您现有的网络排序。

假设x,y和z已排序，以便您可以使用此网络在其正确位置x<y<z添加新元素：d

// note: read from right to left
d<x<y<z -[yes]- (d<x)? -[yes]-- (d<y) -
x<d<y<z -[no]-/               /
x<y<d<z -[yes]- (d<z)? -[no]-/
x<y<z<d -[no]-/

因此，您基本上可以使用现有的树，将其复制 4 次，然后将每个当前叶子替换为上述子树，在每种情况下替换x,y和,的z顺序在当前叶子中。abc

请注意，虽然这适用于您的特定情况并产生最小树，但附加子树以插入“下一个元素”不会为其他情况产生最小高度排序树。例如，对于 sort a,b,c,d,e，最小高度为 7，如5! = 120和7^2 = 128。但是，将 ae放入已排序的 4 个元素的列表中的子树本身至少需要深度 3（因为有 5 个可能的插入位置） - 所以我们可以轻松构建5+3 = 8-depth 树，但需要另一个构建有效深度 7 树的方法。

对于一般性讨论，尼克答案中关于排序网络的链接非常相​​关：您可以通过从左到右读取网络，为每个连接创建一个节点，然后考虑两种变体，从网络构建排序树作为孩子的网络：一个已经进行了交换（比如说，a<b是错误的，所以现在a并被b交换），另一个不需要它（因为a<b）。排序决策树的深度是其排序网络的深度，根据该页面，虽然有一种算法可以生成对数深度树/网络（AKS），但它绝不简单。

于 2019-04-24T11:35:13.857 回答