总合并搜索优化

假设存在大小为N的向量VA，并且每个元素是另一个类型为T的向量。对类型T有一个操作并返回类型T的新值，即bool merge(T a, T b, T &ret);。如果a和c可以合并，则将结果存储在ret中并返回true;否则，返回false。合并操作具有反思性和传递性。总合并搜索优化

的溶液被发现如果任：

∃ X ，X ，...，X _N-1。合并（VA [0] [x ]，VA [1] [x ]，merge（VA [2] [x ]，...，merge（VA [N-2] [ x）[_N-2]，VA [N-1] [x _N-1]，ret）...））;
来自N-1（而不是N）子向量的任何元素都可以合并（选择任何N-1只有一个例外）。

例如： VA的大小为3.元素a可以与元素b合并，结果为c。元素c可以与元素d合并，结果为e。

VA [0] = {A}
VA [1] = {B，Q}
VA [2] = {d，R}

在所有溶液上面的例子是：{a，b}，{a，d}，{b，d}，{a，b，d}。

任务是找出给定矢量VA中的所有解。

我的C++代码是：

void findAll(unsigned int step, unsigned int size, const T pUnifier, int hole_id) { 
    if(step == size) printOneResult(pUnifier); 
    else { 
    _path[step] = -1; 
    findAll(step + 1, pUnifier, step); 
    } 
    std::vector<T> vec = VA[step]; 
    for(std::vector<T>::const_iterator it = vec.begin(); it < vec.end(); it++) { 
    T nextUnifier(); 
    if(merge(*it, pUnifier, nextUnifier)) { 
     _path[lit_id] = it->getID(); 
     findAll(step + 1, nextUnifier, hole_id); 
    } 
    } 
}

的代码包含递归调用;但是，它不是尾递归。它在实践中运行缓慢。实际上，VA的大小可能有数百个，每个子矢量大小也有数百个。我想知道它是否可以优化。

非常感谢。

来源

2012-12-22 Tianyi Liang

C++不会优化你的尾递归调用（至少不按照标准），所以这是一个小问题。你有没有看过你的循环？我想这就是大部分时间都花在哪里，因为你的迭代可以叠加起来。您正在循环并递归到另一个循环中，并且递归，无限。如果你可以减少一些循环，那么你可以节省大量的循环。不是说这是可能的（我没有仔细研究它），但是值得研究。 – RonaldBarzell

谢谢你的回复。这很难减少一些循环。这取决于排序，但很难找到一个好的排序启发式。也许，我可以考虑如何记住一些部分结果。 –

在进入findAll之前，您还可以查看是否有任何可对数据执行的操作，以便您可以使用某些快捷方式。 – RonaldBarzell

-1

为了改善你的代码，当你使用向量时，你应该使用[]运算符，而不是简单的迭代器，而是使用int计数器，这要慢得多。您可以通过最小化函数调用我的任何一个循环来改善它，就像先前堆叠您将使用的值一样。既然你没有解释过什么是T_VEC，我没有写完整的无迭代版本，但是这对速度应该已经是一个很大的优势了。

来源

2012-12-22 01:13:24 tsukasan

-1在发布版本中，你会非常难以找到一个现代标准库实现，它的'std :: vector <>'迭代器有任何开销。 – ildjarn

根据什么证据？最后我检查了一下，迭代器在索引上略有优势... – GManNickG

对于清除，'T_VEC'是'std :: vector '，'T'是一些复杂的数据结构（只是将其视为模板）。使用迭代器比'int'计数器更好。根据我以前的测试，我没有看到使用'int'计数器加速，另一方面，迭代器更方便。 –

如果我正确理解你的代码，你正在执行（递归）蛮力搜索。这是不高效的，因为您可以获得有关搜索空间的一些信息。

我认为这里的一个好的候选人将是A* algorithm。您可以使用当前最大链大小作为启发式，或者甚至可以使用链大小的平方和。

来源

2012-12-22 06:26:07 goncalopp

修剪搜索空间确实很难，实际上几乎每个搜索路径都是有用的。因此，我正在考虑优化递归结构本身。 –

总合并搜索优化

回答

相关问题