如何在 C 中的整数数组中选择（有效）随机相邻点？

Question

假设我们有一个整数数组 (3x3)，如下所示：

+-+-+-+
| |1| |
+-+-+-+
|0|x|1|
+-+-+-+
| |0| |
+-+-+-+

上面的 (0,1) 设置为 1，(1,0) 设置为 0 等等。

现在假设我发现自己位于 (1,1)（位于 x ），对我来说，想出我可以采取的所有方向（比如所有值为 0 的方向）然后在其中选择一个的最简单方法是什么？

我遇到的麻烦实际上是选择所有有效方向然后在其中进行选择之间的步骤。我可以相当容易地分别完成这两个步骤，但我没有一个将这两个步骤结合起来的优雅的解决方案。

例如，我可以将每个单元格的值乘以代表 1、2、4 和 8 和/或它们的值。这将告诉我可以采取哪些方向，但如何在它们之间进行选择？另外，我可以轻松地随机化 1 到 4 之间的数字来选择方向，但如果该方向被“采用”，那么我必须再次随机化，但排除失败的方向。

有什么想法吗？

Answer 1

最快的解决方案可能是您发布的最后一个解决方案 - 随机选择方向，重复直到获得有效的方向。这最多需要四次尝试（最坏的情况是只有一个有效的邻居）。更优雅的方法是迭代所有可能的方向，在每个有效邻居处随机更新变量，例如此伪代码：

c = 1
r = invalid
for i in neighbors:
  if (valid[i]):
    if (rand() <= 1. / c): r = i
    ++c

然后 r 就是答案（c 是数字到目前为止发现的有效邻居）。

Answer 2

这是伪代码中一个非常巧妙的技巧

1. 将“当前结果”初始化为 nil
2. 将“找到的数字”初始化为 0
3. 循环遍历所有可能的方向。如果有效则：
   • 增加“找到的数量”
   • 将“当前结果”设置为概率为 1/“找到的数字”的方向

最后，您将得到一个有效的方向（如果没有找到，则为 nil）。如果有多个有效方向，则它们都会以相同的概率被选择。

Answer 3

假设：

每个位置都有一定数量的有效目标位置（某些位置的有效目标可能较少，国际象棋骑士放置在角落时的有效目标比放置在棋盘中间时的有效目标少。）

您想随机选择一个所有可用的有效动作的目标。

---

算法：

创建一个位数组，其中一位代表每个有效目标。 （在原始示例中，您将创建一个四位数组。）

对于每个有效目标，确定该位置是否为空；如果为空，则将位数组中的相应位设置为 1。

如果位数组> 0 则 number_of_targets = SUM(位数组)，否则返回（无有效移动）。

选择 1 到 number_of_targets 之间的随机数。

return（与位数组中第 n 个设置位关联的位置）

---

使用原始问题的示例：

X 有四个有效的移动。我们创建一个 4 位数组，并为每个空位置填充“1”；从正上方的单元格开始，沿顺时针方向移动，最终得到 :0:0:1:1：

位总和告诉我们有两个可以移动的位置。我们的随机选择将选择“1”或“2”。我们遍历位数组，直到找到第 n 个设置位并移动到该位置。

该算法适用于具有任意数量有效目标（不限于二维）的任何系统。您可以用递归返回最佳移动的函数（MIN-MAX 算法）替换随机数选择器。

Answer 4

一种稍微人为的方法可能是这样的（伪代码）：

1. 根据打开的邻居，按照您的描述构建位掩码。

2. 使用该位掩码作为以下数组的索引：

   <代码>
   结构随机数据
   {
   size_t num_directions;
   struct { 有符号 int dx, dy; } 增量[4];
   } random_data[16];

   其中 num_directions 是开放邻居的数量，deltas[] 告诉您如何到达每个邻居。

这有很多繁琐的数据，但它消除了循环和分支。

更新：好吧，由于某种原因，我在放弃这个想法时遇到了问题。我归咎于工作中对“数据驱动编程”的一定程度的灌输，因为这个非常简单的问题让我更好地“理解”了数据驱动的思想。这总是好的。

无论如何，这是使用上述想法的随机步进函数的完整、经过测试和工作的实现：

