寻找 NP 难题的最佳解决方案的模拟求解器
- 研究人员构建了一个新系统，可以解决一个典型的离散优化问题，称为 MaxSAT。
- 此模拟求解器的性能优于数字计算机，并且还可以扩展到其他优化问题。
今天的数字计算机可以很好地执行大多数任务。它们非常适合某些计算、文字处理、网上冲浪和图形艺术。但由于它们依赖于二进制代码——0 和 1——它们并不适合解决所有问题。
数字计算几乎已达到其最大潜力，这就是为什么一些数学家开始对复兴模拟计算产生兴趣。它可以帮助推进超越数字框架的计算。
最近，罗马尼亚圣母大学和 Babes-Bolyai 大学的研究人员开发了一种新的模拟求解器，可以评估 NP 难题的最佳解决方案。
NP-hard 问题意味着没有算法可以在多项式时间内解决问题。获得解决方案所需的时间随着问题的大小呈指数增长。通常，这些问题与医学成像、生物信息学、蛋白质折叠和调度有关。
研究人员在各种 NP 难题上测试了他们的模拟求解器，他们发现这种新方法有可能在更短的时间内产生更好的解决方案。
为什么是模拟计算？
模拟计算机在 20 世纪中叶非常流行。每个关注动力学问题的大型管理部门和公司都有一个巨大的模拟计算中心。它们被用于向太空发射火箭、在战舰上引导武器以及模拟飞机动力学。
与数字计算机不同，模拟计算机使用非离散数据，如电压、重量、速度、温度和压力。由于它们使用连续值，因此它们不受量化噪声的影响。
可以设计模拟计算机来解决各种问题。它们可以直接执行数学运算。例如，从 3 中减去 8，模拟计算机减去对应于这些值的电压，然后立即提供正确的输出。
它们可用于实时操作和同时计算。在模拟问题的情况下，他们可以提供问题和错误的见解。并且由于它们不需要量化，因此非常适合信号调制/解调和高速电机控制。
参考：Nature Communications | doi:10.1038/s41467-018-07327-2 |圣母大学
然而，数字计算机在 1980 年代占领了市场。它们在执行一般任务时足够灵活、快速和准确。随着高效算法的出现，它们的性能变得更好。
老式模拟 AMF665D 计算机 |图片来源：弗朗西斯·马森 / YouTube
但是数字计算机，包括现代计算机，无法解决具有大变量的 NP 难题。大多数优化问题的难点在于您无法确定解决方案是否最优。确保没有更好的解决方案与问题本身一样困难。
高性能模拟求解器
新的连续时间动力系统可以解决一个典型的离散优化问题，称为 MaxSAT。该方法依赖于一组确定性的常微分方程和一种启发式技术，用于预测通过模拟时间 t 评估最优解的可能性。
在模拟电路中，冯诺依曼瓶颈被消除：电路本身充当处理器和存储器。另一方面，在数字计算机上实施该方法需要使用常微分方程积分器算法，该算法将连续时间方程离散化并在处理错误的同时逐步求解。
在数字形式中，求解器无法高效执行，因为动力学会演化出数千个耦合常微分方程，这是一个耗时的积分过程。
阅读：关于量子计算机最有趣的事实
而且由于该方法使用通用字符，因此也可以扩展到其他优化问题。研究人员计划基于这种新方法设计和制造设备。
工业技术