2

私は、n 個のクイーン問題 (標準のチェス クイーンの動きを使用して、n個のチェス クイーンをn x nチェス盤に配置して、他のクイーンをキャプチャできないようにする問題)を解決するプログラムに取り組んでいます。私は発見的アルゴリズムを使用しており、各行に 1 つのクイーンを配置し、まだ占有されていない列からランダムに列を選択することから始めます。このステップは最適化の機会だと感じています。コードは次のとおりです (C++):

    vector<int> colsleft;

    //fills the vector sequentially with integer values
    for (int c=0; c < size; c++)
        colsleft.push_back(c);

    for (int i=0; i < size; i++)
    {
        vector<int>::iterator randplace = colsleft.begin() + rand()%colsleft.size();

        /* chboard is an integer array, with each entry representing a row
        and holding the column position of the queen in that row */

        chboard[i] = *randplace;
        colsleft.erase(randplace);
    }

コードから明らかでない場合: 各列の整数を含むベクトルを作成することから始めます。次に、行ごとに、ベクトル内のランダムなエントリを選択し、その値を .xml 内のその行のエントリに割り当てますchboard[]。次に、そのエントリをベクターから削除して、他のクイーンで使用できないようにします。

ベクトルの代わりに配列とポインターを使用できるメソッドに興味があります。それとも<list>？forループ以外に、ベクトルを順番に埋めるより良い方法はありますか? いくつかの提案を聞きたいです！

4

3 に答える 3

7

以下は、ニーズを満たす必要があります。

#include <algorithm>

...

int randplace[size];

for (int i = 0; i < size; i ++)
    randplace[i] = i;

random_shuffle(randplace, randplace + size);

必要に応じて、ベクターでも同じことができます。

ソース: http://gethelp.devx.com/techtips/cpp_pro/10min/10min1299.asp

于 2009-08-15T22:22:12.010 に答える
0

ベクトルcolsleft.erase(randplace);の途中にある要素を消去するには、その後の要素をすべてシフトする必要があるため、この行は非常に非効率的です。この場合のニーズを満たすより効率的なアプローチは、(size - i - 1)要素をインデックスの要素と単純に交換することです (インデックスが次の反復で範囲外になる要素なので、その要素を中央に「移動」し、使用済みのものを交換します）。

そして、わざわざその要素を削除する必要さえありません。配列の最後に「選択された」要素が蓄積されます。これで、基本的にインプレース Knuth シャッフルが実装されました。

于 2009-08-16T05:35:40.483 に答える
0

あなたの質問のいくつかに対するいくつかのランダムな回答:):

  1. 私の知る限り、最初に反復処理を行わずに配列に連続した値を入力する方法はありません。ただし、本当に連続した値が必要な場合は、配列を埋める必要はありません。値としてセル インデックスを使用するだけです。a[0] は 0 で、a[100] は 100 です。乱数を取得するときは、値としての数値。
  2. list<> を使用して同じことを実装し、既にヒットしたセルを削除するか、または...
  3. パフォーマンスを向上させるには、セルを削除するのではなく、セルに「既に使用されている」値 (-1 など) を入れて、それを確認してください。73 のような乱数を取得し、a[73] に -1 が含まれているとします。新しい乱数を取得するだけです。
  4. 最後に、項目 3 の説明で再ハッシュ関数を思い出しました。おそらく、アルゴリズムをハッシュテーブルとして実装できますか?
于 2009-08-15T22:21:29.373 に答える