重複の可能性:
同じタイプのアイテムを分離するアルゴリズム
私の友人のプロジェクトから興味深い問題があります。彼はテレビ広告の配置に取り組んでいます。広告は、モバイル、食品、銀行など、さまざまな種類のものです。彼は、広告のリストを並べ替えて、類似した種類の広告が互いに最大の距離で配置されるようにする必要があります。広告ブロックには約 100 の広告があるため、ブルート フォース ソリューションは実行できません。合理的に高速なソリューション (<30 秒) を考え出すことは可能ですか? これを行うための最速の方法は何ですか?
各広告の長さが同じであると仮定します。
例:
[M, M, F, B, F, B]. この特定のシナリオでは、出力は次のようになります。[M, F, B, M, F, B]
最小距離を最大化するとします。まず、持っているアイテムの種類ごとの数を数えます (これらすべての合計がn、リスト内のアイテムの数になります)。ユニークな種類のアイテムのリストを頻度に従って並べ替えます。n次に、セルを含む出力テープを準備します。最も頻度の高い要素から始めて、等間隔で要素を出力テープに均等に配置します。テープ上の空のセルのみを考慮して、項目頻度の降順で続行します。これは ですO(n + m log m)。ここnで、 はアイテムの総数であり、mは固有のアイテム (つまり、アイテムの種類) の数です。この場合、アイテムの種類に線形ソート アルゴリズムを使用することでおそらく回避できることに注意してください。log mただし、実際には (100 個のアイテムと、おそらくもっと少ない種類のアイテムの場合)、それだけの価値があるかどうかはわかりません。
あなたの例では：[M、M、F、B、F、B]。(M, 2)、(F, 2)、(B, 2) があります。最初のパスの後に [M, _, _, M, _, _] を取得し、2 回目のパスの後に [M, F, _, M, F, _] を取得し、[M, F, B, M, F, B] を取得します。三回目以降。
これはヒューリスティックであり、最適である可能性があると思いますが、これが最適であることを証明しようとはしていません。ただし、n要素があり、最も頻繁に要素が表示xされる場合、最小距離はおそらくfloor(n/x)(編集: これは実際には真実ではありません。私のコメントを参照してください) ... であり、それがこのヒューリスティックが狙っているものです。数字が除数でさえない場合、アイテムを「均等に」配置する方法についての質問があると思います...しかし、これが発生する場所で試した例でも、最適化する基準に関しては、ほぼすべての選択で問題ありません. 少し難しい例:
[A, A, A, A, A, B, B, B, C, C, D] は (A, 5), (B, 3), (C, 2), (D, 1) を与えます。[A, _, A, _, A, _, A, _, A, _, _] を最初のパス [A, B, A, _, A, B, A, _, A, B , _] は 2 回目のパスの後、[A, B, A, C, A, B, A, C, A, B, _] は 3 回目のパスの後、[A, B, A, C, A 、B、A、C、A、B、D]。政府の仕事には十分です。
実際、平均距離を最小化するためのこれよりも簡単な方法は考えられません。これはかなり速いはずです...あなたの友人のニーズに十分近いですか？