最佳算法以最小化通过改变输入数据

的输出值I有数据的进入流和一组变换，其可被施加到所述流中的各种组合，以得到一个数字输出值。我需要找到转换的哪个子集使数量最小化。最佳算法以最小化通过改变输入数据

的数据被附加到每一个与元数据数的有序列表。

这些转换是准线性的：它们是以图灵完备语言在技术上可执行的代码，但它们被认为属于总是暂停的受限子集，并且它们通过算术运算将输入数转换为输出数，其流量取决于附加的元数据。而且，这些操作几乎都是线性的（但它们并不一定是 - 这意味着这可能是优化的地方，但不是限制）。

基本上，蛮力方法涉及2个^ñ步骤（其中ñ是许多转换）的工作，但它是可悲无效的，我几乎可以绝对肯定这不会扩大生产。有没有任何算法可以更快地解决这个问题？

2011-09-08 whitequark

n上的范围是多少？ – Timmy

您是否可以在运行时访问转换的“代码”？换句话说，你只是将变换作为黑盒函数给出，还是以某种你可以评估的表达式的形式出现？如果您可以分析转换，它可以包含哪些功能？ – StriplingWarrior

@Timmy，可能高达50，但我需要做很多这些搜索，所以速度很重要。 – whitequark

如果所有操作几乎是线性的，你能不能用线性规划启发式？

也许在做之间一些检查是否转换是特别慢，在这种情况下，你仍然可以切换到蛮力。

你需要找到最佳的输出？

2011-09-08 21:53:55 DaveFar

线性规划对我来说过于严格，请参阅有关转换格式问题的评论，并且实施两种算法 - 线性规则和蛮力规则 - 是一项代价高且容易出错的任务。我仍然可以使用它，但我想知道是否存在更好的解决方案。 – whitequark

是的，输出需要最佳。 – whitequark

如果您正在进行不合理的或非线性的优化，复杂性可能会非常快地上升。所以我会检查你的决定因素是否有NP完全问题。 – DaveFar

回答