问题标签 [approximation]

在一个项目中我遇到了这个问题，我将在这里用问题的实际领域之外的术语重新表述（我想我可以谈论烟花的口径和形状，但这会使理解更加复杂）。我正在寻找一种（可能是近似的）算法来解决它。

我有n个大小不一的容器，m个不同大小职业、不同颜色的物件（物件可以是多色的，所以一个物件的颜色是真正的一套）。

我的目标是将所有对象放入容器中（我已经知道这是可能的），以便每个容器的颜色种类最小化。对于“颜色的种类被最小化”，我的意思是每个容器的不同颜色数量的总和是最小的。

一个例子。我有两个大小为 2 的容器和四个对象，它们的颜色是 {red}、{red,green}、{blue}、{blue,green}，每个大小为 1。最佳解决方案是 [{red} , {red, green}], [{blue}, {blue, green}]，其中总品种为 2+2=4。更糟糕的解决方案是 [{red}, {blue}], [{red, green}, {blue, green}]，其中总品种为 2+3=5。

我的猜测是这个问题是 NP 难题，因为它听起来比背包问题更难：对象的值被转换为负值，而且取决于同一容器内的其他对象。但是我不知道如何解决这个问题以获得一个近似的解决方案，无论如何这将是非常受欢迎的。

我在读一本书，叫《概率中的 50 个具有挑战性的问题》，里面有很多与概率相关的脑筋急转弯。我无法解决其中的一个问题，也无法理解解决方案。所以，我正在编写代码以获得更好的感觉。这是原始问题。

The Theatre Row：八位优秀的单身汉和七位漂亮的模特随机购买了同一排 15 座剧院的单人座位。平均而言，有多少对相邻的座位是为结婚的夫妇买票的？

这是我的代码，从 100 个随机抽样中获取相邻对的平均数量：

该代码生成随机系列的 0（代表女性）和 1（男性）。然后它“减少”随机序列，以便没有重复的 0 或 1。例如，如果代码生成一个随机序列 011100110010011（有 7 个相邻对），则将序列缩减为 01010101。在缩减格式中，要计算出相邻对的数量，只需获取“大小- 1"。

这是我的问题。

1. 这个问题的答案（根据本书）是 7.47，而我从代码中得到的平均约为 7 左右。有人看到差异的来源吗？

2. 我的代码有时似乎效率很低。是因为我生成随机序列的方式吗？（如您所见，为了生成 8 名男性和 7 名女性的随机序列，我一直要求一个大小为 15 的随机序列，直到它恰好有 8 名男性（或“1”）和 7 名女性（或“0”） .当有这样的约束时，有没有更好的方法来产生随机序列？

在编程方面我不是很熟练。我会很感激任何评论。谢谢你的帮助！！

有谁知道在处理大实数和负实数时如何使以下 Matlab 代码更准确地逼近指数函数？

例如，当 x = 1 时，代码运行良好，当 x = -100 时，当它应该更接近 3.7201e-44 时，它返回 8.7364e+31 的答案。

代码如下：

任何帮助表示赞赏，欢呼。

编辑：

好的，所以问题如下：

这段代码近似于哪个数学函数？（我说的是指数函数。）当 x = 1 时它是否有效？（是的。）不幸的是，当 x = -100 时使用它会产生答案 s = 8.7364e+31。您的同事认为程序中存在愚蠢的错误，并请求您的帮助。仔细解释行为并给出一个简单的修复方法，从而产生更好的结果。[您必须建议对上述代码进行修改，否则它会被使用。您还必须检查您的简单修复工作。]

所以我有点理解，当术语之间有 16 个（或更多）数量级时，问题围绕着大量数字，精度会丢失，但解决方案却让我望而却步。

谢谢

编辑：

所以最后我选择了这个：

不确定它是否完全正确，但它返回了一些很好的近似值。

exp(-100) = 3.720075976020836e-044
s = 3.722053303838800e-044

经过进一步分析（不幸的是提交了作业），我意识到增加迭代次数，从而增加项，进一步提高效率。事实上，以下方法更有效：

这使：

exp(-100) = 3.720075976020836e-044
s = 3.720075976020701e-044

注意：由于旅行不会在它开始的同一个地方结束，而且只要我仍然访问所有点，每个点都可以多次访问，这不是真正的 TSP 变体，而是我之所以这样说是因为缺乏对问题的更好定义。

所以..

假设我要去一次有 n 个兴趣点的徒步旅行。这些点都由远足径相连。我有一张地图，显示所有路径及其距离，给我一个有向图。

我的问题是如何估计从 A 点开始并访问所有 n 个兴趣点的旅行，同时在除我开始的点之外的任何地方结束旅行，并且我希望旅行尽可能短。

