向量和運算符組合算法

Question

我試圖找到一個算法，將使用給定的一組運算符上給定的一組運算符的任何組合來達到目標​​向量。不惜一切代價，我想避免使用暴力，我相信這個問題有一個優雅的解決方案。

例問題：
鑑於矢量V1 = [0, -1]; V2 = [2, 1]; V3 = [-1, 0];
而運營商L1和L2。誰的行爲像L1[V1, V2] = V1 + V2; L2[V1, V2] = V1/V2
力爭達到目標矢量T = [-0.5, 0]

解決方案：
L1[V1, V2] = [0, -1] + [2, 1] = [2, 0]
L2[V3, L1[V1, V2]] = [-1, 0]/[2, 0] = [-0.5, 0]（0/0師向我指出，這是一個錯誤，但我認爲該解決方案，努力實現還算說得過去）

我試了一下：
我已經試過處理這個問題作爲一個vector combination problem，但我沒有figu弄清楚如何引入運營商列表。請讓我知道，如果我的術語不正確或混淆;任何幫助表示讚賞。

Answer 1

兩步算法怎麼樣？

1. 隨着給定的矢量V1, V2, V3 ...試圖解決線性方程：a1 * V1 + a2 * V2 + ... = T係數爲整數（不定方程）。而且所有的載體都可以放大到整數。該步驟對應於操作L1。
2. 展開組與操作L2載體，然後轉到步驟1.

Answer 2

假設有m個向量和n的運營商，並且假設每個運算符采用兩個矢量作爲操作數，併產生一個矢量作爲輸出。

我想出了一個在O（mn + mlog（m））時間運行的貪婪算法，但它的而不是保證找到最佳解決方案。它如下：

1. 根據它們的（平方）距離將矢量集合排序到目標矢量。這運行在O（mlog（m））時間內，只需要執行一次。

2. 從最接近目標的矢量集中選擇兩個矢量，並將它們從矢量集中移除。這從O（1）時間開始運行，因爲您要從數組的末尾移除2個項目（向量的排序數組）。

3. 將每個運算符應用於這兩個向量，並跟蹤哪個運算符產生與目標向量最接近的向量。這在O（n）時間運行。如果與目標矢量的最接近的矢量與其完全匹配，則退出算法。

4. 一旦確定了最接近的結果，將該向量插入到適當位置的向量集中，以便向量集保持排序。這可以在log（m）時間內完成。

5. 回去2.

由於，由步驟4的端部，矢量在矢量集的數量已經減少了1在步驟2相比，其數量，則處理是必然會終止。

整體運行時間是多少？步驟2至步驟4的總運行時間爲O（1）+ O（n）+ O（log（m））= O（n + log（m））以及這些步驟必須執行的次數被執行爲O（米），因此總，包括步驟1，是

O（MN +管理記錄（米））

當然，沿途需要存儲關於運營商和足夠的信息及其操作數導致與目標最接近的向量，因此您可以構建一個樹來表示操作符以及它們需要應用的順序。

這個算法的運行時間非常媲美用蠻力算法會嘗試符和操作數的每個組合的運行時間，因爲這顯然對向量集的大小指數。

Answer 3

這不是算法優雅，但可能有助於加快實現，一旦有人張貼了良好的算法答案：

由於每個載體（比如，大小n的）總是被處理爲一個整體，你可以減少矢量操作的數量由一個因子n/s確定。要做到這一點，只能在每個原始矢量的子矢量上執行（不管你最終使用哪種算法）（比如，第一個s元素）。

如果您的計算機體系結構無法處理整個向量，則至少可以節省處理向量中所有組件的計算工作。

由於您忽略了一些變量，這可能會產生誤報。所以你需要驗證你找到的解決方案。誤報的可能性可以通過s的大小和您使用的子集進行調整。

適用於你的例子：

V1 = [0, -1]; V2 = [2, 1]; V3 = [-1, 0]; 
L1[V1, V2] = V1 + V2; 
L2[V1, V2] = V1/V2 

僅使用s=1

V1' = [0]; V2' = [2]; V3 = [-1]; 
L1'[V1',V2'] = V1' + V2'; 
L2'[V1',V2'] = V1'/V2'; 

T = [-0.5]