向量和运算符组合算法

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]