algorithm - 在固定容量中找到所有可能的段平铺

Question

我正在寻找一种有效(比我的组合搜索更有效)的算法来平铺字符串段。

我有两件事:

• 要覆盖的“区域”的长度；
• 段集(段由开始和结束索引以及标签定义)

例子:区域的总长度为5。给定的段是:

- [(0,2), "A B"]
 - [(1,3), "B C"]
 - [(1,4), "B C D"]
 - [(3,5), "D E"]

我正在使用 Python 符号来表示段，例如(0,2) 和它的标签 "A B"一个字符串。

有 3 种方法可以用给定的段填充大小为 5 的“区域”而不重叠:

 1. ("A B"), ("D E")
 2. ("B C"), ("D E")
 3. ("B C D")

其他拼贴是不可能的，因为额外的部分将与已经位于“区域”中的现有拼贴之一重叠。

我目前的方法是从一个片段开始，看看我得到了多少非重叠片段的组合。然后是两个段，依此类推，直到 4。如果无法添加任何剩余段，则检查每个组合的有效性。如果可以插入任何剩余段，则整个组合被拒绝为无效。当片段不多且重叠/组合很少时，此方法非常有效。

是否有一种简单而有效的算法来找到这些“瓦片”？

Answer 1

有一种动态规划方法，您可以沿着要覆盖的区域从左到右工作，并在每个点计算出在该点整齐地完成的平铺数量。要计算这一点，请查看覆盖该点并在该点结束的线段。对于这些段中的每一个，以该段结束的平铺数是在该段开始之前结束的平铺数，您已经计算过了。因此，将这些数字相加以获得覆盖该点并在该点结束的瓷砖数量。你想要的答案是在要覆盖的区域中覆盖终点并在该点结束的瓷砖数量(假设想要整齐地结束或将被迫结束)。

如果您只想要一种可能的拼贴，则无需计算在每个点终止的拼贴数量，您只需要一个标志来告知是否有任何拼贴在该点终止。如果您还记下平铺终止的每个点，其中一个平铺在该点终止的平铺，则以后检索可能的平铺会更容易。

现在您可以算出一种可能的平铺方式来平铺整条线。查看字符串中最后一个字符的条目。这为您提供了结束该平铺的部分。鉴于该段，您知道它的长度。如果它的长度为 3，并且最后一个偏移量是偏移量 10，则必须有一个有效的平铺在偏移量 7 处终止。您会注意到在偏移量 7 处终止的段，它为您提供了所需平铺中的倒数第二个段。通过查看该片段的长度，您可以确定在哪里可以找到该片段之前的音符，依此类推，直到您从右到左恢复了整个拼贴。