0

この形式でツリーを取得する効率的なアルゴリズムを考え出す必要があります。

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

クエスチョン マークのノードに、最小量のミューテーションを提供する値を入力します。値は {A、C、T、G} のみです。ツリーは、常にこの同じ形状とノードの数を持ちます。また、常にリーフ ノードが入力され、残りのノードは入力が必要な疑問符になります。

たとえば、右側のツリーは正しく、左側のものよりも突然変異が少なくなっています。

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

親ノードが子ノードと異なる場合、突然変異が発生します。したがって、左上のツリーには 5 つの突然変異が含まれ、右上には 1 つの突然変異が含まれます。

誰かが疑似コードを提供して助けてくれますか? ありがとう。

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
}

最良の回答と最良のコストを返すには、最良の回答に対応する組み合わせも追跡する必要があります。考えてみると、各ノードで 4 つの色すべての答えを同時に出すことで、時間を節約できます。

于 2012-11-05T04:49:23.787 に答える