2

サブグラフのセットがあり、それらが抽出されたグラフでそれらを一致させる必要があります。また、各サブグラフがそのようなグラフに表示される回数を数える必要があります（可能なすべての一致を保存する必要があります）。サブグラフとグラフの両方のエッジのラベルを考慮すると、完全に一致する必要がありますが、頂点のラベルは互いに一致する必要はありません。JUNG APIを使用してシステムを構築したので、JUNGが提供するグラフ構造を処理できるソリューション（API、アルゴリズムなど）が必要です。何かご意見は？

4

2 に答える 2

0

JUNGは非常にフル機能であるため、必要なものに対するJUNGのグラフ分析アルゴリズムがない場合は、通常、強力で理論的な理由があります。私には、あなたの問題は、NP完全であるサブグラフ同型問題のインスタンスのように聞こえます。

http://en.wikipedia.org/wiki/Subgraph_isomorphism_problem

NP完全性はあなたに馴染みがあるかもしれませんし、そうでないかもしれません（私がそれを理解するのに7年の大学とコンピュータサイエンスの修士号を要しました！）ので、ここで高レベルの説明をします。ソートなどの特定の問題は、入力サイズに関して多項式時間で解決できます。たとえば、N個の要素のリストがある場合、それをO（N log（N）） 時間。より具体的には、多項式時間で問題を解くことができれば、考えられるすべての解を尽くすことなく問題を解くことができるということです。並べ替えの場合、リストのすべての可能な順列をトラバースでき、並べ替えられたリストの順列が見つかった場合は、それを返します。しかし、これは明らかに問題を解決するための最速の方法ではありません！非常に賢い数学者の中には、理論上の最小値であるO（ N log（N ））まで下げることができたため、今日のコンピューターを使用して、非常に大きなリストをすばやく並べ替えることができます。

反対に、NP完全問題には多項式時間解がないと考えられています（証拠はこれが事実であることを強く示唆していますが、誰もそれを証明したことがないためだと思います）。とにかく、これが意味することは、最初にすべての可能な解決策を使い果たすことなしに、NP完全問題を明確に解決することはできないということです。NP完全問題の時間計算量は常にO（c ^ N）以下であり、cは1より大きい定数です。これは、問題のサイズが大きくなるたびに、問題の解決に必要な時間が指数関数的に増加することを意味します。

それで、これは私の問題と何の関係がありますか？

ここで私が得ているのは、サブグラフ同型問題がNP完全である場合、あるグラフが別のグラフのサブグラフであるかどうかを判断できる唯一の方法は、考えられるすべての解を使い果たすことです。したがって、これを解決することはできますが、おそらく数ノード程度のグラフまでです（グラフのサイズが大きくなるたびに、問題の時間計算量が指数関数的に増大するため）。これは、特定のグラフサイズに達するとすぐに、解決策を見つけるのに文字通り永遠にかかるため、問題の解決策を計算することは計算上実行不可能であることを意味します。

より実際的には、上司がNP完全であることが証明できる何かをするようにあなたに頼んだ場合、あなたはそれが不可能であると単純に言うことができ、彼はあなたに耳を傾ける必要があります。教授からNP完全であることが証明できることをするように求められた場合は、それがNP完全であることを教授に示してください。そうすれば、コースのAが得られる可能性があります。NP完全問題を自分でやろうとしている場合は、次のプロジェクトに進む方がよいでしょう...;）

于 2012-03-23T23:34:50.340 に答える
0

さて、私はそれを最初から実装することによって問題を解決しなければなりませんでした。トピック「VF2アルゴリズムの実用的な例はありますか？」で提案されている戦略に従いました。。したがって、誰かがこの問題についても疑問がある場合は、前述のトピックのRichApodacaの回答を確認することをお勧めします。

于 2012-03-27T20:36:06.060 に答える