1

文字列の二分探索木がどのように機能するのかという質問がありました。新しいデータが親データより小さいかどうかをチェックし、小さい場合は左に、大きい場合は右に分岐することにより、整数の二分探索木を知っており、実装しました。ただし、これを文字列のノードで実装する方法について少し混乱しています。

整数または文字を使用して、プログラムしたツリーの挿入メソッドに配列を挿入するだけで、ツリー ノードが正しく構築されます。私の質問は、これを文字列の配列でどのように処理するかです。ツリー内で文字列を正しく分岐させるにはどうすればよいでしょうか? たとえば、一連の質問があった場合、どうすれば BST を正しく分岐できるので、最終的に正しい答えにたどり着くことができるでしょうか。

たとえば、次の自明なツリーの例を見てください。

                                        land animal?            
                   have tentacles?------------^-------------indoor animal
          have claws?-----^----jellyfish    live in jungle?----^----does it bark?      
eat plankton?----^----lobster             bear----^----lion        cat----^----dog
shark----^----whale

ノードが必要な場所に配置されるように、このようなツリーをどのように配置しますか。トラブルシューティングのために BST を作成しようとしていますが、正しい位置に表示されるように文字列のノードを設定する方法がわかりません。ノードをハードコーディングする必要がありますか?

4

1 に答える 1

1

二分決定木を構築する更新 2 :

バイナリ デシジョン ツリーは、葉ノードのファセットに関するブール値の応答を生成する一連の質問と考えることができます。つまり、特定のノード/エッジのすべての子孫に対して、「この質問/回答は成り立つ」(回答は「真」または「偽」) と言えなければなりません。たとえば、樹皮は (通常の) 犬の一面ですが、触手はクジラの一面ではありません。提示されたツリーでは、偽のエッジは常に左のサブツリーにつながります。これは、各エッジに真/偽または Y/N のラベルを付けることを避けるための規則です。

ツリーは、すべての動物の各質問に答えることができる既存/外部の知識からのみ構築できます。

このようなツリーを構築するために使用できる大まかなアルゴリズムを次に示します。

  1. 考えられる動物のセットから始めて、これを A と呼び、一連の質問を Q と呼びます。
  2. count(True(q, a in A)) が count(False(q, a in A)) の質問に最も近い Q から質問 q を選択します。結果のツリーがバランスの取れたバイナリ ツリーである場合、これらのカウントは質問するのに最適な質問は常に等しくなります。
  3. Q から q を削除し、現在のノードを尋ねる質問として使用します。すべての False(q,a) を左の子ノードで使用できる動物のセット (A') に入れ、すべての True(q,a) を右の子ノードで使用できる動物のセット (A'') に入れます。
  4. 各エッジ/ブランチ (false = 左、true = 右) に続いて、残りの Q から適切な質問を選び、繰り返します (A には A' または A'' を適宜使用)。

(もちろん、コース教材やホワイトペーパーとしてオンラインで見つけられる、より多くの完全/詳細/正確なリソースがあります。ほとんどの大学キャンパスでの適切な書籍の選択は言うまでもありません..)

[バイナリ]決定木の更新:

この特定のケース (追加された図で明らか) では、グラフは、ノード間のエッジを表す質問に対する「はい」または「いいえ」の応答に基づいています。つまり、文字列値自体の順序付けを使用してツリーが構築されるわけではありません。この場合、非バイナリ応答が許可されている場合、各ノードはより多くのエッジ/子を持つことができますが、常に左ブランチを「偽」、右ブランチを「真」にすることは理にかなっています。

デシジョン ツリーは「トレーニング済み」でなければなりません (Google 検索)。つまり、ノード間の順序付けのみに基づく BST とは異なり、最初に質問/応答に基づいてグラフを作成する必要があります。エッジは固有の順序付けに従っていないため、最初のグラフ構築は単に一連の質問から行うことはできません。

二分探索木に対する初期応答:

整数の場合と同じ方法: アルゴリズムは変更されません。

compareTo(a,b)a < b、a == b、および a > b に対してそれぞれ -1、0、または 1 を返す関数を考えてみましょう。

次に、このコントラクトを使用して関数を実装するときに、そのような型が順序付けをサポートしている場合、a と b のどちらの型も (それらが同じである限り) 重要ではないことを考慮してください。整数の場合は「生」であり、ホスト言語の対応する文字列比較を使用します。文字列型の場合。

于 2013-03-17T18:52:16.370 に答える