2

我正在开发一个程序来解决n皇后问题（将n棋皇后放在n x n棋盘上的问题，这样它们中的任何一个都无法使用标准棋皇后的移动来捕获任何其他棋子）。我正在使用启发式算法，它首先在每一行中放置一个皇后，然后从尚未被占用的列中随机挑选一列。我觉得这一步是一个优化的机会。这是代码（在 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);
    }

如果从代码中不清楚：我首先为每列构建一个包含整数的向量。然后，对于每一行，我在向量中选择一个随机条目，将其值分配给该行在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

您的一些问题的几个随机答案:)：

  1. 据我所知，如果不先迭代数组，就无法用连续值填充数组。但是，如果您真的只需要连续值，则不需要填充数组 - 只需使用单元格索引作为值：a[0] 为 0，a[100] 为 100 - 当您获得随机数时，请处理数字作为值。
  2. 您可以使用 list<> 实现相同的功能并删除您已经点击的单元格，或者...
  3. 为了获得更好的性能，而不是删除单元格，为什么不在它们中放置一个“已使用”的值（如 -1）并检查它。假设你得到一个像 73 这样的随机数，而 a[73] 包含 -1，你只会得到一个新的随机数。
  4. 最后，描述第 3 项让我想起了重新散列函数。也许您可以将您的算法实现为哈希表？
于 2009-08-15T22:21:29.373 回答
0

您的colsleft.erase(randplace);行确实效率低下，因为擦除向量中间的元素需要移动它之后的所有元素。在这种情况下，满足您需求的一种更有效的方法是简单地将元素与索引处的元素交换(size - i - 1)（在下一次迭代中其索引将超出范围的元素，因此我们将该元素“带入”中间，并且把用过的换掉）。

然后我们甚至不需要删除那个元素——数组的末尾会累积“选择的”元素。现在我们基本上实现了就地 Knuth shuffle。

于 2009-08-16T05:35:40.483 回答