3

n 組の数値が与えられた場合、最初の数値は常に 2 番目の数値よりも小さくなります。ペア (c, d) がペア (a, b) の後に続くのは、b <= c の場合のみです。ペアの連鎖は、このようにして形成できます。与えられたペアのセットから形成できる最長のチェーンを見つけます。

例えば{ (1,2), (3,4), (5,7), (9,10), (7,9), (8,9), (0,6) }

したがって、出力は次のようになります。{(1,2), (3,4), (5,7), (8,9), (9,10)}

これに対する私のアルゴリズムは次のとおりです。

 1. Sort the list according to the 2nd number of elements
i.e.`{ (1,2), (3,4), (0,6), (5,7), (7,9), (8,9), (9,10)  }`
 2. choose the first element from the list  i.e. `(1,2)`
 3. for each element e in the list left
      4. choose this element e if the first number of the element is greater than the 2nd number of the previous element. i.e. after `(1,2)` choose `(3,4)` because `3 > 2.`

上記のアルゴリズムの後、出力は{(1,2), (3,4), (5,7), (8,9), (9,10)}.

アルゴリズムの正しさについて教えてください。ありがとう。

編集：

より直観的な正しさの証明:

証明: より多くのペアをチェーンに含める唯一の方法は、ペアをより小さな Y 値を持つペアに置き換えることです。これにより、次のペアがより小さな X 値を持つようになり、以前は収まらなかった別のペアが収まる可能性があります。ペアを同じ Y 値のペアに置き換えても、何も得られません。置換の Y 値が大きい場合は、以前は適合していたいくつかのペアを潜在的にブロックするだけです。

ペアは Y 値でソートされているため、より小さな Y の置換を見つけることはできません。ソートされたペアを「前方」に見ると、それらはすべて同じかそれ以上の Y 値を持ちます。「後ろ向き」に見ると、最初にチェーンから除外されたものは、X 値が十分に高くなかったためでした。

これはここから取られます

4

3 に答える 3

2

正しいです。ここに証明があります：

s1, s2, ..., slあなたのアルゴリズムによって見つけられたペアでi1, i2, ..., ikあり、最適解であるとしましょう。

我々は持っています：

l == k => your algorithm is obviously correct, since it's clear that
          it doesn't produce invalid solutions;

l > k => this would contradict our hypothesis that i1, ..., ik is optimal,
         so it makes no sense to bother with this;

l < k => this would mean that your algorithm is wrong. 
         Let's assume this is the case.

と仮定しi1 != s1ます。この場合、終了時間が最も短いペアであるため、最適なソリューションでi1置き換えることができます。したがって、最適なソリューションのままです。s1s1s1, i2, ..., ik

t <= lを最初のインデックスにしますst != it。したがって、s1, s2, ..., s[t-1], it, ...最適なソリューションです。次の理由で置き換えることができますit。st

  • st最適解の最初のt-1要素の一部ではありません。
  • stの一部ではありませんi[t+1], ..., ik。もしそうなら、それはそれが終わっstた後に始まったことを意味しit、アルゴリズムが選択する方法と矛盾しますst.

したがって、この方法を続けると、最適解は になりs1, s2, ..., sl, ..., ikます。これは、 の後にさらにペアを追加できることを意味しますがsl、これはアルゴリズムの動作方法と矛盾するため、l = kとなり、アルゴリズムは正しいです。

于 2013-08-02T14:37:27.817 に答える