問題タブ [bipartite]

次の問題に直面しました。

• 互いに素な集合が 2 つありA、B
• 要素の各ペア ( a, b) ( aset に属し、 setAにb属するB) の確率pijは事前にわかっています。aこれは、 と一致する確率 (確実性レベル)、bつまり、どの程度a一致するか (および==bであるため、その逆も同様) を表します。pijpji
• 確率/確実性が最も高いマッチングを見つけ、マッチングを説明するペア ( a、b) を見つける必要があります。
• すべての要素は、他のセットの別の要素と1回だけ一致/ペアにする必要があります（標準の2部一致問題のように）
• 可能であれば、得られたマッチングの不確実性レベルを近似的に表す数値を計算したいと思います (0 はランダムな推測を表し、1 は確実性を表すとしましょう)。

そのようなアルゴリズムが必要とされる簡単な実用的な例を以下に示します (これは実際に私が解決しようとしている問題ではありません!):

• 2 人が紙に a ～ z の文字を書くように求められる
• 文字 ( a, ) の各ペアに対して、パターン マッチャーを実行して、人によって書かれた文字が人によって書かれた文字を表すb確率を決定します。これにより、文字の各ペア ( , )に対するある種の類似性相関を表す確率行列が得られます。aAbBab
• その人が書いた各文字について、その人Aが書いた対応する文字を見つける必要がありますB

現在のアプローチ:セットの要素がaセットの要素とA一致する確実性レベル/確率の対数に比例する重みを割り当ててから、最大加重二部マッチングを実行して最大合計を見つけること ができるかどうか疑問に思っています。対数は、複数の一致の合計確率を最大化したいためであり、単一の一致 (一致した要素のペアとして表される-bBab) 確率の積である一連のイベントを形成します。対数を取ることにより、これを確率の合計に変換します。これは、ハンガリーのアルゴリズムなどの加重二部マッチングのアルゴリズムを使用して簡単に最大化されます。しかし、私は、このアプローチが統計上の期待最大値の点で最良のマッチングを保証するとはどういうわけか疑問に思っています。

少し検索した後、私が見つけた最も近い問題は、NP困難である2段階の確率的最大加重マッチング問題でしたが、実際にはある種の「1段階」の確率的最大加重マッチング問題が必要です。

任意の数の NSArray オブジェクトを受け取り、その配列のメンバーのすべての可能な完全な組み合わせのネストされた配列を返すメソッドを作成しようとしています。

この質問への回答で言われたように、2 部グラフ、より正確には完全な 2 部グラフを作成しようとしています。

たとえば、2 つの配列があるとします。

これらの配列の配列を取るメソッドが必要です。

同じ長さのすべての可能な組み合わせの配列を返しました。したがって、この例では、大まかに次のような配列が必要です。

これらの配列内のオブジェクトの数が増えるにつれて、結果の数も指数関数的に増加すると思います。おそらく、このメソッドを NSArray のカテゴリにするでしょう。また、結果がすべて同じ長さになるようにしたいと思います。つまり、ソース配列が 3 つある場合、メソッドによって返されるネストされた各配列の長さは 3 でなければなりません。

これを行うための最もエレガントな方法のアイデアはありますか?

私が書いている作図ソフトウェアで発生した問題を (効率的に) 解決するためのアルゴリズムが必要です。

N と M の 2 つのノードのセットがあります。N の各ノード n0 には、M の一意の (n0 の) ノードへの 0 から M の接続があります。これらのノードのセットは、N 個のノードを持つ 2 本の平行な水平線上に配置されます。 M ノードの上の行にあります。接続は、N から M への直線として描画されます。

私がする必要があるのは、交差を最小限に抑えるために、水平線内で N ノードと M ノードを再配置することです。O（N！* M！）であるすべての可能な配置を単純に列挙するよりも効率的なこれを行う方法はありますか？（実際には、各接続も交差をチェックする必要があるため、それよりもかなり悪いです）。

関連する文献への参照も歓迎しますが、その関連性が望まれる理由についての説明が必要です。

指摘したように、一般的なケースでは、これは 2 部グラフ (セット N および M) の平面化アルゴリズムと見なすことができます。ただし、この特定の問題はそれよりもかなり制限されており (高速化できることを願っています)、次のように追加情報を生成する必要があります (低速化する可能性があります)。

1. ダイアグラムの制限は、接続が N から M への直線として描かれなければならないことです。グラフ理論では、これは事実上、接続がN または M のノードの後ろに行くことはできず、それらの間のみに行くことを意味します。したがって、4 つのコネクタを持つ 2x2 のケースは、一般的な 2 部グラフのケースでは平坦化できますが、私の図の場合は平坦化できません。

