問題タブ [data-partitioning]

グラフパーティションのデータグループ化ノードを保存する必要があります。

[node1、node2] [node3] [node4、node5、node6]

私の最初のアイデアは、単純なベクトルまたはintの配列を作成することでした。配列内の位置は、node_idを示し、その値は、ある種のgroup_idです。

問題は、多くのパーティションアルゴリズムがグループ内のノードのペアでの動作に依存していることです。この方法では、どのノードが同じグループに属しているかを見つけるために、ベクトルを検索するために多くの計算を無駄にするだろうと思います。

パーティションの数学的定義に近いように見えるセットのstlセットとして保存することもできますが、ネストされたセットはアドバイスされていないか不要であるという印象を受けており、よくわからない内部セットを変更する必要があります可能です。

助言がありますか？

昨日スーパーマーケットの売り場に立って以来、私の後ろのせっかちで神経質な列を無視しようとしながら、コインの最適な配分をヒューリスティックに見つけようとして、根本的なアルゴリズムの問​​題について考えていました。

_{値が v 1} ,...,v _nのコイン システムが与えられ、限られたコインのストック a ₁ ,...,a _nと、支払う必要のある合計 s が与えられます。_{パーティション x 1} ,...,x _n (with 0<=x _i <=a _i ) を x ₁ *v ₁ +x ₂ *v ₂ +...+xで計算するアルゴリズムを探しています。_n *v _n >= s x ₁ +...+x _n - R(r) の合計が最大になるようにします。ここで、r は変化です。つまり、r = x ₁ *v ₁ +x ₂ *v ₂ + です。 ..+x_n *v _n - s であり、R(r) はレジ係から返されたコインの数です。レジ係はすべてのコインの量に制限がなく、常に最小数のコインを返すと仮定します (たとえば、SCHOENING et al. で説明されている欲張りアルゴリズムを使用して)。また、お金の変更がないことを確認する必要もあります。そのため、最善の解決策は、単純にすべてのお金を提供することではありません (その場合、解決策は常に最適であるため)。

クリエイティブなご意見ありがとうございます。

各画像のカラー レイアウト記述子 (CLD) を計算したい..このアルゴリズムには 4 つの段階が含まれます。最初の段階では、各ブロックから単一の代表色を計算するために、各画像を64ブロックi（8×8）nに分割する必要があります..（Forループ）を使用して画像を64ブロックに分割しようとしましたが、64を取得しますティン画像。DCT変換を適用してからジグザグスキャンしてアルゴリズムを完成させるために、（8×8）ブロックで画像を取得したい

次のようなベクトルがありc(1, 3, 4, 5, 9, 10, 17, 29, 30)、規則的な連続シーケンスを形成する「隣接する」要素をグループ化したいと思います。つまり、1ずつ増加し、次のような不規則なベクトルになります。

L1：1
L2：3,4,5
L3：9,10
L4：17
L5：29,30

（元Cプログラマーの）ナイーブなコード：

これで、a）RはCではない（中括弧にもかかわらず）
b）グローバル変数は純粋な悪
であるc）結果を達成するためのひどく非効率的な方法であることがわかりました

、したがって、より良い解決策は大歓迎です。

配列 S を入力として受け取り、S を 3 つのセット (負、ゼロ、および正) に分割する O(n) アルゴリズムを指定します。これをその場で、つまり新しいメモリを割り当てずに実装する方法を示します。また、番号の相対的な順序を維持する必要があります。例: {-1, 4, 0, -2, 1, 2} ==> {-1, -2, 0, 4, 1, 2}

そのような解決策が存在するかどうかはわかりません。私が考えることができる最善の解決策は次のとおりです。

解決策 1: 追加の整数配列を使用して、配列全体をトラバースして、負の値、0、正の値の順に取得します。

解決策 2: 数値の相対順序を保持しない。次に、配列を 2 回ループします。

与えられた整数の集合 S:

各部分の合計が最小になるように、集合を k 個の部分に分割するにはどうすればよいでしょうか? 実装もお願いしCます。

例：

パーティション

各分割の合計が最小になるという性質があります。

Setを指定し、和の差が最小になるようSにセットを互いに素なサブセットに分割します。k

