生成最佳二叉搜索树(Cormen)

本文介绍了生成最佳二叉搜索树(Cormen)的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

我正在阅读Cormen等人的《算法入门》 (第三版)(

让我们将 e [i，j] 定义为搜索包含从 i 到 j .最终，我们希望计算 e [1，n] ，其中 n 是键的数量(在此示例中为5).最终的递归公式为:

应通过以下伪代码实现:

请注意，伪代码可互换地使用基于1和0的索引，而Python仅使用后者.结果，我在实现伪代码时遇到了麻烦.这是我到目前为止的内容:

将numpy导入为npp = [0.15，0.10，0.05，0.10，0.20]q = [0.05，0.10，0.05，0.05，0.05，0.10]n = len(p)e = np.diag(q)w = np.diag(q)根= np.zeros((n，n))对于范围(1，n + 1)中的l:对于范围(n-l + 1)中的i:j = i + le [i，j] = np.infw [i，j] = w [i，j-1] + p [j-1] + q [j]对于范围(i，j + 1)中的r:t = e [i-1，r-1] + e [r，j] + w [i-1，j]如果t ＜e [i-1，j]:e [i-1，j] = t根[i-1，j] = r打印(w)打印(e)

但是，如果我执行此操作，权重 w 会正确计算，但是预期的搜索值 e 仍然停留"在其初始值:

[[0.05 0.3 0.45 0.55 0.7 1.][0. 0.1 0.25 0.35 0.5 0.8][0. 0. 0.05 0.15 0.3 0.6][0. 0. 0. 0.05 0.2 0.5][0. 0. 0. 0. 0.05 0.35][0. 0. 0. 0. 0. 0.1]][[0.05 inf inf inf inf][0. 0.1 inf inf inf inf][0. 0. 0.05 inf inf inf][0. 0. 0. 0.05 inf inf][0. 0. 0. 0. 0.05 inf][0. 0. 0. 0. 0. 0.1]]

我期望的是 e ， w 和 root 如下:

到目前为止，我已经调试了几个小时，但仍然遇到问题.有人可以指出上面的Python代码有什么问题吗?

解决方案

最后，我使用了 pandas 使用自定义 index 和 columns 初始化的' Series 和 DataFrame 对象，以强制数组具有与中相同的索引伪代码.之后，伪代码几乎可以复制粘贴:

将numpy导入为np将熊猫作为pd导入P = [0.15，0.10，0.05，0.10，0.20]Q = [0.05，0.10，0.05，0.05，0.05，0.10]n = len(P)p = pd.Series(P，index = range(1，n + 1))q = pd.Series(Q)e = pd.DataFrame(np.diag(Q)，index = range(1，n + 2))w = pd.DataFrame(np.diag(Q)，index = range(1，n + 2))根= pd.DataFrame(np.zeros((n，n))，索引=范围(1，n + 1)，列=范围(1，n + 1))对于范围(1，n + 1)中的l:对于范围在(1，n-l + 2)中的i:j = i + 1e.set_value(i，j，np.inf)w.set_value(i，j，w.get_value(i，j-1)+ p [j] + q [j])对于范围(i，j + 1)中的r:t = e.get_value(i，r-1)+ e.get_value(r + 1，j)+ w.get_value(i，j)如果t ＜e.get_value(i，j):e.set_value(i，j，t)root.set_value(i，j，r)打印(e)打印(w)打印(根)

产生预期的结果:

0 1 2 3 4 51 0.05 0.45 0.90 1.25 1.75 2.752 0.00 0.10 0.40 0.70 1.20 2.003 0.00 0.00 0.05 0.25 0.60 1.304 0.00 0.00 0.00 0.05 0.30 0.905 0.00 0.00 0.00 0.00 0.00 0.05 0.506 0.00 0.00 0.00 0.00 0.00 0.00 0.100 1 2 3 4 51 0.05 0.3 0.45 0.55 0.70 1.002 0.00 0.1 0.25 0.35 0.50 0.803 0.00 0.0 0.05 0.15 0.30 0.604 0.00 0.0 0.00 0.05 0.20 0.505 0.00 0.0 0.00 0.00 0.05 0.356 0.00 0.0 0.00 0.00 0.00 0.00 0.101 2 3 4 51 1.0 1.0 2.0 2.0 2.02 0.0 2.0 2.0 2.0 4.03 0.0 0.0 3.0 4.0 5.04 0.0 0.0 0.0 4.0 5.05 0.0 0.0 0.0 0.0 0.0 5.0

不过，我仍然对使用Numpy数组的解决方案感兴趣，因为这对我来说似乎更优雅.

I'm reading Cormen et al., Introduction to Algorithms (3rd ed.) (PDF), section 15.4 on optimal binary search trees, but am having some trouble implementing the pseudocode for the optimal_bst function in Python.

Here is the example I'm trying to apply the optimal BST to:

Let us define e[i,j] as the expected cost of searching an optimal binary search tree containing the keys labeled from i to j. Ultimately, we wish to compute e[1, n], where n is the number of keys (5 in this example). The final recursive formulation is:

which should be implemented by the following pseudocode:

Notice that the pseudocode interchangeably uses 1- and 0-based indexing, whereas Python uses only the latter. As a consequence I'm having trouble implementing the pseudocode. Here is what I have so far:

import numpy as np p = [0.15, 0.10, 0.05, 0.10, 0.20] q = [0.05, 0.10, 0.05, 0.05, 0.05, 0.10] n = len(p) e = np.diag(q) w = np.diag(q) root = np.zeros((n, n)) for l in range(1, n+1): for i in range(n-l+1): j = i + l e[i, j] = np.inf w[i, j] = w[i, j-1] + p[j-1] + q[j] for r in range(i, j+1): t = e[i-1, r-1] + e[r, j] + w[i-1, j] if t < e[i-1, j]: e[i-1, j] = t root[i-1, j] = r print(w) print(e)

However, if I run this the weights w get computed correctly, but the expected search values e remain 'stuck' at their initialized values:

[[ 0.05 0.3 0.45 0.55 0.7 1. ] [ 0. 0.1 0.25 0.35 0.5 0.8 ] [ 0. 0. 0.05 0.15 0.3 0.6 ] [ 0. 0. 0. 0.05 0.2 0.5 ] [ 0. 0. 0. 0. 0.05 0.35] [ 0. 0. 0. 0. 0. 0.1 ]] [[ 0.05 inf inf inf inf inf] [ 0. 0.1 inf inf inf inf] [ 0. 0. 0.05 inf inf inf] [ 0. 0. 0. 0.05 inf inf] [ 0. 0. 0. 0. 0.05 inf] [ 0. 0. 0. 0. 0. 0.1 ]]

What I expect is that e, w, and root be as follows:

I've been debugging this for a couple of hours by now and am still stuck. Can someone point out what is wrong with the Python code above?

解决方案

In the end I used pandas' Series and DataFrame objects initialized with custom index and columns to coerce the arrays to have the same indexing as in the pseudocode. After that, the pseudocode can be almost copy-pasted:

import numpy as np import pandas as pd P = [0.15, 0.10, 0.05, 0.10, 0.20] Q = [0.05, 0.10, 0.05, 0.05, 0.05, 0.10] n = len(P) p = pd.Series(P, index=range(1, n+1)) q = pd.Series(Q) e = pd.DataFrame(np.diag(Q), index=range(1, n+2)) w = pd.DataFrame(np.diag(Q), index=range(1, n+2)) root = pd.DataFrame(np.zeros((n, n)), index=range(1, n+1), columns=range(1, n+1)) for l in range(1, n+1): for i in range(1, n-l+2): j = i+l-1 e.set_value(i, j, np.inf) w.set_value(i, j, w.get_value(i, j-1) + p[j] + q[j]) for r in range(i, j+1): t = e.get_value(i, r-1) + e.get_value(r+1, j) + w.get_value(i, j) if t < e.get_value(i, j): e.set_value(i, j, t) root.set_value(i, j, r) print(e) print(w) print(root)

which yields the expected results:

0 1 2 3 4 5 1 0.05 0.45 0.90 1.25 1.75 2.75 2 0.00 0.10 0.40 0.70 1.20 2.00 3 0.00 0.00 0.05 0.25 0.60 1.30 4 0.00 0.00 0.00 0.05 0.30 0.90 5 0.00 0.00 0.00 0.00 0.05 0.50 6 0.00 0.00 0.00 0.00 0.00 0.10 0 1 2 3 4 5 1 0.05 0.3 0.45 0.55 0.70 1.00 2 0.00 0.1 0.25 0.35 0.50 0.80 3 0.00 0.0 0.05 0.15 0.30 0.60 4 0.00 0.0 0.00 0.05 0.20 0.50 5 0.00 0.0 0.00 0.00 0.05 0.35 6 0.00 0.0 0.00 0.00 0.00 0.10 1 2 3 4 5 1 1.0 1.0 2.0 2.0 2.0 2 0.0 2.0 2.0 2.0 4.0 3 0.0 0.0 3.0 4.0 5.0 4 0.0 0.0 0.0 4.0 5.0 5 0.0 0.0 0.0 0.0 5.0

I would still be interested in a solution with Numpy arrays, though, as this seems more elegant to me.