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

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()确定。创建一个人工源，其中每个节点的出射弧都以左边界为起点。从右边界为末端的每个节点创建一个带有传入弧的人工汇。

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

Answer 2

这有点晚了，但我确实解决了这个问题。为此，我最终使用了稍微修改过的 Dijkstra 版本，但任何寻路算法都可以工作。我也尝试了 A*，但由于问题的非欧几里德性质，找到一个好的启发式被证明是极其困难的。

Dijkstra 的主要变化是在某些时候我已经知道一些未访问的节点无法提供最佳结果。这大大加快了算法速度，这也是我没有选择 A* 的原因之一。

算法基本上是这样工作的：

search()
  visited = set()
  costs = map<node, double>()
  
  // add initial node to costs

  while costs is not empty:
    node = node with minimum cost in costs

    if current.Index == songEnd:
      // backtrack from current to get fingering for the song
      return solution

    visited.add(node)

    foreach neighbour of node:
      if visited node:
        continue
      
      newCost = costs[node] + distance(node, neighbour)
      add neighbour with newCost to costs

    
  // we can remove nodes that have a higher cost but
  // which have a lower index than our current node
  // this is because every fingering position is reachable
  // from any fingering positions
  // therefore a higher cost node which is not as far as our current node
  // cannot provide an optimal solution
  remove unoptimal nodes from costs

  remove node from costs

// if costs ends up empty then it is impossible to play this song
// on guitar (e.g. more than 6 notes played at the same time)

这个算法的神奇之处在于获取邻居和计算两个节点之间的距离，但这些与这个问题无关。

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

Algorithm for finding optimal multiple partitionings based on some costs

algorithm

search

midi

dijkstra