通过改变输入数据来最小化输出值的最佳算法
我有一个传入的数据流和一组转换，可以将它们以各种组合应用于该流以获得数字输出值。我需要找到变换的哪个子集使数字最小化。
数据是一个有序的数字列表，每个数字都附加了元数据。
这些转换是准线性的：它们在技术上是图灵完备语言中的可执行代码，但已知它们属于始终停止的受限子集，并且它们通过算术运算将输入数转换为输出数，其流程是相关的关于附加的元数据。此外，操作几乎总是线性的（但它们不一定是线性的——这意味着这可能是优化的地方，但不是限制）。
基本上，涉及 2n 个步骤（其中 n 是许多转换）的强力方法是可行的，但它的效率非常低，而且我几乎绝对确定这不会扩大生产规模。有没有什么算法可以更快地解决这个任务？
I have an incoming stream of data and a set of transformations, which can be applied to the stream in various combinations to get a numerical output value. I need to find which subset of the transformation minimizes the number.
The data is an ordered list of numbers with metadata attached to each one.
The transformations are quasi-linear: they are technically executable code in a Turing-complete language, but they are known to belong to a restricted subset which always halts, and they transform the input number to output number with arithmetic operations, whose flow is dependent on metadata attached. Moreover, the operations are almost all the time linear (but they are not bound to be—meaning this may be a place for optimization, but not restriction).
Basically, a brute-force approach involving 2n steps (where n is a number of transformations) would work, but it is woefully ineffective, and I'm almost absolutely sure this would not scale in production. Are there any algorithms to solve this task faster?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
如果几乎所有操作都是线性的，那么您不能使用线性编程作为启发式方法吗？
也许在两者之间确实检查某些转换是否特别慢，在这种情况下您仍然可以切换到暴力。
您需要找到最佳输出吗？
If almost all operations are linear, can't you use linear programming as heuristics?
And maybe in between do checks whether some transformations are particularly slow, in which case you can still switch to brute force.
Do you need to find the optimal output?