将 SimpleCluster1D 伪代码转换为 python

Question

我指的是马塞尔·R·阿克曼(Marcel R. Ackermann(撰写的论文，发现 https://d-nb.info/100345531X/34。在论文中，Marcel为最优的一维K中位数算法编写了一个伪代码。它如下所示：

用于最佳 K 中位数的伪代码

我尝试将代码转换为 python，如下所示：

import math
import statistics
def cost(arr, median):
cost = 0
for i in range(len(arr)):
cost = cost + abs(arr[i] - median)
return cost
def simpleCluster1D(arr, k):
n = len(arr)
B = [[0] * k for i in range(n)]
C = [[0] * k for i in range(n)]
for i in range(k):
c = statistics.median(arr[:i+1])
B[i][0] = cost(arr[:i+1], c)
C[i][0] = c
for j in range(1, k):
for i in range(j, n):
B[i][j] = math.inf
C[i][j] = []
for t in range (j, i+1):
c = statistics.median(arr[t:i+1])
b = B[t-1][j-1] + cost(arr[t:i+1],c)
if b < B[i][j]:
B[i][j] = b
tmp = C[t-1][j-1]
C[i][j] = [C[t-1][j-1]] + [c]
return C[n-1][k-1]

但是，我获得的结果并不直观。 例如，当

arr = [50,60,70,80]
k = 2
simpleCluster1D(arr, k)

结果是 [0,80]，这是错误的。答案应该是[55,75]或[50,70]。 我不知道我哪里做错了。

我想知道是否有人可以帮助我进行此转换？我对数组 C 的声明有点困惑 - 数组的第 1 列包含中位数，第 2 列包含每个数组索引中的列表。我该怎么做？

此外，R/Python 的库/包是否已经具有内置的最佳一维求解器？我知道对于d>1，不可能达到最佳结果，因此使用启发式方法获得局部最优解。这就是为什么我得出的结论是，这些库也将用启发式方法解决一维问题，因此答案不是确定性的。我得出这个结论是对的吗？

Answer 1

我不知道

我哪里出错了。

你没有。错误出在论文中;行

1：对于 i = 1,2,...,k do

必须是

1：对于 i = 1,2,...,n do

- 否则，数组 B 和 C 的从 k+1 到 n 的行不会完全初始化。