On Huang and Wong’s algorithm for generalized binary split trees
On Huang and Wong’s algorithm for generalized binary split trees
复制标题
关于 Huang 和 Wong 的广义二叉分裂树算法
DOI：
10.1007/s00236-021-00411-z
复制
发表时间：
2019
期刊：
影响因子：
0.6
通讯作者：
N. Young
中科院分区：
文献类型：
--
作者：
M. Chrobak;M. Golin;J. Munro;N. Young
Huang和Wong(Acta Inform 21(1)：113-123,1984)提出了一种计算最优广义二叉分裂树的多项式时间动态规划算法。我们证明了他们的算法是错误的。因此，这种树是否可以在多项式时间内计算仍然是个未知数。Spuer(基于双向关键字比较的最优搜索树，博士论文，1994)建议对Huang和Wong的算法进行修改，以获得一个不同问题的算法：计算最优双向比较搜索树。我们证明了基于Spuer算法的动态规划是无效的，因为它不满足必要的最优子结构性质，并且它所提出的递推关系是错误的。目前尚不清楚该算法是否能保证计算出正确的整体解。
Huang and Wong (Acta Inform 21(1):113–123, 1984) proposed a polynomial-time dynamic-programming algorithm for computing optimal generalized binary split trees. We show that their algorithm is incorrect. Thus, it remains open whether such trees can be computed in polynomial time. Spuler (Optimal search trees using two-way key comparisons, PhD thesis, 1994) proposed modifying Huang and Wong’s algorithm to obtain an algorithm for a different problem: computing optimal two-way comparison search trees. We show that the dynamic program underlying Spuler’s algorithm is not valid, in that it does not satisfy the necessary optimal-substructure property and its proposed recurrence relation is incorrect. It remains unknown whether the algorithm is guaranteed to compute a correct overall solution.