0

假设有一个大小为 N 的向量 VA，每个元素都是另一个类型为 T 的向量。对类型 T 进行一个操作并返回一个类型为 T 的新值，即bool merge(T a, T b, T &ret);。如果a和c可以合并，则将结果存入ret并返回true；否则，返回假。合并操作是反射和传递的。

如果出现以下任一情况，则可以找到解决方案：

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

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

  • VA[0] = {一个}
  • 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 的大小可能是数百，每个子向量的大小也可能是数百。我想知道它是否可以优化。

非常感谢。

4

2 回答 2

1

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

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

于 2012-12-22T06:26:07.827 回答
-1

为了改进您的代码，当您使用向量时，您应该使用 [] 运算符，使用int计数器而不是简单的迭代器，这要慢得多。您可以通过最小化任一循环中的函数调用来进一步改进它，就像之前堆叠您将使用的值一样。由于您没有解释什么是真正的 T_VEC，我不能不编写完整的无迭代器版本，但这应该已经是速度方面的一大优势。

于 2012-12-22T01:13:24.813 回答