4

それぞれ 500 個のオブジェクトを 9 セット持っています。セットは独立していますが、セットは共通のオブジェクトのコアを共有していると思います。ただし、同じオブジェクトでも、セットによって名前 (インデックス) が異なる場合があります。しかし、2 つのオブジェクト間のペアごとの距離を測定することはできます。

ペアごとの距離に基づいて、セットのすべてのペアについて、2 つのセットのオブジェクト間の最適なマッピングを既に計算しました。したがって、セットのすべてのペアについて、任意の 2 つのオブジェクト間の対応を示すことができます。

ここで、{ 5 (セット 1) -> 13 (セット 2) -> 24 (セット 3) -> 5 (セット 1) } などの閉じたマッピング円を検出します。つまり、セット 1 のオブジェクト 5 は、オブジェクト 13 にマップされます。セット 2 はセット 3 の 24 にマップされ、セット 1 のオブジェクト 5 にマップされます。オブジェクトが本質的に同じであると主張するには、この形式の循環マッピングが必要です。

もちろん、理想的な世界では、9 つ​​のセットすべてにまたがる大部分の円を特定できます。しかし、3～9セット間の共通オブジェクトも興味深いものです。したがって、網羅的なリストが必要です。

このタスクを実行するアルゴリズム、またはこの問題が組み合わせ数学でどのように呼ばれているか知っていますか!?

ヒューリスティックなアプローチとして、3 つのセットのすべての組み合わせ内で円を決定することから始め、これらの結果を組み合わせてより大きなセットの組み合わせを作成します。

4

1 に答える 1

0

私があなたの説明に正しく従えば、セット間の対応を見つけたいと思うようです. このアルゴリズムはあなたのために働くでしょうか。

 1. Intialize a hashmap H
 2. Initialize key frequency map U = {}
 3. for each set i 
 4.    for each element e in set i
 5.        H.insert {e.key, {i, ...}}
 6.        if U.contain(e.key)
 7.            c = U.get(e.key)
 8.           U.update(e.key,  c + 1)
 9.        else
10.            U.insert(e.key,  1)
11.        endif 
12.    endfor
13. endfor

行 5 は要素をマップ H に挿入します。同じキーを持つ要素はリンクされたリストに格納されます。U で最大の頻度を持つキーを見つけることで、最長のチェーンを見つけることができます。次に、H.get(key) を実行すると、リストが返されます。最後の要素を最初の要素にリンクすることで、求めるサイクルが得られます。

これが役立つことを願っています。

于 2013-02-13T20:45:35.340 に答える