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 回答