すべての組み合わせツリーアルゴリズム

Question

私は木に関係する質問があります。私は「車」のような話題について約100の文章を持っています。それらの文章は基本的に車について語ります。ユーザーがクエリを送信した場合：「単語「エンジン」と「オイル」の間の単語リンクのすべての組み合わせを検索します。」私は可能なすべての単語のリンクを見つけることができますように "エンジン"と "オイル"は、文章内の任意の数の類似した単語で接続します。

たとえば、

1. 実行時にエンジンが暑いです。
2. 車にエンジンがあります。
3. 車はオイルを使用します。

この場合、答えはエンジン - >車 - >オイル（3つの単語の組み合わせ）です。そして、私は最終的に "エンジン"と "オイル"がお互いにつながるようにすべての組み合わせを見つけたいと思っています。これは最短パスでも最長パスでもなく、あらゆる方向と言葉で実行可能なすべてのパスです。パスが似ていない限り、「エンジン」と「オイル」に到達するために1,000語の組み合わせを持つことも可能です。

これを行う方法はありますか？私はパンを最初に使ってみましたが、少し難解です。たとえば組み合わせが可能です。

1. エンジン - >カルボ>ラン> stop->オイル
2. エンジン - >カルボ>オイル
3. エンジン - >急速> brake->オイル

缶誰これで私を助けてください。ここでの論理とアイデアは何ですか？私はすでに訪れた言葉を無視することはできません。なぜなら、それはアルゴリズムを停止させ、すべてのリンクを私に与えないからです。

助けてください。

ありがとうございました。

fa323

Answer 1

あなたの質問はそれもあなたの例では、ある...ので、不足のある答えはengine->an->oilが含まれていない理由、それは不明です。

また、実際にはツリーとは関係なく、グラフを扱います。

まず、グラフの作成方法を決定する必要があります。これを行う合理的な方法は、両方が特定の文に現れる場合には、2つの単語の間にエッジを置くことです。

次に、出力する内容を決定する必要があります。私はあなたがすべての道を望むことを非常に疑う。どうして？まあ、私が説明したグラフを作成すると、最初の文章だけを使っても、エンジンからオイルまでの経路はサイクル数でカウントされません。しかし、それがあなたがとにかく欲しいなら、グラフ内のすべての非周期パスを深さ優先探索で見つけることができます。そこでは、ノードをスタックに押したときに訪れたノードをマークし、離したときにマークを外します。