3

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

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

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

示例数据

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

4

1 回答 1

2

我不知道python，但我可以用伪代码帮你。对于您的约束，这可能不是完美的最佳选择，但您可以根据需要对其进行调整。

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

将所有元素放入数组 elem[] 中，并begin先将它们排序为 lower。复制第一个元素并将其放在数组的末尾，10其坐标begin和end坐标都增加。（所以它可能会变成 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)，因为我不知道您需要处理多少个元素。使用浮点坐标，您无法得到比这更便宜的价格。

Possibility of improvement:当您知道有一个孔必须添加新元素来修复时，可能会丢弃先前选择的元素，无论是在孔的开头和/或结尾。例如，考虑元素 {(0,1), (0.7, 1.7), (1.8, 2.8), (2,3)}。在第二个和第三个元素之间有一个长度为 0.1 的孔，但是如果你添加一个长度为 1 的新元素并将它放在 1.0 和 2.0 之间，你实际上可以将第二个和第三个元素都扔掉。

于 2013-05-21T06:07:57.127 回答