python - 选择优化最小数量的元素以跨越一个区域

Question

我有一个优化问题。我没学过算法，只自学了python，所以我不确定这是一个难解决的问题还是容易解决的问题。这个问题的非抽象应用是确定使用可用试剂对 DNA 进行测序的最便宜的方法。现在的问题...

有一个圆形区域，比如 0-10，其中 10 循环回到 0。有长度为 1 的元素，每个元素跨越该区域的一部分，最终目标是在覆盖每个位置的同时尽量减少元素的数量.我有一些长度为 1 的元素，但这些元素并没有覆盖整个区域。因此，我需要付费添加额外的元素。

因此最终成本将类似于(元素数量)+ 2(购买的元素数量)，目标是最小化成本。这是一个容易解决的问题，还是需要付出巨大的努力才能解决？

所以在这个例子中，我会选择在大约 2 和 5.75 处添加一个值，并在大约 2.5 处删除一些值。

Answer 1

我不懂python，但我可以帮你写伪代码。对于您的约束，这可能不是完美，但您可以根据需要调整它。

假设您的元素有两个属性，begin 和 end，它们分别定义开始和结束位置的 X 坐标! (即使你的结尾总是 begin+1。如果一个元素从 9.5 开始，考虑它以 10.5 而不是 0.5 结束)

将所有元素放入一个数组 elem[] 中，并首先按较低的 begin 对它们进行排序。复制第一个元素并将其放在数组的末尾，在其 begin 和 end 坐标上递增 10。 (因此它可能会变成 10.2 到 11.2 之类的东西)这是为了涵盖您问题的循环方面，我们仅将其用作引用，但不会将其计入成本中两次。

X = 0  (the farthest you have got covered so far)
foreach element i in array, in order, except for last element:
  if elem[i+1].begin <= X
    continue; // this means you dont need the current element, discard it and go to the next iteration of the loop.
  if elem[i].begin <= X
    X = elem[i].end // you will use this element to expand your reach
  else // bad news, you got an empty hole
    add_elements += ceil(elem[i].begin - X)  // ceil = round up to an integer number of elements needed to cover the hole
    X = elem[i].end // you will use this element anyway!

if X < 10 // after the loop ends
  add_elements += ceil(elem[last].begin - X)

您可以重写最后一个 if/else 以只需要一个 if，我只是认为这种方式会更具教学性和更容易理解。

add_elements 包含您需要添加多少个额外元素。 ceil() 函数是这样的，如果你有一个长度为 2.4 的连续孔，你知道你至少需要 3 个新元素来修复它。

这个算法相当简单快速，初始排序的时间复杂度为O(n logn)，因为我不知道你需要处理多少元素。使用浮点坐标，没有比这更便宜的了。

改进的可能性:当您知道必须添加新元素来修复的漏洞时，可以丢弃之前选择的元素，或者在洞的开始和/或结束。例如，考虑元素 {(0,1), (0.7, 1.7), (1.8, 2.8), (2,3)}。第二个和第三个元素之间有一个长度为0.1的洞，但是如果你在1.0和2.0之间添加一个长度为1的新元素，实际上可以把第二个和第三个元素都扔掉。