問題タブ [graph-theory]

いくつかの単語を入力すると、関連する用語、フレーズ、または概念の多様なセットを返すユーティリティが必要です。注意点は、最初に用語の大きなグラフが必要になることです。そうしないと、この機能はあまり役に立ちません。

たとえば、「野球」を送信すると返されます

Google Setsは、この種の機能を見つけることができる最良の例ですが、パブリック API がないため使用できません (そして、TOS に反対するつもりはありません)。また、単語を 1 つ入力しても、非常に多様な結果が得られるわけではありません。私は、接線で外れる解決策を探しています。

私が実験した最も近い方法は、WikiPedia の APIを使用してカテゴリとバックリンクを検索することですが、これらの結果を「関連性」または「人気」で直接並べ替える方法はありません。それがなければ、提案リストは膨大であちこちにあり、すぐには役に立たず、絞り込むのが非常に困難です.

A Thesaurus を使用することも最小限で済みますが、それでは固有名詞や接線に関連する用語 (上記の結果のいずれか) が除外されます。

オープン サービスがあれば喜んで再利用しますが、十分なものは見つかりませんでした。

私は、これを社内で十分に人口の多い開始セットで実装するか、これを提供する無料サービスを再利用する方法を探しています。

解決策はありますか？ お早めにどうぞ！

更新: 信じられないほど緻密で有益な回答をありがとう。6 か月から 12 か月以内に、皆さんが提案したことを理解できるといいのですが、勝利の答えを選びます =)

マージする必要があるエンティティのクラスに関する複数のデータ ソースを持つデータ ウェアハウスを維持しています。各ソースには自然キーがあり、自然キーごとに常に 1 つだけの代理キーが作成されることが想定されています。特定の自然キーを持つ 1 つのソース システムからの 1 つのレコードが、別の自然キーを持つ別のソース システムからの別のレコードと同じエンティティを表す場合、同じ代理キーが両方に割り当てられます。

つまり、ソース システム A に、ソース システム B の自然キー DEF と同じエンティティを表す自然キー ABC がある場合、両方に同じ代理キーを割り当てます。テーブルは次のようになります。

それが計画でした。ただし、このシステムはしばらく本番環境にあり、代理キーの割り当てがめちゃくちゃです。ソース・システム A は、ある日、ソース・システム B がそれを知る前に、ナチュラル・キー ABC を与えます。DW はそれに代理キー 1 を割り当てました。次に、ソース システム B は、ソース システム A の自然キー ABC と同じものを表す自然キー DEF を与え始めました。DW は、このコンボ サロゲート キー 2 を誤って指定しました。テーブルは次のようになります。

だから倉庫がぐちゃぐちゃ。これよりもはるかに複雑な状況があります。クリーンアップのための短いタイムラインがあり、サロゲート キーから自然キーへのマッピングのクリーンなセットを見つけ出す必要があります。

少しグーグルで調べてみると、これは非二部グラフのマッチング問題としてモデル化できることがわかります。

ウィキペディア - マッチング

MIT 18.433 組み合わせ最適化 - 非二部マッチングに関する講義ノート

Edmond のパス、ツリー、および花のアルゴリズムの (最適なパフォーマンスではない) 理解しやすい実装が必要です。私は正式な数学やコンピュータ サイエンスのバックグラウンドを持っていません。私が持っているのは独学であり、今夜は数学のヘッドスペースにはいません。誰でも助けることができますか？実装に私を導くよく書かれた説明は、深く感謝されます.

編集：

グローバルな適合度を最大化したいので、数学的なアプローチが最適です。貪欲なアプローチ (最初に A のすべてのインスタンスを取得し、次に B、次に C...) を使用すると、局所的な最大値のコーナーに追い込まれます。

いずれにせよ、私はこれをビジネス アナリストに手動で行うようにプッシュしました (2,000 万人全員)。私は、グローバルな試合の質を評価する機能で彼ら​​を支援しています。とにかくサインオフするのは彼らなので、これは理想的です。

代理キーを使用しなくても、一致の問題は変わりません。発見して維持する必要がある 1:1 の自然キー マッピングがまだあります。代理キーはそのための便利なアンカーであり、それ以上のものではありません。

私は、隣接行列として与えられた n-partite (無向) グラフを持っています。たとえば、次のようになります。

