1

わかりました...少しトリッキーなものがあります（少なくとも私にとっては）。

単純なオブジェクトのリストがあり、最大数を利用する組み合わせを見つける方法を見つける必要があります。これらのオブジェクトの各クラスには、名前のプロパティ (文字列)、結合する他の要素の名前のプロパティ (リスト)、結合する他の要素の名前のプロパティ (リスト) があります。結合するのが好きではありません。

コレクションに要素が追加され、その特定の要素が既にコレクション内にある他の要素の 1 つ (または複数) を「気に入っている」場合、追加された要素はコレクション内の気に入った各項目に対して +1 のスコアを返します。同様に、追加された要素が気に入らないコレクション内の他の要素ごとに -1 のスコアが返されます。すべての要素を最終的なコレクションに追加した後、各要素のスコアは >= 0 でなければなりません。

最大のコレクションを返すために使用できる要素の組み合わせを見つけるにはどうすればよいですか? 複数の組み合わせが同じ数の要素を返す場合は、すべての可能な組み合わせを返す必要があります。

それが理にかなっていることを願っています...また、私はC＃（.NET 4.0）を使用していますが、どのプログラミング言語も使用できます。その背後にあるロジックを理解する必要があるだけです。

前もってありがとう、
ソニー

4

1 に答える 1

2

これは難しい問題だとおっしゃるのが正しいと思います。オブジェクトはグラフのノードであり、好き嫌いの情報はノード間のリンクに重みを与えるものと考えています。「いいね」フィールドを無視して、すべてのリンクの重みを 0 または -1 にします。この場合、問題は、ノード間のすべてのリンクの重みが 0 で、重みが -1 のリンクがないように、ノードの最大数を見つけることです。これを効率的に行うプログラムがあるとします。

ここで問題http://en.wikipedia.org/wiki/Clique_problemを見てください。これは既知の困難な問題です。最大クリークの問題がある場合は、すべてのノード間にリンクを作成します。max clique で 2 つのノードがリンクされている場合は、重みを 0 にします。リンクが存在しない場合は、重みを -1 にします。問題を解決するプログラムを実行すると、max clique が解決されます。したがって、あなたの問題は NP-Complete であり、効率的な解決策がある可能性はほとんどありません。

于 2011-10-21T04:17:38.637 に答える