algorithm - 特定の最小距離/差で整数の最大サブセットを取得します

Question

私は整数のセットまたは例を持っています: {1,3,4,5,10} 今、各要素が他の要素との距離/差が最小である最大の (最大 = ほとんどの要素) サブセットが必要です。

たとえば、セット {1,3,4,5,10} と最小距離 2 の場合、結果は次のようになります。

{1,3,5,10}

または距離 3 の場合:

{1,5,10}

その問題を解決するための (優れた/効率的な) アルゴリズムは存在しますか?

Answer 1

これは間違いなく NP 完全問題ではありません。

実際には、これは古典的なインターバル スケジューリング問題の特殊なケースですが、通常のインターバル スケジューリング問題では、長さは固定されていません。

ここであなたの問題では、各数値が間隔の開始時間であり、各間隔が間隔の長さとして「最小距離」を持っていることを確認できます。

各インターバルには、開始時刻 + インターバルの長さである終了時刻があります。

したがって、解決策は

1 すべてのインターバルを終了時刻でソートします。

2 並べ替えられた順序で 1 つずつ確認し、結果セット内のすべての既存の間隔と互換性のある間隔を結果セットに追加します。

このソリューションは最適であり、O(nlogn) 時間の複雑さがあります。

上記のリンクで、他の貪欲なアルゴリズムに関する証拠と情報を見つけることができます。

Answer 2

これらの線に沿った何か：

1）入力を並べ替えます。

2）入力を確認し、各要素に、選択された場合にセットから除外する要素の数をマークします。

3）利用可能な要素から、マークが最も低い要素を順番に選択します。

4）除外された要素を削除します。

5）3）と4）を繰り返します

だから、あなたの例では：

1  3  4  5  10     - difference 3

ステップ1はすでに完了しており、ステップ2に進むと次のようになります。

1  3  4  5  10
1  3  2  2  0

説明-を選択した場合1、1つの数値-3を除外します。を選択3すると、1、4、5の3つの数字が除外されます。

次のステップ：

• 10を選択し、何も削除しません。-1 3 4 5 (10)
• 1を選択し、3を削除します。-(1) 4 5 (10)
• 4（または5）を選択し、5（または4）を削除します-1 4 10

これが機能することを保証するものではありませんが、それは始まりです...

Answer 3

はい、次の貪欲なアルゴリズムは最適なソリューションを提供します。ソートされた順序で整数をスキャンし、前に取得した整数が十分に離れている場合は各整数を取得します。正しさは、すべての解 S とすべての整数 u に対して、貪欲な解が少なくとも S と同じ数の整数 ≤ u を選択するという帰納的証明によって導かれます。