2

すべて同じサイズの文字列のベクトルがあります。
ソリューションとして、いくつかの条件を満たす文字列のリストを作成する必要があります。

擬似コードアルゴリズムは次のようになります。

backtrack(N)
if solution_valid()
    print solution
else
    for each word in vector
        if(possible candidate)
           backtrack(N+1)

実際にコードを書く方法に迷いました。

現在のソリューションを保存する方法、関数に渡すパラメータの種類がわかりません...

これは私が持っているものですが、それは完全に間違っていると思います：

int backtrack(vector<string> &dictionary, vector<string> &solution, int current_row)
{
cout << "current row: "<< current_row <<  " of: " << rows << endl;
if(current_row == rows /*&& square_completed(solution)*/)
{
    vector<string>::iterator word;
    for(word = solution.begin(); word != solution.end(); ++word)
    {
        cout << *word << endl;

    }
    return 0;
}

vector<string>::iterator word;
for(word = dictionary.begin(); word != dictionary.end(); ++word)
{
    backtrack(dictionary,solution,current_row+1);
    solution.push_back(*word);


}

return 1;

}

問題は、ソリューションが制御なしで成長し続けることです。対処方法を教えてください。そして適切なバックトラックを行いますか？

4

1 に答える 1

1

1 つの問題は、それdictionaryを反復しながら変更することです。ベクトルを変更すると、そのベクトルの反復子が無効になるためword、次回使用するときに無効になります。これはクラッシュするか、失敗する可能性があります。しかし、erase関数は新しい有効な反復子を返します。それを使用して反復を続けることができます。

また、基本的にバックトラック関数ですべての要素を消去するdictionaryと、非常に高速に要素が残りませんdictionary。おそらく、再帰呼び出しが戻った後に、消去された要素を再度追加したいですか?

于 2011-02-05T19:31:15.720 に答える