问题标签 [data-partitioning]

我需要存储图形分区的数据分组节点，例如：

[节点1，节点2] [节点3] [节点4，节点5，节点6]

我的第一个想法是只有一个简单的向量或整数数组，其中数组中的位置表示 node_id，它的值是某种 group_id

问题是许多分区算法依赖于对组内的节点对进行操作。使用这种方法，我想我会浪费大量的计算来搜索向量以找出哪些节点属于同一组。

我也可以存储为一组 stl 集，这似乎更接近分区的数学定义，但我得到的印象是不建议或不需要嵌套集，我需要修改我不确定的内部集是可能的。

有什么建议么？

自从昨天站在超市的销售点，再次尝试启发式地找到我的硬币的最佳分区，同时试图忽略我身后不耐烦和紧张的队列，我一直在思考潜在的算法问题：

给定一个价值为 v ₁ ,...,v _n的硬币系统，有限数量的硬币 a ₁ ,...,a _n以及我们需要支付的金额 s。我们正在寻找一种算法来计算分区 x ₁ ,...,x _n (with 0<=x _i <=a _i ) with 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 等人解释的贪婪算法）。我们还需要确保没有换钱，所以最好的解决方案不是简单地给所有的钱（因为在这种情况下解决方案总是最优的）。

感谢您的创意输入！

我想为每个图像计算颜色布局描述符（CLD）。这个算法包括四个阶段。在第一阶段，我必须将每个图像划分为 64 个块 i(8×8)n，以便从每个块中计算出一个代表颜色。我尝试使用（For 循环）将图像划分为 64 个块，但我得到 64廷形象。我想用（8×8）块获得图像，以便通过应用 DCT 变换然后之字形扫描来完成算法

我有一个向量，例如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）这是一种非常低效的实现结果的方法

，所以欢迎任何更好的解决方案。

给出一个 O(n) 算法，该算法将数组 S 作为输入，然后将 S 分为三组：负数、零数和正数。展示如何就地实现这一点，即不分配新内存。而且你必须保持数字的相对顺序。例如：{-1, 4, 0, -2, 1, 2} ==> {-1, -2, 0, 4, 1, 2}

我不确定这样的解决方案是否存在。我能想到的最佳解决方案是：

解决方案1：使用一个额外的整数数组，然后遍历整个数组得到负数，然后是0，然后是正数。

解决方案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 整除，并且每一半都可以放在一个单独的分区中。

例如：N = 4 数字：20 5 3 1

结果是：15

解释：第一个数字将被二除，每半放在两个分区之一 => 第一个分区 = 10，第二个分区 = 10。第二个数字将添加到第一个分区 => 第一个分区 = 15。最后两个数字将添加到第二个分区 => 第二个分区 = 14

=> 更大分区的总和（分区一）= 15。

我的想法是对奇数进行递减排序并使用贪心算法开始添加它们，始终保持两个分区之和之间的差异尽可能最佳。在完成奇数之后，剩下的就是取偶数，看看是否将它们完全添加到一个分区中，是否比将它们除以 2 并将每一半添加到这两个分区中的一个分区中更好。

同样对于以下数据集，算法将提供正确答案：N = 2 数字：16 15

=> 将取 15，将其添加到第一个分区，然后取 16，看到将其除以 2 不是最佳的，因此它将添加到第二个分区。

=> 答案将是 16。

如果您能给我提供一组数据，算法无法提供最佳答案，我很感兴趣，如果您能提出任何改进建议，我也将不胜感激。

谢谢！:)

给定凸多边形 P 和 P 边界上的点 A，我如何计算 P 边界上的点 B 使得 AB 将 P 分成给定比例的两个区域？

理想情况下，我想要一个分析解决方案。作为最后的手段，我可​​以在多边形的任何地方画一条线并逐渐移动它，直到比例正确到给定的精度。

一旦我知道它应该在多边形上的哪两个点之间，我已经计算出如何计算 B 。因此，如果有办法找出它应该在哪些点之间移动，我应该能够从那里拿走它！

有一个包含 N 个整数的集合 S，每个整数的值 1<=X<=10^6。问题是将集合 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}

第一个问题是在数学上表达一个分区优于另一个分区的条件。第二个问题是如何解决问题。问题是NP-Hard。有什么启发式方法吗？

在我试图解决 N <= (k*logX)^2 的问题中，K 从 2 到 7 不等。

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

基于其他相关的 SO 问题，评估分布有两个合理的函数：

a) 最小化具有最大值的分区的值。

再想一想，这不是一个好的指标。考虑，一组 {100, 40, 40} 被划分为三个子集。该指标不区分以下两种分布，即使其中一种明显优于另一种。

分布 1：{100}、{40}、{40} 和分布 2：{100}、{40、40}、{}

b) 最小化给定分区中任意两个值之差的最大值，即最小化 max|AB| 对于任何 A、B