最小电阻算法

Question

我正在尝试设计一个简单的算法，它接受标准电阻值的向量以及所需电阻值的输入，然后通过串联和并联组合来确定实现等效电阻所需的最小标准电阻器数量，采用串联和并联电阻器的任意组合，以取得较少的电阻器。 有人有什么想法吗？如果我只需要并联或者只需要串联，那就容易得多了，但我不确定如何将两者结合起来以获得最小的总电阻器数量。 顺便说一下，如果你不知道总串联电阻是 S1 + S2 + ...+ SN，总并联电阻是 (1/S1 + 1/S2 + ... + 1/SN)^-1。

- Austin

---

我忘了提到我是在Matlab中尝试这个，所以代码可以向量化。我还计划甚至不考虑公差，只使用一个5％电阻器输入列表。 - Austin

n个电阻器在串联和并联的所有变化中，不同电阻值的数量由http://oeis.org/A005840给出。该数字渐近于n! *（1-log（2））/（log（2））^（n + 1）->指数增长。如果输入值没有太多模式，我会感到惊讶，如果有合理的方法来缩小这个数字。 - Edward Doolittle

“标准电阻值”与它们的公差被设计为覆盖整个正实数线。换句话说，任何电阻已经在标准电阻值的公差范围内，因此您可以用n=1个电阻解决问题。 :-) - Edward Doolittle

代码的另一部分是一个可变输入，您可以在其中列出实验室缺货的电阻器值，并将它们从向量列表中移除。 - Austin

如果是这种情况，那么我们可以将它看作是一个找零问题。我认为我在答案中提出的方法可以解决问题。你可能想考虑另一个问题：有一些将电阻器组合的方式并不能归结为串联和并联，例如立方体边缘上的电阻器。为了真正最小化电阻器的数量，你应该考虑这些电阻网络。 - Edward Doolittle

Answer 1

创建一个对象来保存电阻值，以及它来自的两个电阻值和用于从这两个先前的值中获取该值的操作（串联或并联）。

使用一些集合数据结构，如Set或ArrayList来保存电阻对象。您的集合S1最初只包含您拥有的电阻器（1个电阻器的网络）。现在创建一个集合S2，其中包含S1中一个元素与S1中一个元素的所有组合（串联或并联）。S3是S1和S2的组合。S4是S1和S3的组合，再加上S2和S2的组合。继续进行，直到Sk的成员在容差范围内（例如1％、5％或10％）达到目标值。生成的电阻对象可以逐步展开，以找到其构建方式。

您需要考虑的另一件事是容差如何组合。误差会传播，因此您可能需要从1％电阻器开始，以便在末端获得所需的5％容差电阻值。

- Edward Doolittle

---

这个算法是超指数级的。即使你的电阻器集合相对较小（例如100个），在现代计算机上，你甚至无法在合理的时间或内存中得到5个电阻器网络（S5将有约10^12个元素）。 - MooseBoys

如果两个不同的组合给出相同的结果（例如 R1 + R2 + R3 = R2 + R3 + R1），第二个组合将不会被存储。这样，它就是一个动态规划算法。如果有一种方法可以对电阻的大小设置最大值，以解决特定问题，那么就更容易获得运行时间和空间估计。 - Edward Doolittle

Answer 2

也许遗传算法是最好的选择？我不知道这种情况下的O大写符号计算方法，但它看起来是指数级别的：O(cⁿ)。

我在另一个网站的帖子上找到了这个评论，它表示可以使用不同电阻值的电阻器获得的变化次数（即暴力破解）：
1个电阻器网络：1
2个电阻器网络：2
3个电阻器网络：10
4个电阻器网络：68
5个电阻器网络：558
6个电阻器网络：5186
7个电阻器网络：53805

遗传算法可以避免暴力破解，可能让你更快地得出答案。不幸的是，它不能保证最少量的电阻器得到答案。它很可能会找到与较少工作量相对应的接近等效电阻值，并且可以进行加权以支持使用尽可能少的电阻器。

我将继续研究并发布我找到的任何其他信息。

- Alter

---

不是指数级的O，因为你的算法受到“迄今为止最佳结果”的限制。一旦你知道可以在3步内从A到达B，就不需要再检查了。这感觉非常像路径查找算法。 - Michael Dorgan

哦，很好，那么如果一个通常呈指数增长的O方程可以在一步中解决，那你怎么称呼它？ - Alter

可能是指数级的？ :) - Michael Dorgan