5

人々のグループ[たとえば1874人]がいて、全員が世界のさまざまな会社[たとえば236人]を代表しています。私の仕事は、一人一人がどの会社で働いているかを最もよく特定することです。秘訣は、「どこで働いているのか」と単純に聞いて答えを出すことはできないということですが、私が持っているのは、いくつかの質問（たとえば290の質問）と従業員に期待すべき正確な回答を含む質問票です。各社の 答えが同じ会社もあるので、最終的には、どの会社に勤めているのか正確にわからなくても、絞り込んで、その会社に勤めなければならないと言うことができるはずです。

複数の値のマップと他のいくつかのデータ構造を使用して、1つの質問[クエリ]で識別できるすべての会社を特定するところまで行きました。これらのクエリを使用してツリーデータ構造のルートを表すには、他のクエリ/質問をブランチとして使用して残りのツリーを構築し、残りを識別する必要があります。

アドバイス/ヘルプ/提案はありますか？

4

3 に答える 3

2

コメントでの回答に基づいて、ツリーの各レベルで質問を表し、そのレベルのノードのブランチ/サブノードで回答を表すこともできます。btillyが述べたように、これは技術的にはトライになります。

より効率的な（必ずしもスペース単位ではありませんが）ソリューションには、ハッシュテーブルと、回答の選択肢に基づいてハッシュを作成するハッシュ関数を使用することが含まれる可能性がありますが、要件とドンを考えると、トライが最善の方法だと思います't-cares。

ああ、そうです。回答の選択肢がどのように配置されているかに応じて、いくつかのレベルのサブブランチ/ツリーがない特定のブランチに一連の回答がある可能性があります。このような場合、これらの単一の分岐セクションを個々のノードに折りたたむ可能性があります。http://en.wikipedia.org/wiki/Trie#Compressing_triesもいくつかのヒントを提供する場合があります。

私の最初の答えに対するあなたの回答に基づいて、ここに私の考えがあります：

質問とその回答の選択肢のノードの配列を保持します。各回答の選択肢はハッシュテーブル（または使用したいデータ構造）に関連付けられています。Pythonを頻繁に使用し、 Pythonのsetデータ構造（ハッシュテーブルの一種として実装されます）には、各企業へのポインター、または特定の質問に対する特定の回答が最初に企業を示す場合は単一の企業へのポインターが含まれます。

特定の質問に対する回答を初めて確認し、その回答の選択肢に複数の会社が関連付けられている場合は、その最初の回答のハッシュテーブルのデータをリンクリストなどとして一時的にコピーします。さらに多くの質問に回答したら、リストの要素を新しい回答ごとのハッシュテーブルと照合し、新しい回答ごとのハッシュテーブルに存在しない会社をリストから削除します。1）リストに1つの会社だけが残っている、2）リストに会社が残っていない、または3）すべての質問をするまで、質問のプロセスを繰り返します。

1）の場合、それは質問回答者の雇用主です。
2）の場合、従業員はどの会社にもチェックのために雇用されていないか、どこかにエラーがあります。
3）の場合、リンクリストに残っている企業は、質問回答者が雇用されている可能性のある企業です。

私の実装では最低580個のハッシュテーブル（回答ごとに1つ、質問ごとに最低2つの回答）が必要になるため、これを行うにはおそらくより効率的な方法がありますが、現時点では何も考えられません。

于 2011-06-14T13:53:25.280 に答える
2

ルートから始めて、再帰的にツリーを構築します。各ステップで、アクティブな一連の質問票が作成されます。これは、最初はすべての質問票になります。アクティブなアンケートから、「はい」と「いいえ」の回答がほぼ同じ数の質問を選択します。この質問のツリーノードを作成します。このノードで選択した質問に対して「はい」と答えたサブセット質問票を使用して、「はい」サブツリーを（再帰的に）作成します。また、選択した質問に対して「いいえ」と答えた質問票のサブセットを使用して、「いいえ」サブツリーを作成します。

簡単な例：

動物を推測しようとしていて、クマ、シマウマ、サーモン、ワニからの質問票があるとします。

アンケートを見ると、約半数が「ほ乳類ですか？」と答えているので、それを木の根にします。

ここで、その質問に「はい」と答えた質問票だけを取り上げます。私たちの例では、それらはクマとシマウマからのものです。「縞模様はありますか？」という質問を選択します。これは、それらの約半分が「はい」、半分が「いいえ」と答えているためです。これらの回答ごとに質問票が1つしかないため、シマウマを推測して適切に耐えるリーフノードを作成します。

ここで、ルートノードに戻り、「no」ブランチに対してプロセスを繰り返します。つまり、鮭とワニの質問票を見て、それらを別々のグループに区別する質問を選択します。「あなたは笑顔が好きですか？」法案に適合します。

最終的なツリーは次のようになります。

Ask: "Are you a mammal?"
 |
 +- yes -> Ask: "Do you have stripes?"
 |          |
 |          +- yes -> Guess: Zebra
 |          |
 |          +- no --> Guess: Bear
 |
 +- no --> Ask: "Do you like to smile?"
            |
            +- yes -> Guess: Crocodile
            |
            +- no --> Guess: Salmon
于 2011-06-14T16:35:28.763 に答える
0

Prologを使用してエキスパートシステムを構築することは、 1つの可能な解決策です。このオプションを検討しましたか？

そうすることで、ユーザーとの対話を容易にする自然言語処理機能を追加することもできます。

于 2011-12-10T16:44:47.057 に答える