問題タブ [bipartite]

クエリと関連するクリックされた URL の 2 部グラフがあります。これらのクエリに基づいて、クエリをクラスター化します。2 つのクエリが同じかどうかを判断するために、単純なセット ベースの式を使用する予定です。私の初期入力データは次の形式です。

この問題を解決するための適切なアルゴリズムを決定するのに苦労しています。

どんな助けにも感謝します。

現在、深さ優先検索 (最大 10 レベル) を実行して、2 部グラフで長さ $n$ のパスの数を数えています。ただし、これを実装すると、3000 個以上の要素を持つ 2 部グラフから長さ 5 の 700 万個のパスをカウントするのに 5 分以上かかります。このカウントの問題をより効率的に行う方法を探しています。文献にそのようなアルゴリズムがあるかどうか疑問に思っています。

これらは無向 2 部グラフであるため、パスにサイクルが存在する可能性があります。

ここでの私の目標は、1 分以内に 100 万要素の 2 部グラフで長さ $n$ のパスの数を数えることです。

提案された回答を事前にありがとうございます。

切断された二部無向グラフがあります。グラフを完全に切り離したい。私が実行できる唯一の操作は、ノードの削除です。ノードを削除すると、そのエッジが自動的に削除されます。タスクは、削除するノードの数を最小限に抑えることです。グラフの各ノードには最大 4 つのエッジがあります。

グラフを完全に切り離すということは、リンクを介して 2 つのノードを接続してはならないということです。基本的に空のエッジ セットです。

学級試験で問題が出題されました。ある図書館では、各メンバーが 4 冊の本をリクエストし、各本は 2 人のメンバーのみによってリクエストされました。この情報は、二部グラフ G = ( X + Y , E ) の形式で与えられます。

X : すべてのメンバーのセット Y : すべてのブックのセット エッジ E = エッジのセット (x,y) ここで、x はブック y に対して要求されたメンバーです。私たちは、司書が各メンバーに最大 2 冊の本を与えて、最大のメンバーが満足できるようにする方法を見つけなければなりません。

私は2つのアプローチを思い付きました：

1. 2 つの新しい頂点 s(ソース) と t(デスティネーション) を導入します。s から X のすべてのメンバーに容量 2 でエッジを導入します。すべてのエッジ E は容量 1 を持ち、新しいエッジ Y から t は容量 1 を持ちます。ここで最大フロー アルゴリズムを適用して、最大の一致を見つけます。最大マッチングが必要なソリューションです。
2. もう 1 つの方法は、同じエッジを導入することによって上記と同じアルゴリズムに従うことですが、各エッジの容量は 1 です。次に、最大一致を見つけます。このマッチングは、最大会員数に1冊の本をプレゼントします。一致した書籍を削除し、上記のアルゴリズムを再度適用します。一致した本と 2 冊の本を持っているメンバーを再度削除し、X と Y の間にエッジがなくなるまでアルゴリズムを適用します。達成されたソリューションは、必要なソリューションです。

アルゴリズムを超えましたが、どちらが正しいか、どれも正しくないかわかりません。他のアルゴリズムがある場合は、ここで提案してください。

私はアルゴリズムを見つけたようですが、それを理解するのに苦労しています.アルゴリズムの一般的な概要を知っている人がいるかどうか疑問に思っていました.

2ページで見つけたアルゴリズムへのリンクは次のとおりです

http://www.cse.iitb.ac.in/~sundar/cs435/lecture23.pdf

二部グラフで設定された最大の独立頂点を見つけるための総当たりアルゴリズムの一般的な概要を知っている人はいますか?

MIS を見つけるためのケーニッヒの定理など、他のアルゴリズムがあることは知っていますが、ブルート フォース方式の疑似コードはどうなるのだろうと思っていました。

さらに、そのようなブルー​​ト フォース アルゴリズムの実行時の複雑さはどれくらいになるでしょうか?

vectors2つのAでマッチング問題を解いていますclass

これは私が実装しようとしているアルゴリズムです:

大まかなマッチングでは、 、 、 、および と一致する場合、および一致しleft[i]ないものにはメンバーがあり、right[j]left[i].n = jleft[i].match ='M'right[j].n = iright[j].match = 'M'n = -1match = 'U'

拡張パスを見つけている間、別の (i, j) に 1 つ存在する場合、一致しmatchないもののメンバーを から'M'に'U' 変更n = -1 し、拡張パスと一致する 2 つのメンバーmatchを 'A' に変更します。nインデックスに応じたメンバー。

