最佳算法以最小化通過改變輸入數據

的輸出值I有數據的進入流和一組變換，其可被施加到所述流中的各種組合，以得到一個數字輸出值。我需要找到轉換的哪個子集使數量最小化。最佳算法以最小化通過改變輸入數據

的數據被附加到每一個與元數據數的有序列表。

這些轉換是準線性的：它們是以圖靈完備語言在技術上可執行的代碼，但它們被認爲屬於總是暫停的受限子集，並且它們通過算術運算將輸入數轉換爲輸出數，其流量取決於附加的元數據。而且，這些操作幾乎都是線性的（但它們並不一定是 - 這意味着這可能是優化的地方，但不是限制）。

基本上，蠻力方法涉及2個^ñ步驟（其中ñ是許多轉換）的工作，但它是可悲無效的，我幾乎可以絕對肯定這不會擴大生產。有沒有任何算法可以更快地解決這個問題？

2011-09-08 whitequark

n上的範圍是多少？ – Timmy

您是否可以在運行時訪問轉換的「代碼」？換句話說，你只是將變換作爲黑盒函數給出，還是以某種你可以評估的表達式的形式出現？如果您可以分析轉換，它可以包含哪些功能？ – StriplingWarrior

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

如果所有操作幾乎是線性的，你能不能用線性規劃啓發式？

也許在做之間一些檢查是否轉換是特別慢，在這種情況下，你仍然可以切換到蠻力。

你需要找到最佳的輸出？

2011-09-08 21:53:55 DaveFar

線性規劃對我來說過於嚴格，請參閱有關轉換格式問題的評論，並且實施兩種算法 - 線性規則和蠻力規則 - 是一項代價高且容易出錯的任務。我仍然可以使用它，但我想知道是否存在更好的解決方案。 – whitequark

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

如果您正在進行不合理的或非線性的優化，複雜性可能會非常快地上升。所以我會檢查你的決定因素是否有NP完全問題。 – DaveFar

回答