順序付けられていないツリーパターンマッチングアルゴリズム

Question

私は、合理的なアルゴリズムを見つけようとしています。 some researchによると、この問題はNP完全です。私はすべてのパターンマッチを見つける必要はありません、私はちょうど存在するパターンマッチングを見つける必要があります。好ましくは、ツリー上で「削除」を実行する必要はありません（ノードを削除するコピーを作成する必要はありません）。

もう1つ注目すべきことは、ツリーがツリー照合クエリ間で更新されることです。この事実を利用するアルゴリズムが存在する可能性もあります。これは、以前の部分的な将来のマッチを最適化するためにツリー内で一致します。

私が言及した基準でこの問題を解決できる簡単なアルゴリズムはありますか？純粋な単純なブルートフォースアプローチよりもまだ優れていますか？

注：私の問題はthis previously asked questionと似ていますが、その問題は順序付けられたツリーに固有です。

Answer 1

http://www.sciencedirect.com/science/article/pii/S1570866704000644によると、NP完了の問題はツリーの包含です。これは、ツリーが潜在的にスキップする世代に収まることを意味します。たとえば、1つのルートと1000の葉を持つツリーは、2つの10xで分岐するツリーに収まる可能性があります。この問題はNP完全であるため、木が成長するにつれて根本的に優れた指数関数的な成長はできません。

しかし、あなたはその指数を減らすことができますし、強引な力よりもはるかに優れています。たとえば、ツリー内の各ノードについて、その下の最大深度と子孫の総数を記録します。あるツリーをもう一方のツリーに収めようとするときに、深さが深すぎたり子どもが多す​​ぎるサブツリーに収まるようにしようとすると、検索が停止します。これにより、多くの紛失原因を避けることができます。

また、動的プログラミングを使用して支援することもできます。あなたがしようとしているのは、1つ下のサブツリーを他のツリーにマップできるかどうかにかかわらず、2つのツリーからノードの各ペアを格納することです。 aがbに行くことができるかどうかを調べるときは、先ずaの子どもをbの子供に割り当てます。もし行けない人がいるなら、その答えは「いいえ」であることを知っています。すべてが行くことができる場合は、aの子を少なくとも最も多くの場所に合わせて並べ替えます。今度は、一方を他方に合わせる方法を強引に探します。検索を整理するこの方法で、あなたの死んだ終わりを非常に迅速に見つける傾向があります。

しかし、もし木が大きければ、それが他のものに収まらない場合は、その事実を理解する非常に、非常に長い時間を費やすことができます。