問題タブ [disjoint-union]

2つのセット（ILists）があり、最初のリストのすべてのアイテムが必要ですが、そのアイテムは2番目のリストにはありません。

誰かがLINQステートメントでこれを達成するための最良の方法を私に指摘できますか？

クエリを機能させるのに問題がありますが、うまくいくはずです。という形になっています

しかし、mysql は "IN (" が始まる場所をチョークします。mysql はこの構文をサポートしていますか? サポートしていない場合、これらの結果を取得するにはどうすればよいですか? テーブル 1 に存在しない (a,b,c) の個別のタプルを見つけたい表2で。

今日、このスライドの 13 ページのために、Kruskal 最小スパニング ツリー アルゴリズムについて誰かと議論しました。

プレゼンテーションの著者は、(二重) リンク リストを使用して素集合を実装すると、MakeとFindのパフォーマンスはそれぞれ O (1)とO(1 )になると述べています。Union(u,v)操作の時間はmin(nu,nv)です。ここで、nuとnvは u と v を格納するセットのサイズです。

セットの実表現へのポインターを含むロケーターを指す各メンバーの表現ポインターを作成することにより、 Union(u,v)がO(1)になる時間を改善できると述べました。

Java では、データ構造は次のようになります。

ミニマルなコードで申し訳ありません。この方法で作成できる場合、互いに素な集合操作 ( Make,Find,Union )ごとの実行時間はO(1)になります。しかし、私が話し合った人は改善を見ることができません。これについてあなたの意見を知りたいです。

また、さまざまな実装における Find/Union の最速のパフォーマンスは? 私はデータ構造の専門家ではありませんが、インターネットをざっと見てみると、これを行う一定時間のデータ構造やアルゴリズムがないことがわかりました。

f 比較的単純な AND/OR 句のように見えるものがあり、少し頭が痛くなります。

$regionとの両方から値を取得するために必要$countriesです。ただし、そのままでは の値しか返されません$countries。の行を削除すると、ORの値が返されますが$region、両方は返されません。私は間違って何をしていますか?

素結合では、高さがそれぞれ h1 と h2 である 2 つのツリーをマージする必要があるとします。この手法を使用すると、結果のマージされたツリーの高さは、h1 が h2 と等しくない場合は max(h1, h2) になり、h1 == h2 の場合は h1+1 になります。初期状態から始まるマージ操作の任意のシーケンスの後にこの手法を使用すると、「k」個のノードを含むツリーの高さは最大 (logk のフロア) になります。これは帰納法により次のように証明される.

ベース: k=1 の場合、高さは 0. 0<= (floor(log 1))

誘導ステップ: を考えk >1て、仮説により、 となるすべての m に対して定理が真であるとし1<=m<kます。kノードを含むツリーは、2 つの小さなサブツリーをマージすることによって取得できます。これらの 2 つの小さなツリーには、一般性を失うことなく想定できる「a」ノードと「b」ノードがそれぞれ含まれているとしa<=bます。したがってa>=1、初期状態から始まるノードが 0 のツリーを取得する方法はなく、k=a+b です。そして、、、 両方、 、、 したがって、 と続きますa<=k/2b<=k+1。k>1k/2 < k(k-1) < ka<kb<k

上記の私の質問は

1. 上記の「a<=k/2 and b<=k+1」というステートメントをどのようにして得たのか。

ありがとう！

整数値または整数範囲 (initial..final) を返すメソッドがあり、値がすべてばらばらかどうかを知りたいです。

次のソリューションよりも効率的なソリューションはありますか。

こんにちは、これは私の初めての投稿です、

私は勉強のための質問を考え出そうとしましたが、それを理解することができませんでした：

サイズとパス圧縮による加重和集合を使用した、互いに素なセットの抽象データ型のフォレスト実装を検討します。最初は、各要素は1ノードツリーにあります。

上記の初期状態から開始します。

1. UNIONおよびFIND操作の（短い）シーケンスを指定します。最後の操作はUNIONであり、高いツリーAが短いツリーBのサブツリーになります（つまり、Aの高さがBの高さよりも厳密に大きい）。 。

2. 最後のUNIONがマージする2つのツリーAとBを表示します

ヒント：n = 9個の要素から開始でき、各要素は1ノードツリーにあります。

サイズによる結合のために、小さいツリーは常に大きいツリーとマージされるため、それがどのように機能するかわかりませんか？

ありがとう。

まず、問題に関するいくつかのコンテキスト:

いくつかのタイプのリソース (A、B、C...) を持つシステムで作業しています。いくつかのリソース要件が与えられており、それらを購入できるかどうかを判断する必要があります。

このために、いくつかのソースがあり、それぞれが複数のタイプのリソースを提供できますが、各リソースに使用するソースを選択する必要があります。

たとえば、1A、2B、および 0C ((1,2,0) として表される) を支払う必要があり、次のソースがあるとします。

1. (1,1,0) //生産物 A または B を選択する必要があることを意味します
2. (0,1,1) //生産物 B または C を選択する必要があることを意味します
3. (1,1,0)

リソース B にソース 2 を使用しなければならないことは明らかであり、1 と 3 のどちらが A と B を生成するかを選択できます。

これを実装するための私のアプローチは、上記の状況が次のように表される依存グラフとして表示することです。

したがって、リソースをループし、すべてのリソースについて、それに到達するリンクをループします。現在のリソースの現在のノードを削除すると、残りの支払いコストを支払うのに十分な到達リンクが他のリソースに残っていることを意味する場合は、それを使用します。

前の例では、最初にリソース A にソース 1 を使用しようとします。B にはまだ 2 つのリンクがあるので、使用できます。タイプ B のリソースだけが残っているので、残りのリソースを使用して B を支払います。

これで問題ありませんが、新しいシナリオで作業する必要があります。ここでは、2 種類のソースがあり、それぞれが 1 種類のリソースをコスト 1 またはコスト 2 で生成し、総コストを最小限に抑える必要があります。

この例をわずかに変更すると、次のようになります。

常識的な解決策は、1 と 2 を使用して B に支払い、3 を使用して A に支払い、合計コスト 1 にする必要がありますが、上記のように、私の実装では、B にはまだ 2 つのリンクがあるため、ソース 1 を使用して A に支払います。そのため、最後にソース 3 をコスト 2 で使用する必要があります。

すべての選択肢の組み合わせを試すことを意味する解決策は、可能であれば避けるべきです。

このケースに適用できる既知の解決策を持つ一般的なアルゴリズムの問​​題について知っていますか? または、この新しいシナリオで機能するように実際のソリューションを改善するにはどうすればよいですか? それとも、別の別のアプローチを取る必要がありますか?

ばらばらのセットフォレストを使用して、ペナルティが最小化されるようにペナルティのあるジョブをスケジュールするにはどうすればよいですか？

最初に、ペナルティに基づいて降順でジョブを並べ替えることができます。フォレストの各ノードxはジョブ番号を表し、値rank[x]はそのペナルティを表します。しかし、ペナルティを最小限に抑えるために、この値のランク[x]を最小化するにはどうすればよいですか？ノードの順序によってジョブの順序がわかりますが、このためのアルゴリズムは何になりますか？どうすれば森を作ることができますか？