基于一些成本，寻找最优多重分区的算法。

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* ?）来解决这个问题。这可能非常有效，因为我们可以比在常规图中更快地过滤掉不好的解决方案（因为输入技术上是一个完整的图，因为任何一个指法都可以从其他任何一个指法到达）。

我无法决定最佳方法是什么，因此目前被卡住了。任何提示或想法都将不胜感激。

- porras

---

第一个子数组是否总是[]，或者有些子数组不允许，或者需要最少的子数组？更具体地说，什么阻止你取整个数组？ - kcsquared

@kcsquared 是的，第一个子数组总是空的，因为在演奏一首歌时，你开始时没有手指放在任何弦上。整个数组只有在歌曲最多包含6个不同音符并且它们可以同时演奏时才能被取出。然而，对于任何真实的歌曲来说，这种情况可能永远不会发生。 - porras

Answer 1

这可能不是NP难问题。

构建一个图，其节点与（连续的）子数组一一对应。对于每对节点u、v，其中u的右边界为v的左边界，从u到v添加一条弧，其长度由distance()确定。创建一个带有从开头开始的每个节点的出弧的人工源。创建一个带有从结尾结束的每个节点的入弧的人工汇。

现在，我们可以通过有向无环图的线性时间算法（大小为图参数的立方）找到从源到汇的最短路径。

- David Eisenstat

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)

该算法的神奇之处在于获取相邻节点并计算两个节点之间的距离，但对于本问题来说这些都不相关。

- porras