问题标签 [approximation]

我有一个正整数数组 A [a0, a1, a2, ..., an] 和一个正数 K。我需要找到数组 A 的所有（或几乎所有）子集 U 和 V 对，例如：

1. U 中所有元素的总和小于或等于 K
2. V中所有元素的总和小于或等于K
3. U + V 可能不包含原始数组 A 的所有元素
4. U 中的所有元素都应该在初始数组 A 中 V 中的所有元素之前。例如，假设我们选择 U = [a1, a3, a5] 那么我们可以仅从 a6 开始构建数组 V。在这种情况下，不允许使用元素 a0、a2 或 a4。

我能够找到 DP 解决方案，即 O(N^2 * K^2) （其中 N 是 A 中的元素总数）。尽管 N 和 K 很小（< 100），但仍然太慢。

我正在寻找一些近似算法或伪多项式动态规划算法。装箱问题看起来与我的相似，但我不确定如何将其应用于我的约束......

请指教。

编辑：每个数字的上限等于 50

经典的旅行商问题 (TSP) 定义之一是：

给定一个三角不等式成立的加权完全无向图，返回一条总权重最小的哈密顿路径。

在我的情况下，我不想要哈密顿路径，我需要两个众所周知的顶点之间的路径。所以公式是：

给定一个加权完全无向图，其中三角不等式成立，并且两个称为源和目标的特殊顶点返回一个最小加权路径，该路径恰好访问所有节点一次，并从源开始并结束到目的地。

我记得哈密顿路径是无向图中的路径，它只访问每个顶点一次。

对于原始问题，Christodes 算法是一个很好的近似值（最好解决方案的 3/2），是否可以针对我的情况进行修改？或者你知道另一种方式？

所以我有一个 alpha 向量，一个 beta 向量，当所有估计值（对于 alpha 的 i 到 n 和 beta 的 i 到 n）的总和等于 60 时，我试图找到一个 theta。

