基于某些成本寻找最佳多重分区的算法

Question

我有一种情况，我需要根据一些成本在数组中找到最佳分割位置。问题是这样的:

作为输入，我有一个按整数时间戳排序的事件数组，作为输出，我想要一个索引数组，它将输入数组分成许多部分。输出数组需要是最优的(更多内容见下文)。

struct e {
    int Time;
    // other values
}

Example Input:  [e0, e1, e2, e3, e4, e5, ..., e10]
Example output: [0, 2, 6, 8] (the 0 at the start is always there)

使用上面的示例，我可以使用拆分索引将原始数组分成 5 个子数组，如下所示:

[ [], [e0, e1], [e2, e3, e4, e5], [e6, e7], [e8, e9, e10] ]

此示例解决方案的成本是子阵列之间“距离”的总成本:

double distance(e[] arr1, e[] arr2) {
    // return distance from arr1 to arr2, order matters so non-euclidean
}

total cost = distance([], [e0, e1]) + distance([e0, e1], [e2, e3, e4, e5]) + ...

此时有助于理解实际问题。

输入数组表示某个时间的音符(即 MIDI 文件)，我想将 MIDI 文件拆分为最佳吉他指法。因此，每个音符子阵列代表一个和弦(或在一个指法中组合在一起的旋律)。两个子阵列之间的距离表示从一种指法模式移动到另一种指法模式的难度。目标是找到用吉他弹奏歌曲的最简单(最佳)方式。

我还没有证明它，但对我来说这看起来像是一个 NP-Complete 或 NP-Hard 问题。因此，如果我可以将其简化为另一个已知问题并使用已知的分而治之算法，它可能会有所帮助。此外，可以使用更传统的搜索算法 (A* ?) 来解决这个问题。它可能是高效的，因为我们可以比在常规图中更快地过滤掉不好的解决方案(因为输入在技术上是一个完整的图，因为每个指法都可以从任何其他指法到达)。

我无法决定最好的方法是什么，所以我目前被困住了。任何提示或想法将不胜感激。

Answer 1

它可能不是 NP-hard。

形成一个图，其节点与(连续的)子数组一一对应。对于每对节点 u，v，其中 u 的右边界是 v 的左边界，添加一条从 u 到 v 的弧，其长度由 distance() 确定。创建一个人工源，其中每个节点的出射弧都以左边界为起点。创建一个人造汇，其中每个节点的入弧都以右边界为终点。

现在我们可以通过有向无环图的线性时间(在图的大小中，因此是感兴趣的参数的立方)算法找到从源到汇的最短路径。