由于徒步旅行的性质，我认为这很遗憾不是一个对称问题（或者我可以将我的不对称图转换为对称图吗？），因为从高海拔到低海拔显然比相反的方式更容易。

此外，我相信它必须是一种适用于非度量图的算法，其中不满足三角形不等式，因为从 a 到 b 到 c 可能比走一条从 a 到 c 的漫长而奇怪的道路更快直接地。我确实考虑过三角不等式是否仍然成立，因为对于我访问每个点的次数没有限制，只要我访问所有这些点，这意味着我总是会选择从 a 到 c 的两条不同路径中最短的一条，因此永远不会走上漫长而怪异的道路。

我相信我的问题比 TSP 容易，所以那些算法不适合这个问题。我考虑过使用最小生成树，但我很难说服自己它们可以应用于非度量非对称有向图。

我真正想要的是一些关于如何提出近似算法的指示，该算法将在所有 n 点中找到接近最优的路径

我有一个包含 N 个测量值的数组，应该以图形的形式呈现，但图形只能是 M 像素宽，并且只能滚动 M 像素。

虽然 M 是常数，但 N 可以是从几万到几千的任何值。每次我需要显示图表时，我都知道 N 是什么，但是由于 N/M 不能是整数，所以我想以某种方式补偿累积的误差。

我正在使用普通的 C 语言，并且不能使用任何数学库。

编辑 2：数据相对均匀，偶尔会出现峰值，我不想在插值时错过这些峰值。

编辑 3：我正在寻找对任何大于 M 且小于 M 的 N 都足够好的解决方案。

谢谢。

保证目标函数在插值范围内[a, b]及其一阶和二阶导数是有限且连续的，并且在此范围内不超过一个最小值（如果它没有最小值，则它是单调的）。该函数在插值范围内没有窄峰，一般接近抛物线y = a*x + b*x^2（但不完全是抛物线）。请建议一种迭代算法（和插值方法），以选择“最佳”新采样点（从点a和开始b）以构建插值函数，该函数在范围内的任何点以规定的相对精度逼近目标函数[a, b]（至少有合理的概率）。该函数的计算成本非常高，因此函数评估（采样点）的数量应该最少。同时，算法的复杂性并不重要。

问题如下。我有一维数据数组，我需要以最佳方式近似给定数量的水平线（例如，3 条线）（因此，汇总误差变得最小）。近似方法应该尽可能快（所以，我不能取每条水平线，近似数据集，从数据集中提取它的值，然后用剩余的线集近似其余部分）。现在，我不知道该怎么做，只是稍微感觉这个问题的解决方案与最大子阵列问题的解决方案有关。拜托，你能给我一些建议如何解决它吗？

我正在使用从 MATLAB 文档中获取的以下代码来估计 ARMA 模型的参数：

y = sin([1:300]') + 0.5 * randn(300, 1);
y = iddata(y);
mb = ar(y, 4, 'burg');

在这一点上，如果我输入mb我得到的是：

离散时间 IDPOLY 模型：
A(q)y(t) = e(t)
A(q) = 1 - 0.2764 q^-1 + 0.2069 q^-2 + 0.4804 q^-3 + 0.1424 q^-4
估计使用来自数据集 y
损失函数 0.314965 和 FPE 0.323364的 AR ('burg'/'now')
采样间隔：1

如何使用mb我获得的变量来生成具有这些系数的样本？
mb看起来不像矢量。
特别是，我该如何处理丢失的数据？

我有两组不同的随机分布的实验数据。我需要通过对它的每个值应用一些函数来使其中一个分布与另一个分布尽可能相似。函数示例：F(x) = x*(1+(x+p1)*p2，其中 p1 和 p2 是一些任意参数。找出是否可能，如果可能，那么 p1 的值是多少和 p2，我写了一个简单的 python 脚本：

我知道在所有可能的方式中，这是最丑陋和最慢的一种。不幸的是，我根本没有编程背景，这是我第一次卑微的努力。鉴于得到的分布的平均值是一个 khown 常数，适当的 p1-p2 对的数量非常有限，但我在这里使用了简单的蛮力。我认为，应该有某种方法可以将 p2 表示为 p1 的函数，但我完全不知道该怎么做。也许你可以给我一些想法？
对不起，我的英语不好...

我有一些容量不同的垃圾箱和一些指定大小的对象。目标是将这些对象打包到垃圾箱中。到目前为止，它类似于装箱问题。但扭曲的是，每个对象都与另一个对象有部分重叠。因此，虽然对象 1 和 2 的大小分别为 s1 和 s2，但当我将它们放在同一个 bin 中时，填充的空间小于 s1+s2。假设我知道每对对象的重叠值，是否也有任何近似算法，例如用于该问题的原始装箱算法？