ええ、それはとてもいい問題ですが、そこでいくつかのとてもいいトリックを行うことができます。行と列の数が頂点の数である0の正方行列としてグラフを表示できます。1それぞれ1が、行の頂点から列の頂点へのエッジを示します。次に、すべての可能なグラフは、N^2 ビットの 1 つの大きな 2 進数です。つまり、N 個の頂点から作成された 2^(N^2) の可能なグラフがあります。これで、問題を 2 つの部分に分割できます。
- 可能なすべてのグラフを生成します
S- 各グラフは 1 つの N^2 ビット数です。
- 次に、このグラフごとに、行列を行と列で展開し、各行と列で正確に 1で
Vある組み合わせで可能性を乗算します。1V
1 つ説明が必要です。あなたが書いた... からの各頂点Sは、任意の数のインエッジとアウトエッジを持つことができます0 は任意の数に含まれますか? 次に、結果にConstrainとの間のすべての頂点が正確に含まれている必要があることをVS理解していません。それぞれがゼロのインエッジとアウトエッジを持つ頂点として各ソリューションに含まれてSいるため、意味がありません。それ以外の場合は、すべての N^2 ビット数ではなく、各行と列にS少なくとも 1 つあるものだけであり、問題を 2 つの部分に分割することはできず、一緒に解決する必要があります。次に、最初に行と列を満たす方が簡単かもしれません(ちょうど 1 つ)1SVV1行と列で）、次に、この各解を、行と列に少なくとも 1 つ必要な場合に制約を満たすSxS行列の解で乗算します。S1
少数の頂点のリストのリストとして、さまざまな表現を試すことができます。arrayインデックスを計算するときにモジュールを試すR+C*Nか、配列の配列を試すことができます。頂点の数が多い場合は、バイナリの配列を使用して実行できます。digraphここでモジュールを試すこともできます。同様のアプローチは、Perl で完全なクロージャー グラフを生成するのにうまく機能しましたvec。しかし、それは非常に異なる問題であるため、ここでは当てはまらないようです。より最適化されたプレゼンテーションが見つかるかもしれませんが、Erlang がこの種の計算を非常に効率的に行うための最良のツールであるとは思えません。とにかく、ここでは可能性の数がかなり急速に増加しています O(2^(N^2)) ので、大きな行列の効率的なストレージについて心配する必要はありません;-)
編集：
この観点から問題を見てください。10 個の頂点があり、それが空であるVと仮定した場合。S次に、10!可能なグラフ、つまり 3628800 がSあります。その場合、約2^1001.2677e+30 グラフ (1 秒あたり 1e+09 グラフを生成する場合は 4.0197e+13 年) になります。これは、頂点の数が非常に少ない場合、可能なグラフの数が非常に多くなることを意味します。ここでの最大の問題は、それらをどうするかということです。それらを保管することはできませんが、保管する場合は非常に効率的に保管する必要があります。Binary フィールドは、 から作成されたグラフを格納するための最も効率的な方法ですS。頂点を持つエッジのより効率的な方法を見つけることができますV。配列またはリストとして保存します。ここで、位置はエッジの始点である頂点であり、値はエッジの終点である頂点です。
したがって、ソリューションは、結果をどうするかによって大きく異なります。非常に多数のグラフで何をするか想像できないため、何らかの方法で結果を除外すると思います;-)私のアドバイスは、グラフ生成中にできるだけ早く意味のあるグラフを除外することです。これは、アルゴリズムの生成に結果のフィルタリングを含めることができるようにするには、目的によってアプローチを決定する必要があることを意味します。
そして、この問題に対する Erlang の効率について言えば、膨大な数のエンティティ (考えられるグラフ) を扱う場合、メモリと CPU の使用を非常に慎重に管理する必要があります。Erlang を使用できますが、時間が重要な部分については、NIF で C を使用する必要があります。また、リストやタプルの代わりに、よりメモリに優しいデータ構造をバイナリまたはビッグナムとして使用する必要があります。また、C、C++、OCaml、Haskell などの他の言語を見つけることもできます。このようなメモリと計算を多用するタスクにより適しています。