返回首页
24小时热榜
这个项目的起始点是我决定编写一个自动布线器，比起手动为一个8000多个网络的背板布线要容易得多。<p>这是一个KiCad插件，包含几种不同的算法，其中最酷的是一种“曼哈顿布线网格”自动布线器，它沿着正交轨迹进行布线。基本思路是借用FPGA布线的算法并将其应用于PCB。我正在使用CuPy来加速布线；与GPU版本相比，CPU版本的速度至少慢10倍。<p>目前这个项目处于非常早期的开发阶段，但它在技术上是可行的。虽然从任何标准来看都不算优秀，但毕竟它是一个自动布线器。<p>我有一篇关于其制作过程和原因的文章：<a href="https://bbenchoff.github.io/pages/OrthoRoute.html" rel="nofollow">https://bbenchoff.github.io/pages/OrthoRoute.html</a><p>还有一段视频展示它在2分钟多一点的时间内为一个512网络的背板布线：<a href="https://www.youtube.com/watch?v=KXxxNQPTagA" rel="nofollow">https://www.youtube.com/watch?v=KXxxNQPTagA</a><p>这非常酷，也是几个月前发布的KiCad IPC API的首次良好应用之一。如果这听起来有趣且有用，欢迎提出PR和问题。
受到另一篇帖子启发。我在2019年做过类似的事情，但那是为了通过游戏学习荷兰语，最初是为我的孩子制作的，但这也帮助我记住了很多A2级别的单词，并且对我的考试有帮助。现在我已经获得了荷兰国籍。<p><a href="https://play.google.com/store/apps/developer?id=Joel+Bryan+Juliano">https://play.google.com/store/apps/developer?id=Joel+Bryan+J...</a>
当我开始为我的代数引擎 RomiMath 用 TypeScript 实现布赫伯格算法时，我发现了一个令人惊讶的事实：这个被认为是计算代数中最复杂的算法之一，实际上只是纯粹的机械操作。
让我们一步一步地将其简化为易于理解的内容，不做不必要的抽象。
1. 单项式（简单明了）
单项式就是一个项。加法（+）和减法（-）将单项式分开。
示例：25<i>4 + 15</i>x - 2 有 3 个单项式。
在代码中：
```typescript
class Monomial {
coefficient: number; // 例如，5，-2
variables: string[]; // 例如，['x', 'y']
exponents: number[]; // 例如，[2, 1] 表示 x²y
}
```
2. 次数（超级简单）
次数就是指数的总和：
```
3x²y → 次数 = 2 + 1 = 3
5x → 次数 = 1
7 → 次数 = 0
```
3. 词典顺序（比看起来简单）
这就像在字典中排列单词：
```
x > y > z > w
x³ > x²y¹⁰⁰⁰ (因为 3 > 2)
x²y > x²z (因为 y > z)
xy > x (因为它有更多的变量)
```
4. 布赫伯格算法（逐步解析）
步骤 1：取两个多项式
P1: x² + y - 1
P2: x + y² - 2
步骤 2：查看它们的“主项”
```
LT(P1) = x² (因为 x² > y > -1)
LT(P2) = x (因为 x > y² > -2)
```
步骤 3：计算这些项的“最小公倍数”
```
LCM(x², x) = x² (指数的最大值：max(2,1) = 2)
```
步骤 4：进行“智能减法”（S-多项式）
```
S(P1,P2) = (x²/x²)P1 - (x²/x)P2
= (1)(x² + y - 1) - (x)(x + y² - 2)
= (x² + y - 1) - (x² + xy² - 2x)
= -xy² + 2x + y - 1
```
步骤 5：与已有的结果进行简化
```
尝试使用 P1 和 P2 来简化结果
如果不能简化为零 → 新多项式！
```
步骤 6：重复直到没有新项出现
真正的精髓
布赫伯格算法实际上就是：
```
while (还有对) {
1. 取两个多项式
2. 进行它们的“智能减法”
3. 简化结果
4. 如果还有新项，添加到基底
}
```
这并不比跟随食谱复杂。
为什么这很重要
我在 TypeScript 中实现了这个算法，现在它可以在浏览器中在几秒钟内解决 7 个变量的系统。复杂性并不在于理解算法，而在于克服对数学符号的恐惧。
当你将“高级”概念分解为机械操作时，一切都变得可接近。
有没有其他人也有过这样的经历：发现一个“复杂”的概念实际上在分解后变得简单？