と言うと、S = {1,2,3,4,5}それらk = 2の{ {3,4}, {1,2,5} }合計{7,8}の差は最小限であるためです。合計の差S = {1,2,3}, k = 2が であるためです。{{1,2},{3}}0

この問題は、The Algorithm Design Manual のThe Partition Problemに似ています。ただし、 Steven Skienaが再配置せずに解決する方法について説明しています。

シミュレーテッドアニーリングを試してみました。だから、もっと良い方法があったのだろうか？

前もって感謝します。

次の問題があります: N 個の整数のセットが与えられた場合、それらを 2 つのほぼ等しいパーティションに分割し、より大きなパーティションの合計が最小になるようにします。これは、1 つの例外を除いて、従来のパーティションの問題とほぼ同じように思えます。

例: N = 4 数値: 20 5 3 1

結果: 15

説明: 最初の数値は 2 で除算され、各半分は 2 つのパーティションのいずれかに配置されます => 最初のパーティション = 10、2 番目のパーティション = 10。2 番目の数値は最初のパーティションに追加されます => 最初のパーティション = 15。最後の 2 つの数字が 2 番目のパーティションに追加されます => 2 番目のパーティション = 14

=> より大きいパーティション (パーティション 1) の合計 = 15。

私が持っているアイデアは、奇数を減らして並べ替え、貪欲なアルゴリズムを使用してそれらを追加し始め、常に2つのパーティションの合計の差を可能な限り最適に保つことです。奇数の処理が終わったら、残っているのは偶数を取り、1 つのパーティションにそれらを完全に追加する方が、それらを 2 で割って 2 つのパーティションの 1 つに追加するよりも最適かどうかを確認することです。

また、次のデータセットについても、アルゴリズムは正しい答えを提供します: N = 2 数字: 16 15

=> 15 を取り、それを最初のパーティションに追加し、次に 16 を取り、それを 2 で割るのが最適ではないことを確認します。したがって、2 番目のパーティションに追加します。

=> 答えは 16 になります。

アルゴリズムが最適な答えを提供しない一連のデータを提供していただければ幸いです。また、改善点を提案していただければ幸いです。

ありがとう！:)

凸多角形 P と P の境界上の点 A が与えられた場合、AB が P を所定の比率の 2 つの領域に分割するように、P の境界上の点 B を計算するにはどうすればよいですか?

理想的には、分析ソリューションが必要です。最後の手段として、ポリゴンの任意の場所に線を描画し、比率が所定の精度になるまで徐々に移動します。

ポリゴン上のどの 2 点間を移動すべきかがわかったら、B を計算する方法を考え出しました。したがって、どのポイントの間を進むべきかを調べる方法があれば、そこから取ることができるはずです!

それぞれ値が 1<=X<=10^6 の N 個の整数を含むセット S があります。問題は、セット S を k 個のパーティションに分割することです。パーティションの値は、そこに存在する要素の合計です。分割は、セット S の合計値が k 個の分割に均等に分配されるように行われます。公正さの数学的意味も定義する必要があります (たとえば、目的は、集合 S の平均値からのパーティションの値の標準偏差 (つまり、sum(S)/k) を最小化することである可能性があります)。

例: S = {10, 15, 12, 13, 30, 5}, k=3

適切なパーティショニングは、{30}、{10, 15}、{12, 13, 5} です。

不適切なパーティショニングは {30, 5}、{10, 15}、{12, 13} です。

最初の質問は、あるパーティションが他のパーティションよりも優れている条件を数学的に表現することです。2番目の質問は、問題を解決する方法です。問題は NP-Hard です。ヒューリスティックはありますか？

N <= (k*logX)^2 を解決しようとしている問題で、K は 2 から 7 まで変化します。

================================================== ================================

他の関連する SO の質問に基づいて、分布を評価するための 2 つの合理的な関数があります。

a) 最大値を持つパーティションの値を最小化します。

よく考えてみると、これは良い指標ではありません。セット {100, 40, 40} を 3 つのサブセットに分割するとします。このメトリックは、次の 2 つの分布を区別しませんが、一方が他方よりも明らかに優れています。

分布 1: {100}、{40}、{40} および分布 2: {100}、{40、40}、{}

b) 特定のパーティション内の任意の 2 つの値の差の最大値を最小化します。つまり、max|AB| を最小化します。任意の A、B