2. 追加情報は、平面化できない場合でも、最小交差ソリューション (またはそれに近いソリューション) が必要であるということです。一般に、最小交差アルゴリズムは、平面化のみのアルゴリズムとは大きく異なります。

グラフに複数のコンポーネントがある場合、最大の二部一致をどのように見つけますか? 各コンポーネントは 2 つの方法で色付けできます。最大一致ルーチンを実行するために、2 つのセット X と Y をどのように決定しますか?

多くの個別のコンポーネントを含むグラフが表示されます。各コンポーネントは2部です。A頂点を2つのセットに分散しB、2つのセット間の差が最小になるようにするにはどうすればよいですか？

例：

1：1 -> 2 ->3 -> 4 -> 5

2：6 -> 7 -> 8

最善の解決策は

A = {1, 3, 5, 7}

B = {2, 4 ,6, 8}

他の（最適ではない）解決策は

A = {1, 3, 5, 6, 8}

B = {2, 4, 7}

グラフに多くの個別の2部コンポーネントがある場合、これをどのように解決しますか？

2 部グラフの接続を表す正方バイナリ マトリックスがあります。問題は、すべての行から列への 1 対 1 のマッピングが存在するかどうかです。(明確にするために、言語を間違って使用している場合、完全に接続されたグラフは、1 対 1 のマッピングのみに制限されていないため、この要件を満たします)。

以下を書きました。これを達成するためのとてつもなく速い方法はありますか？

友人が私に真実のように思われる推測を提示しましたが、私たちのどちらも証明を思い付くことができません. 問題は次のとおりです。

|U|<|V| のように、互いに素な空でない頂点セット U と V をもつ接続された 2 部グラフが与えられ、すべての頂点が U または V のいずれかにあり、同じセット内の 2 つの頂点を接続するエッジはありません。次数(a)>次数(b)となるように頂点a∈Uとb∈Vを接続するエッジが少なくとも1つ存在する

U に V の次数よりも高い次数を持つ頂点が少なくとも 1 つあることを証明するのは簡単ですが、それらを接続するエッジを持つペアが存在することを証明するのは困難です。

グラフ理論に関連する次の質問を考えてみましょう。

Gを2部グラフとします。問題をより具体的にするために、Gが2つの集合の非交和であると仮定します。たとえば、IとSを仮定します。

• 私は名前が1、2、3、4、5、6、7、8、9、10の個人を表します
• Sは、名前がa、b、c、d、e、f、g、hのスキルを表します。

したがって、各個人にはいくつかのスキルがあります。たとえば、

• 個人1はスキルb、d、g、hを持っています。
• 個人2には、スキルa、f、およびhがあります。
• 等

[この例では、データはランダムに与えられます]。

Sのすべてのスキルがチームに表されるように、つまりSのスキルごとに、そのスキルを持つチームのメンバーが存在するように、Iの最小数の個人で構成されるチームを構築することを目指しています。 s。

この問題には名前がありますか？それを解決するための効率的なアルゴリズムは知られていますか？

二部グラフの問題で最大マッチングに行き詰まっています。問題は次のようになります。

m 個の円形の穴があるボードと n 個の円形ディスクのセットが与えられます。穴には h ₁、...、h _m、ディスクには d ₁、...、d _nの番号が付けられます。

m 行 n 列の行列 A があります。A[i][j] = 1 は、h _{iが d j}に適合する場合(つまり、h _iの直径 ≥ d _jの直径)、それ以外の場合は 0 です。

任意の穴に最大 1 つのディスクを含めることができるという条件を考えると、穴ディスクのフィッティングが最大になる構成を見つける必要があります。

この問題はネットワーク フローの問題にモデル化できると読みましたが、その方法を正確に追うことができませんでした。誰かがこれを行う方法を説明できますか? また、私が見ることができるかもしれないこれのためのCコードはありますか?

BPMの実装である次のコードがあります（グラフ理論からの二部マッチング）

このコードの定義cntと目的を以下に示します。

m 行 n 列の行列として表される 2 部グラフを指定すると、graph[i][j]はtruepigeoniから hole へのエッジがある場合にj、穴を見つけることができる鳩の最大数 (鳩ごとに 1 つ) と最適な割り当てを計算します。

• graph[m][n]、matchL[n]、matchR[m]およびseen[m]はグローバル配列です。
• main()すべてのコンポーネントで初期化matchL[]してmatchR[]からにします。-1

• main()すべてのハトiをループし、各反復でループします

  • すべてのコンポーネントseen[]でクリア0
  • カウンターを呼び出しbpm(i)てインクリメントしますmaxflow
  • bpm(i)trueハトiに穴を割り当てることができる 場合は返します

• cnt幸せなハトの数が含まれています。

私の場合、cntの値は として出力され0ます。このグラフ アルゴリズムは正しく機能しますか、それともエラーが発生しましたか?