15

要素のリストがあり、それぞれがタイプで識別されています。同じタイプの要素間の最小距離を最大化するために、リストを並べ替える必要があります。

セットは小さいので（10〜30アイテム）、パフォーマンスはそれほど重要ではありません。

タイプごとのアイテムの数やタイプの数に制限はなく、データはランダムと見なすことができます。

たとえば、次のリストがある場合：

  • A5点
  • B3点
  • Cの2アイテム
  • D2点
  • E1点
  • F1点

次AのようなものBを作成したい Cと思います：、、、、、、、、、、、、、、、、、ADFBAECADBA

  • Aには、発生の間に少なくとも2つのアイテムがあります
  • Bには、発生の間に少なくとも4つのアイテムがあります
  • Cには発生の間に6つのアイテムがあります
  • Dは発生の間に6つのアイテムがあります

これを達成するためのアルゴリズムはありますか？

-アップデート-

いくつかのコメントを交換した後、私は二次的な目標の定義に到達しました：

  • 主な目標：距離の短いタイプのみを考慮して、同じタイプの要素間の最小距離を最大化します。
  • 二次目標：すべてのタイプの要素間の最小距離を最大化します。IE：組み合わせによって、特定のタイプの最小距離が他のタイプを減少させることなく増加する場合は、それを選択します。

-アップデート2-

答えについて。有用な答えはたくさんありましたが、どちらも両方の目標の解決策ではありません。特に、2番目の目標は注意が必要です。

答えについてのいくつかの考え：

  • PengOne：具体的な実装を提供するわけではありませんが、良さそうに聞こえます。また、2番目の目標に従って常に最良の結果が得られるとは限りません。
  • Evgeny Kluev：主な目標に具体的な実装を提供しますが、副次的な目標によると最良の結果にはつながりません。
  • tobias_k：ランダムなアプローチが好きでした。常に最良の結果が得られるとは限りませんが、適切な近似値であり、費用対効果が高くなります。

Evgeny Kluev、バックトラッキング、およびtobias_k式の組み合わせを試しましたが、結果を得るのに時間がかかりすぎました。

最後に、少なくとも私の問題については、tobias_kが最も適切なアルゴリズムであると考えました。その単純さと、タイムリーな結果が得られるからです。おそらく、シミュレーテッドアニーリングを使用して改善できる可能性があります。

4

6 に答える 6

5

まず、明確に定義された最適化問題はまだありません。同じタイプの2つのアイテム間の最小距離を最大化したい場合は、それが明確に定義されています。2つのA間および2つのBと...間および2つのZ間の最小距離を最大化したい場合、それは明確に定義されていません。2つのソリューションをどのように比較しますか？

  1. Aは少なくとも4つ離れており、Bは少なくとも4つ離れており、Cは少なくとも2つ離れています。
  2. Aは少なくとも3つ離れており、Bは少なくとも3つ離れており、Cは少なくとも4つ離れています。

「良い」（より正確には「より良い」）の明確な尺度が必要です。今のところ、測定値は次のとおりであると想定します。同じアイテムの任意の2つの間の最小距離を最大化します。

これは、最小距離を達成するアルゴリズムです。ここでceiling(N/n(A))、Nはアイテムの総数であり、n(A)はインスタンスのアイテムの数です。これが最も多いAと仮定します。A

  • A1, A2, ... , Akアイテムタイプを注文しますn(Ai) >= n(A{i+1})。
  • リストLを空に初期化します。
  • jfromkから、までのタイプのアイテムを。でできるだけ均一に1配布します。AkL

例：質問の分布が与えられると、アルゴリズムは以下を生成します。

F
E, F
D, E, D, F
D, C, E, D, C, F
B, D, C, E, B, D, C, F, B
A, B, D, A, C, E, A, B, D, A, C, F, A, B
于 2012-09-11T19:28:24.580 に答える
4

これは面白い問題のように聞こえたので、試してみました。Pythonで行われた私の超単純なランダム化アプローチは次のとおりです。

def optimize(items, quality_function, stop=1000):
    no_improvement = 0
    best = 0
    while no_improvement < stop:
        i = random.randint(0, len(items)-1)
        j = random.randint(0, len(items)-1)
        copy = items[::]
        copy[i], copy[j] = copy[j], copy[i]
        q = quality_function(copy)
        if q > best:
            items, best = copy, q
            no_improvement = 0
        else:
            no_improvement += 1
    return items

コメントですでに説明したように、本当にトリッキーな部分は、オプティマイザーにパラメーターとして渡される品質関数です。いくつか試した後、ほとんどの場合、最適な結果が得られるものを思いつきました。これをより効率的にする方法を指摘してくれたpmoleriに感謝します。

def quality_maxmindist(items):
    s = 0
    for item in set(items):
        indcs = [i for i in range(len(items)) if items[i] == item]
        if len(indcs) > 1:
            s += sum(1./(indcs[i+1] - indcs[i]) for i in range(len(indcs)-1))
    return 1./s

