0

我必须想出一个有效的算法，采用这种格式的树：

    ?           
   /  \       
  ?    ?      
 / \  / \  
G  A  A  A

并用提供最少突变量的值填充问号节点。值只能是 {A, C, T, G}。树将始终具有相同的形状和数量的节点。此外，它总是会填充叶节点，其余节点将是需要填充的问号。

例如，右边的树是正确的，并且比左边的树具有更少的突变。

    A           A
   /  \        /  \
  G    G      A    A
 / \  / \    / \  / \
G  A  A  A  G  A  A  A

当父节点与子节点不同时，就会发生突变。因此，左上方的树包含五个突变，而右上方有一个。

有人可以通过提供伪代码来帮助我吗？谢谢。

4

1 回答 1

0

这看起来像从树的底部向上的动态编程。对于每个节点，您要针对这些可能性中的每一个制定出将该节点标记为 A、C、T 或 G 的成本最低的解决方案。您可以通过使用先前为该节点正下方的节点计算的每种可能性的成本来解决此问题。只是计算成本的代码可能有点像这样。

LeastCost(node, colourHere)
{
  foreach colour
    leastLeft[colour] = LeastCost(leftChild, colour)
    leastRight[colour] = LeastCost(rightChild, colour)
  best = infinity
  foreach combination
    cost = leastLeft[combination.leftColour] +
      leastRight[combination.rightColour]
    if (combination.leftColour != colourHere)
      cost++;
    if (combination.rightColour != colourHere)
      cost++;
    if (cost < best)
      cost = best;
  return cost
}

要返回最佳答案以及最佳成本，您还需要跟踪与最佳答案相对应的组合。想一想，您可以通过同时计算每个节点的所有四种颜色的答案来节省时间。

于 2012-11-05T04:49:23.787 回答