3

いくつかの実験データがあり、それらをセットとして表すことにしました。

たとえば、 E={a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,q,r,s}というメイン セットがあるとします。 (青い円) と、メイン セットEの要素を含むいくつかのサブセットB (赤い点線の楕円) 。

これらのサブセットをメイン セットEで表し、それらの交差を示す必要があります。多かれ少なかれ下の図に似ています。

そのため、その図を描くにはいくつかのアルゴリズム (例を含む) が必要です。Webアプリケーションでこの問題を実装する予定なので、できればPHPまたはJavascript（SVG仕様を使用）で。

集合被覆問題のグラフ表示

よろしくお願いします！

4

1 に答える 1

1

私の感覚では、これは遺伝的アルゴリズムが得意とするものだと思います。理由は次のとおりです。

  1. すべてのサブセット境界の合計パス長は、フィットネス関数として使用できます (これを最小化すると、長い細いサブセットを欠く「良い」ソリューションが得られる傾向があります)、この関数は連続的です。
  2. ミューテーション (1 つまたは複数の要素の位置を揺らす) とクロスオーバー (いくつかの要素の位置を入れ替える) を実装するのは簡単なはずです。

適合度関数に関するもう 1 つの重要な提案: 1 つのサブセットの境界がそのセットに属さない要素を囲んでいる解には、大きなペナルティを課します。

私の提案は、サブセットの境界 (または、さらに単純なバウンディング ボックス) の要素の凸包を使用することです。最適な位置が決定されたら、スプラインを使用して周囲を描き、滑らかにすることができます。

于 2010-12-22T10:53:28.380 に答える