そしてここにいくつかのランダムな結果：

>>> print optimize(items, quality_maxmindist)
['A', 'B', 'C', 'A', 'D', 'E', 'A', 'B', 'F', 'C', 'A', 'D', 'B', 'A']

別の品質関数を渡すと、同じオプティマイザをさまざまなリスト再配置タスクに使用できることに注意してください。たとえば、（かなりばかげた）ランダム化ソーターとして使用できます。

于 2012-09-11T19:36:45.950 に答える
3

これは、同じタイプの要素間の最小距離のみを最大化し、それを超えることは何もしないアルゴリズムです。次のリストを例として使用します。

AAAAA BBBBB CCCC DDDD EEEE FFF GG
  • 各タイプの要素数の降順で要素セットを並べ替えます。実際には、最大のセット（A＆B）と、要素が1つ少ない要素セット（C＆D＆E）のみをリストの先頭に配置する必要があります。他のセットはソートされていない可能性があります。
  • 配列内のRの最後の位置を、最大の各セットの1つの要素用に予約し、残りの配列を最大のセットの残りのS-1個の要素に均等に分割します。これにより、最適な距離が得られます：K =（N-R）/（S-1）。ターゲット配列を、K列およびL = N / Kの完全な行（および場合によってはN％Kの要素を持つ1つの部分行）を持つ2D行列として表します。たとえば、セットにはR = 2、S = 5、N = 27、K = 6、L=4があります。
  • 行列にS-1の完全な行がある場合は、この行列の最初のR列に最大のセット（AおよびB）の要素を入力します。それ以外の場合は、最後の列から順にすべての列に入力します。

この例では、次のようになります。

AB....
AB....
AB....
AB....
AB.

残りの列を同じ順序で他のセットで埋めようとすると、問題が発生します。

ABCDE.
ABCDE.
ABCDE.
ABCE..
ABD

最後の「E」は、最初の「E」からわずか5桁離れています。

  • 最後の列から順に、すべての列に入力します。

この例では、次のようになります。

ABFEDC
ABFEDC
ABFEDC
ABGEDC
ABG

線形配列に戻ると、次のようになります。

ABFEDCABFEDCABFEDCABGEDCABG

この問題にシミュレーテッドアニーリングを使用する試みは次のとおりです（Cソース）：http：//ideone.com/OGkkc。

于 2012-09-12T14:06:31.567 に答える
0

物理的に互いに反発する粒子の束のように問題を見ることができると思います。「安定した」状況を繰り返すことができます。

基本的な擬似コード：

force( x, y ) = 0 if x.type==y.type
                1/distance(x,y) otherwise 

nextposition( x, force ) = coined?(x) => same
                           else => x + force

notconverged(row,newrow) = // simplistically
   row!=newrow

row=[a,b,a,b,b,b,a,e]; 
newrow=nextposition(row);
while( notconverged(row,newrow) )
   newrow=nextposition(row);

収束するかどうかはわかりませんが、それはアイデアです:)

于 2012-09-11T19:37:44.267 に答える
0

より効率的な解決策があると確信していますが、次の1つの可能性があります。

まず、同じタイプのアイテム間の最小距離が1になる順序を見つけるのは非常に簡単であることに注意してください。ランダムな順序を使用するだけで、MDBIOSTは少なくとも1になります。

したがって、MDBIOSTが2になるという仮定から始めます。MDBIOSTが2になるという仮定に基づいて、可能な順序のスペースを再帰的に検索します。この検索からブランチをプルーニングするために使用できる条件がいくつかあります。正常に機能する順序が見つかった場合は、検索を終了します。

動作するものが見つかった場合は、MDBIOSTが3になると想定して、再試行します。次に、検索が失敗するまで4...というように続きます。

更新：実際には、可能な選択肢をより制限するため、高い数値から始める方が良いでしょう。次に、機能する順序が見つかるまで、数を徐々に減らします。

于 2012-09-11T19:42:47.493 に答える
0

別のアプローチがあります。

すべてのアイテムを同じタイプの他のすべてのアイテムから少なくともkの場所に保持する必要がある場合は、各タイプの残りのアイテムの数を追跡しながら、アイテムを左から右に書き留めます。それぞれの時点で、合法的に置くことができる残りの最大数のアイテムを置きます。

これは、同じタイプのceil（N / k）アイテムしか存在しない場合、このプロパティを保持するため、N個のアイテムに対して機能します。k個のアイテムを配置した後、k個のアイテムが少なくなり、少なくとも1つを配置しました。そのタイプのceil（N / k）アイテムで始まる各タイプ。

混合アイテムのクラッチが与えられた場合、サポートできる最大のkを計算し、このkを解決するためにアイテムをレイアウトできます。

于 2015-03-27T20:49:17.427 に答える