このマトリックスに適用できる一連のマトリックス操作があるかどうかを知りたいです。これにより、このグラフのすべてのパス (長さ n、つまりすべてのパーティションを通る) を「リスト」するマトリックスが得られます。上記の例では、パス a->b->d および a->c->d があります。したがって、結果として次のマトリックスを取得したいと思います。

最初のパスにはノード a、b、d が含まれ、2 番目のパスにはノード a、c、d が含まれます。必要に応じて、次のように、結果のマトリックスにすべて 0 の行が含まれる場合があります。

ありがとう！

PS私は推移閉包を計算するためのアルゴリズムを見てきましたが、これらは通常、2つのノード間にパスがあるかどうかのみを示し、どのノードがそのパス上にあるかを直接示しません。

ここでのグラフとは、これらの画像に似たものを意味します。

理想的なソリューションは次のとおりです。

• マネージド コードのみを使用する
• ビットマップ画像への出力を許可する
• WPF 要素への出力を許可する
• ノードのズーム、パン、および再編成をサポートするグラフを表示するためのある種のインタラクティブなサーフェスを含める

また、この種の作業の出発点として使用できる可能性のあるプロジェクトについても興味があります。私が望むものを達成するために何らかの開発が必要な場合は、それに取り組む準備ができています. この目標の最も複雑な部分は、適切な時間枠内でグラフ レイアウトを取得することのようです。

DAG を「反転」(反転?裏返し?)するアルゴリズムを探しています。

私が使用している表現は、真に不変の DAG です (「親」ポインターはありません)。同等のノードを使用して「鏡像」グラフを作成しながら、何らかの方法でグラフをトラバースしたいのですが、ノード間の関係の方向が逆になっています。

したがって、入力は一連の「ルート」(ここでは {A}) です。出力は、結果グラフの「ルート」のセットである必要があります: {G, F}。(ルートとは、着信参照のないノードを意味します。リーフは、発信参照のないノードです。)

入力のルートは出力のリーフになり、その逆も同様です。変換はそれ自体の逆でなければなりません。

(興味深いことに、構造クエリ用の XML を表現するために使用しているライブラリに機能を追加したいと思います。これにより、最初のツリーの各ノードを 2 番目のツリーの「ミラー イメージ」にマップできます (また、元に戻すことができます)。繰り返します) クエリ ルールのナビゲーションの柔軟性を高めるためです)。

問題があります：

私はクラス A とクラス B を持っています。これらのインスタンス オブジェクトは、さまざまな量で互いに似ているか異なっているかをプログラムで調べることができます。たとえば、それらは完全に一致する場合もあれば、まったく異なる場合もあります (クラスが異なっていても、同じ情報を表し、同じスコアを付けることができます)。

ここで、A の 1 つと B の 1 つの 2 つのコレクションがある場合、A と B をペアにして、どちらかのコレクションが他のコレクションよりも大きいか、 As または B の一部が単純に一致するにはあまりにも異なる場合は?

私の最初の試みは、2 次元配列を作成することでした。各セルは一致の「スコア」 (0 = パーフェクト、数値が大きいほど悪い) であり、すべてのパスを再帰的に繰り返し、累積スコアが最も低いものを探します。これは機能し、結果は完璧ですが、非常に遅いです。

より効率的なアルゴリズムに関するアイデアはありますか?

ご参考までに、私の A クラスはオーディオ ミキサーの入力チャネルを表し、B は同じ (シーンと呼ばれる) 持続状態を表します。私が解決しようとしている問題は、既存のミキサーにシーンをインポートする方法です。この場合、シーン (B) は、既存のチャンネル (A) とわずかに、または大きく異なる場合があります。どちらかを少し変更して一致させることができれば、チャネル (A) を追加したくありません。たとえば、A にエフェクト インサートを追加して、B と完全に一致させ、別の A を追加する必要がないようにすることができます。

マイク

Splay tree、Red-black tree、AVL tree、B-tree、T-treeとは?

私は良い実装を探しています。

対応するadjMat[i、j] = 1に1を含めることにより、ノード間のエッジを追跡するグラフの隣接行列があります。この隣接行列を通して、グラフに存在する長さ4のすべての閉じたパスを見つけたいと思います。誰かが私に擬似コードを提供してくれませんか。ありがとう