0

サイズ N のベクトル VA があり、各要素が型 T の別のベクトルであると仮定します。型 T に対する操作があり、型 T の新しい値、つまり を返しbool merge(T a, T b, T &ret);ます。a と c をマージできる場合は、結果を に格納してrettrue を返します。それ以外の場合は false を返します。マージ操作は反映的で推移的です。

次のいずれかの場合に解決策が見つかります。

  1. ∃ x 0 , x 1 , ..., x N-1 . merge(VA[0][x 0 ], VA[1][x 1 ], merge(VA[2][x 2 ], ..., merge(VA[N-2][x N-2 ], VA[N-1][x N-1 ],ret)...));
  2. N-1 ( N ではない) サブベクトルからの任意の要素をマージできます (厳密に 1 つの例外を除いて任意の 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 のサイズはおそらく数百であり、各サブベクトルのサイズも数百です。最適化できるか心配です。

どうもありがとうございました。

4

2 に答える 2

1

私があなたのコードを正しく理解していれば、あなたは (再帰的な) ブルートフォース検索を実行しています。検索スペースに関する情報が提供されるため、これは効率的ではありません。

ここでの良い候補はA* アルゴリズムだと思います。現在の最大チェーン サイズをヒューリスティックとして使用することも、チェーン サイズの二乗和を使用することもできます。

于 2012-12-22T06:26:07.827 に答える
-1

ベクトルを使用する場合、コードを改善するには、intはるかに遅い単純な反復子の代わりに [] 演算子をカウンターと共に使用する必要があります。以前に使用する値をスタックするように、ループのいずれかで関数呼び出しを最小限に抑えることで、さらに改善できます。T_VEC が実際に何であるかを説明していないので、完全なイテレータなしのバージョンを書くことはできませんでしたが、これはすでに速度に関して大きなプラスになっているはずです。

于 2012-12-22T01:13:24.813 に答える