これがこれを解決するための正しいアプローチであるかどうかはわかりません。これは最大一致の最初の試みであり、オンラインで多くの記事を読み、チュートリアルを見てきましたが、「コード」を適切に機能させることができません。

コードは必要ありません。コードを書くことができます。このアルゴリズムを段階的に理解したいだけです。上記で試したようなアルゴリズムを誰かが教えてくれたら、ありがたいです。また、それ以来間違った方向に進んでいる場合は、修正してください。

次のデータフレームがあります。

ここで、X1は個人番号であり、X2はその個人が属するグループです。1人が異なるグループに属することができます。今、私は各人から彼が属する各グループに線を引きたいと思います。私はそれをこのplot()ように解決しました：

結果は次のようになります。

今、ggplot2でこれをどのように行うことができるのだろうか？

ご協力いただきありがとうございます！

二部グラフG = ( U , V , E ) が与えられた場合、 Gの連結成分の 1 つの「側」であるVのすべての (最大) サブセットを見つけたいと考えています。

たとえば、入射行列の場合

ここで、行インデックスはUを表し、列インデックスはVを表し、出力はセット {0, 1, 5}、{2, 4}、および {3} になります。

これは標準的な問題と同等ですか? もっと言えば、効率的な解決策はありますか?

ユーザーが選択した小売製品のバスケットを 1 つ以上の有効なプロモーションに一致させる従来のシステムを再開発しています。これらのプロモーションは、業界標準の BOGOF (1 つ購入すると 1 つ無料)、2 つ購入すると 3 つ目が無料になる、製品 X と Y を購入すると 10% オフになる、などです。これらのプロモーションを満たすもの。

注文時に単一の製品を照合する従来の方法とは対照的に、小売商品のバスケット全体を取得して 1 回の操作で分析するソリューションが必要です。(現在の解決策は望ましくない制限につながります)

各プロモーションには、プロモーションをトリガーするために存在する必要がある一連の適格な製品があります。これらは n 個のセット (または位置) に配置されます。たとえば、次のようになります。

アイテムが同じセットに複数回登場する場合を除き、各プロモーションには、存在する各グループから 1 つの製品を含める必要があります。プロモーションには、製品の「セット」を無制限に (通常は 10 未満) 含めることができます。

簡単な例として、 のショッピング バスケットがItem 1, Item 4 and Item 6プロモーションをトリガーし、同様に のバスケットもプロモーションをItem 1, Item 1 and Item 2トリガーします。Item 1, Item 2 and Item 3しかし、各セットが満たされていないので、バスケットはそうではありません。

プロモーションがいつトリガーされたかを検出する最善の方法に関する明白な質問は別として、価格設定などの詳細を処理するために、アイテムが一致したセット (位置) を回復する必要もあります。それも望ましいでしょう。プロモーションに割り当てる際に、より高価な (通貨換算で) アイテムがより安価な (同等に一致する) アイテムよりも優先される場合。

次の部分が解決策に役立つことを願っています。不要なノイズが発生するほど不明瞭な音ではありません。無視してかまいません。

これまでの私の最善の解決策は、このアイテムが満足するプロモーション セット (位置) を保持する「ショッピング バスケット」内の各小売アイテムに対して新しいセットを作成することです。すなわち。

次に、このセットのリストに各ポジションに固有のアイテムが含まれていること、および各プロモーションポジションが満たされていることを「確認」するというのが私の理論です。これまでのところ、私の作業例はすべて、ブルートフォース、ループ、または再帰を使用して、セットのすべての組み合わせ (上記) を生成し、一意の組み合わせがあるかどうかを確認しようとしています。これはスケーリングが非常に悪く、非常に些細な例以外では、現実の世界ではまったく機能しません。(この関数は、アイテムがバスケットに追加されるとリアルタイムで呼び出されるため、高速である必要があります)

多くの研究は、二部マッチングが望ましい結果を生み出すことを示唆していますが、私は研究記事と、この主題に関するかなり複雑な数学的テキストしか見つけることができません. いくつかの疑似コードまたは基本的なロジックは素晴らしいでしょう。

私の2つの質問は基本的に次のとおりです。

1) 顧客バスケットを分析してマッチング プロモーションを作成するための、より優れた/より迅速な/簡単な方法を知っている人はいますか?
2) アイテムを関連する位置に一致させる最も効率的な方法を特定したと仮定すると、プロモーションに対して記録する小売アイテムのリストを決定する最も安価な方法は何ですか.

トンネルの終わりに光が見えなくなったので、どんな支援もありがたく受け取られます! (最終的なソリューションは .NET であり、SQL Server 2008 R2 を使用します。)