/* Directions are ordered from north and going clockwise, and assigned to bits:
 *
 *  3       2       1      0
 * WEST | SOUTH | EAST | NORTH
 *  8       4       2      1
*/
static void random_walk(unsigned int *px, unsigned int *py, unsigned max_x, unsigned int max_y)
{
    const unsigned int  x = *px, y = *py;
    const unsigned int  dirs = ((x > 0) << 3) | ((y < max_y) << 2) |
                               ((x < max_x) << 1) | (y > 0);
    static const struct
    {
        size_t  num_dirs;
        struct { int dx, dy; } deltas[4];
    } step_info[] = {
#define STEP_NORTH  { 0, -1 }
#define STEP_EAST   { 1, 0 }
#define STEP_SOUTH  { 0, 1 }
#define STEP_WEST   { -1, 0 }
    { 0 },
    { 1, { STEP_NORTH } },
    { 1, { STEP_EAST } },
    { 2, { STEP_NORTH, STEP_EAST } },
    { 1, { STEP_SOUTH } },
    { 2, { STEP_NORTH, STEP_SOUTH } },
    { 2, { STEP_EAST, STEP_SOUTH } },
    { 3, { STEP_NORTH, STEP_EAST, STEP_SOUTH } },
    { 1, { STEP_WEST } },
    { 2, { STEP_NORTH, STEP_WEST } },
    { 2, { STEP_EAST, STEP_WEST } },
    { 3, { STEP_NORTH, STEP_EAST, STEP_WEST } },
    { 2, { STEP_SOUTH, STEP_WEST } },
    { 3, { STEP_NORTH, STEP_SOUTH, STEP_WEST } },
    { 3, { STEP_EAST, STEP_SOUTH, STEP_WEST } },
    { 4, { STEP_NORTH, STEP_EAST, STEP_SOUTH, STEP_WEST } }
    };
    const unsigned int  step = rand() % step_info[dirs].num_dirs;

    *px = x + step_info[dirs].deltas[step].dx;
    *py = y + step_info[dirs].deltas[step].dy;
}

int main(void)
{
    unsigned int    w = 16, h = 16, x = w / 2, y = h / 2, i;
    struct timeval  t1, t2;
    double      seconds;

    srand(time(NULL));
    gettimeofday(&t1, NULL);
    for(i = 0; i < 100000000; i++)
    {
        random_walk(&x, &y, w - 1, h - 1);
    }
    gettimeofday(&t2, NULL);
    seconds = (t2.tv_sec - t1.tv_sec) + 1e-6 * (t2.tv_usec - t1.tv_usec);
    printf("Took %u steps, final position is (%u,%u) after %.2g seconds => %.1f Msteps/second\n", i, x, y, seconds, (i / 1e6) / seconds);

    return EXIT_SUCCESS;
}

一些解释可能是按顺序的，在您“理解”它之前，上面的内容相当不透明，我猜：

• 函数本身的接口应该说清楚。请注意，网格的宽度和高度表示为“max_x”和“max_y”，以便在检查当前位置是否位于边界上时节省一些常数减法或不。
• 变量 dirs 设置为“开放”行走方向的位掩码。对于空网格，除非位于边界上，否则该值始终为 0x0f。当然，可以通过测试地图来处理墙壁。
• step_info 数组收集有关可从 16 种可能的开放方向组合中采取哪些步骤的信息。读取每个struct 的初始化（每行一个）时，请考虑该结构的二进制索引，并将其转换为dirs 中的位。
• STEP_NORTH 宏（和朋友）减少了打字，并使发生的事情更加清晰。
• 我喜欢 random_walk() 的“核心”只是四个几乎清晰的表达式，令人耳目一新的是其中没有看到任何 if 。

当在我的 2.4 GHz x86_64 系统上使用 gcc (Ubuntu/Linaro 4.4.4-14ubuntu5) 4.4.5 进行编译时，使用优化级别 -O3，性能似乎略低于每秒 3600 万步。读取汇编的核心逻辑是无分支的。当然，有一个对 rand() 的调用，我不想一路走来并实现一个本地随机数生成器来内联。

注意：这并不能解决所提出的确切问题，但我认为该技术值得扩展。