math.exp(alpha[i] * (theta - beta[i])) / (1 + math.exp(alpha[i] * (theta - beta[i])

基本上我所做的是从 theta = 0.0001 开始，遍历，计算所有这些总和，当它低于 60 时，继续每次添加 0.0001，而高于 60 意味着。

我以这种方式找到了 theta 值。问题是，我使用 Python 花了大约 60 秒，才找到 0.456 的 theta。

找到这个 theta 的更快方法是什么（因为我想将它应用于其他数据）？

首先阅读：问题只是绝对值的括号应该围绕实际分数。现在的问题是它实际上不够精确，它忽略了 0.000001，并且更喜欢 0.0001 作为容差（当我要求它接近 55 时，它停在 54.994397921372205）。我将容差增加到疯狂的 0，然后是 1，但例如接近 50，它估计为 49.14！糟糕的！为什么会这样？

更新：它必须是float()

我试图找到属于基于某些向量的函数的 theta。我让这段代码在 R 中运行，我试图将它从 R 字面上翻译成 Python。

当 grensscore 等于 50 时，我想近似 Theta 的值。我有一个 theta = 0.5 的起始值，然后它在 R 中迭代。在 R 中只需要大约 11 次迭代就可以达到这一点。

可悲的是，这在 Python 中不起作用，我将它隔离了这么多：由于某种原因，这些值只能低于 0.5，但不能高于。在这些地方使用打印甚至表明它没有#a在代码中运行该部分，而该#b部分正在运行。这表明该值永远不会上升，因此我永远找不到像 0.4 这样的值（因为它必须上升 0.5、0.25、0.37.5、0.4375 等，但它只能下降；0.5、0.25、0.125然后迟早停止）

我可以看到它运行#b。很多时候它必须下降，但它永远不会上升。我也切换了它们，看看是否有顺序效应，但没有：它根本不会评估它是真的（即使我知道它是真的）任何人都可以看到出了什么问题，因为这是在 R 中工作？

我完全了解二进制格式的浮点表示，因此我知道在尝试用任何编程语言完美表示浮点数时存在数学“不可能”。但是，我希望编程语言在处理近似值时遵循一些众所周知且完善的规则。

话虽如此，我读到（这里也是在stackoverflow上）PHP中的printf可能是“正确截断/近似”数字的最佳方法，并且 - 再次 - 我完全意识到并且我可以轻松编写单行函数给我“完美”的近似值。这只是为了避免诸如“你为什么不使用 XXX 或做 YYY？”之类的回答。

尝试这个：

这是输出：

1.500000 1.50
1.501000 1.50
1.502000 1.50
1.503000 1.50
1.504000 1.50
1.505000 1.50
1.506000 1.51
1.507000 1.51
1.508000 01.510
1.510 1.51

如您所见，1.504（正确）打印为 1.50，而 1.506（正确）打印为 1.51。但是为什么 1.505 打印为 1.50？！它必须是 1.51，而不是 1.50！

谢谢...

在我们的模拟中，我们有一个基本的 2D 网格，闭合曲线（红线）可以在该网格上移动。网格单元根据其中心的位置被着色为曲线内部（绿色）或曲线外部（蓝色），并且每个状态变量（例如压力）可以具有不同的值。对于域中的任何给定点，我们可以准确地知道它是在内部还是外部，并且插值可以给出该点的特定状态（即，此信息比仅使用以单元为中心的笛卡尔网格更具体）。

我们正在尝试对曲线内的“峰值”压力进行稳健的测量（例如，峰值可能是前 1% 值的平均值）。

目前，我们只取单元格中心值的最大值，但正如您在图像中看到的那样，每次曲线移动时，这都会给我们带来非常大的差异。我正在尝试评估不同的选项，但我不确定它们的有效性，特别是如果有我们可以使用的统计技术。

我们考虑过的选项：

1. N*N*num_of_2D_cells在整个网格上随机抽取点样本
2. 对于每个 2D 单元，随机抽取N*N点样本
3. 将每个 2d 单元格细分为N*N更小的单元格并计算它们以单元格为中心的值

然而，随着N规模的扩大，这些方法应该会收敛，但是我们的 2D 网格可以有超过 1e7 个单元；因此，计算时间对大小设置了上限N。

有没有人有经验——或者知道一组处理——这类问题的文献？

http://en.wikipedia.org/wiki/Nearest_neighbour_algorithm

我正在使用最近邻算法来解决旅行商问题。它非常快，但并不准确。我在某处读到了我可以做出的两项改进。第一种不是从一个随机点开始，而是从每个节点开始运行最近邻算法。（所以如果有N个节点，最近邻居运行N次）然后比较并选择总距离最小的路线。这似乎要精确得多。但是太慢了。

另一种方法不是随机选择起始节点，而是选择一个特殊的节点。然后仍然只运行一次最近的邻居以获得结果。这不会像上面的方法那样准确，但肯定要快得多，因为该算法像以前一样只运行一次。但不幸的是，我不记得我在哪里读到那篇文章以及选择这个起始节点的标准。

我猜我应该得到每个节点到其他节点之间的总距离，然后应该选择具有最大值的节点作为起始节点。（用我的话来说，这是选择一个离图表“最远”的节点，同时也避免选择靠近图表中心的节点）我认为这样我得到的路线应该非常接近最佳最短路线。

我想对了吗？

编辑：我正在处理具有欧几里得距离的度量 TSP。

我们在学校有这个练习，我们要计算算法的下限。我们知道下限是：Log_6((3*n)! / n!^3) 我们将使用斯特林近似来近似 n!。当应用斯特林近似时，我们得到：

log_6((sqrt(2*pi*3*n)*((3*n)/e)^(3*n) * e^alpha)/(sqrt(2*pi*n)*(n/e) ^n * e^alpha)^3)

现在我们的问题是，每次我们尝试用简单的对数属性扩展这个公式，例如 log(a/b) = log(a)-log(b), log(a*b) = log(a)+log( b), log(a^b) = b*log(a) 最后对于 sqrt log(sqrt(a)) = log(a^1/2) = 1/2 * log(a)，我们得到一个结果支配表达式的位置将是 n*log(n) * 常量。现在我们从老师那里知道我们必须找到一个线性下限，所以这是错误的。

我们已经使用了 2 天，即将放弃。有人可以帮助我们吗？

提前致谢！

我们有一些以某些关键值为特征的元素。

我们按照键值的降序考虑元素。所以，如果我们有十个元素的键值是 4、5、7、10、2、8、9、10、8.5、9，我们按元素的键值对元素进行排序，并将具有相同键值的元素一起考虑。

因此，将一起考虑具有相同键值（例如 10）的元素，然后是具有键值 9 的元素，依此类推。当一个元素被考虑，并且它通过了某个适应度函数时，它就会从列表中删除并且不再被考虑。

现在我们稍微放宽了将键值相等的限制放在一起考虑，将键值大致相等的元素放在一起考虑。因此，当我们说在排序顺序中第二个元素在第一个元素的 10% 范围内时，它们将被一起考虑。

因此，现在要一起考虑键值为 10、10、9、9 的元素。并且如果此处未删除键值为 9 的一个元素，则必须使用 8.5 再次考虑它。

我能想到实现上述场景的唯一方法是这样的，

1. 按键值的降序对元素进行排序。
2. 对于订单中的第一个元素，找到 10% 作为允许偏差。查找落在此偏差窗口内的元素。因此，我们在此窗口中考虑 10、10、9、9。
3. 如果任何元素通过适应度函数，则将其从列表中删除。
4. 形成下一个窗口并重复循环。

这就是我的想法令人难以置信的地方。如何从下一个窗口的开始形成开始？如果排序后的值是 10, 10, 9, 9, 8.5, 8 ... 和 10, 10, 9, 9，在第一个窗口中已经考虑过，下一个窗口应该以 9 开​​头，由 9, 8 组成,5。

以前一个窗口的最后一个值启动下一个窗口是否总是足够的？我尝试了一些反例，但都没有使我的猜想无效。但是如果两个 9 都通过了适应度函数并从列表中删除，那么哪个值开始下一个窗口呢？排序列表中的下一个可用？

所以，我的问题是，

1. 关于使用上一个窗口的最后一个值（如果它被删除，下一个可用）开始下一个窗口的猜想是否正确？
2. 整个过程有没有更好的算法？

Heron 的方法生成一个数字序列，这些数字代表√n的越来越好的近似值。序列中的第一个数字是任意猜测；序列中的每个其他数字都是使用公式从前一个数字prev获得的：

我应该编写一个heron()将两个数字作为输入的函数：n和error。该函数应该从1.0的初始猜测开始，然后重复生成更好的近似值，直到逐次逼近之间的差值（更准确地说，差值的绝对值）最多为error。

这有点棘手，但我需要跟踪四个变量：

我还需要一个带有条件的while循环：

while循环的一般规则是：

所以这就是我到目前为止所得到的，这并不多，因为一开始我不知道如何在while循环下合并“if”语句。

有人可以给我一些正确方向的指示吗？

谢谢你