5

我已经坐了将近一个星期了。这是PDF格式的问题。

到目前为止，我只能想到一个想法，但它失败了。这个想法是递归地创建在 O(num_of_connected_subgraphs) 中工作的所有连接子图，但这太慢了。

我真的很感激有人给我一个方向。我倾向于认为唯一的方法是动态编程，但我似乎无法弄清楚如何去做。

4

2 回答 2

2

好的，这是我提出的算法的概念描述：

  1. 在两个维度上形成一个从 -7 到 7 的 (x,y) 棋盘图数组，并将对手的棋子放在上面。

  2. 从第一行开始（最低 Y 值，-N）：

    • 枚举该行中第二个玩家棋子的所有可能组合，仅排除与对手棋子冲突的组合。

    • 对于这一行上的每个组合：--将连接的部分分组到单独的网络中，并将这些网络从 1 开始编号，升序

      --将行编码为向量，使用：

      = 0 for any unoccupied or opponent position
= (1-8) for the network group that that piece/position is in.

      -- 给每个这样的分组一个 1 的计数，并使用编码的向量作为它的键将它添加到字典/哈希集中

  3. 现在，对于随后的每一行，按升序 {y=y+1}：

    • 对于上一行字典中的每个条目：

      --如果条目正好有 1 个组，则将其 COUNT 添加到 TOTAL

      --枚举当前行中第二个玩家棋子的所有可能组合，仅消除与对手棋子冲突的组合。（更改：）您应该跳过此步骤的初始组合（所有条目都为零），因为上面的步骤实际上涵盖了它。对于当前行上的每个这样的组合：

      + produce a grouping vector as described above

+ compare the current row's group-vector to the previous row's 
  group-vector from the dictionary:

    ++ if there are any group-*numbers* from the previous row's 
      vector that are not adjacent to any gorups in the current
      row's vector, *for at least one value of X*, then skip 
      to the next combination.

    ++ any groups for the current row that are adjacent to any
      groups of the previous row, acquire the lowest such group
      number

    ++ any groups for the current row that are not adjacent to 
      any groups of the previous row, are assigned an unused
      group number

+ Re-Normalize the group-number assignments for the current-row's
  combination (**) and encode the vector, giving it a COUNT equal 
  to the previous row-vector's COUNT

+ Add the current-row's vector to the dictionary for the current
  Row, using its encoded vector as the key.  If it already exists,
  then add it's COUNT to the COUNT for the pre-exising entry

  4. 最后，对于字典中最后一行的每个条目：

    • 如果条目只有一组，则将其 COUNT 添加到 TOTAL

**：Re-Normalizing 只是意味着重新分配组号，以消除分组模式中的任何排列。具体来说，这意味着新的组号应按从左到右、从一个开始的递增顺序分配。因此，例如，如果您的分组向量在将 ot 分组到上一行后看起来像这样：

2 0 5 5 0 3 0 5 0 7 ...

它应该重新映射到这种正常形式：

1 0 2 2 0 3 0 2 0 4 ...

请注意，与本示例一样，在第一行之后，分组可以是不连续的。必须保留这种关系，因此在重新归一化中将两组“5”重新映射到相同的数字（“2”）。

好的，有几点注意事项：

A. 我认为这种方法是正确的，但我真的不确定，所以它肯定需要一些审查等。

B. 虽然很长，但还是很粗略。每个单独的步骤本身都是不平凡的。

C. 虽然有很多单独的优化机会，但整体算法仍然相当复杂。它比蛮力好得多，但即便如此，我的餐巾背面估计仍然在 N=7 的 (2.5 到 10)*10^11 操作左右。

所以它可能很容易处理，但距离在 3 秒内完成 74 个案例还有很长的路要走。我还没有阅读 Peter de Revaz 答案的所有细节，但他旋转“钻石”的想法可能适用于我的算法。虽然它会增加内部循环的复杂性，但它可能会将字典的大小（因此，要比较的分组向量的数量）减少多达 100 倍，尽管如果不实际尝试它真的很难说.

另请注意，这里没有任何动态编程。我想不出一个简单的方法来利用它，所以这可能仍然是改进的途径。

好的，我枚举了所有可能的有效分组向量以获得对上述 (C) 的更好估计，这将 N=7 的值降低到 O(3.5*10^9)。这要好得多，但仍然比您可能需要在 3 秒内完成 74 次测试要高出一个数量级。不过，这确实取决于测试，如果它们中的大多数都小于 N=7，它可能会成功。

于 2013-05-27T20:47:51.823 回答
1

这是解决此问题的方法的粗略草图。

首先注意格点需要|x|+|y| < N，这导致菱形从坐标 0,6 到 6,0，即每边有 7 个点。

如果您想象将这颗钻石旋转 45 度，您最终会得到一个 7*7 的正方形格子，这可能更容易想象。（虽然注意也有中间 6 高柱。）

例如，对于 N=3，原始格点为：

..A..
.BCD.
EFGHI
.JKL.
..M..

哪个旋转到

A   D   I
  C   H
B   G   L
  F   K
E   J   M

在（可能旋转的）格子上，我会尝试通过动态编程来解决计算在前 x 列中放置军队的方式数量的问题，这样最后一列是某个字符串（加上一个布尔标志来说明是否有一些点已放置）。

该字符串包含每个格点的数字。

0 represents an empty location
1 represents an isolated point
2 represents the first of a new connected group
3 represents an intermediate in a connected group
4 represents the last in an connected group

在算法过程中，字符串可以表示包含多个连接组的形状，但我们拒绝任何留下孤立连接组的转换。

放置所有列后，您只需计算最多具有一个连接组的字符串。

例如，下面形状的前 5 列的字符串是：

....+  = 2
..+++  = 3
..+..  = 0
..+.+  = 1
..+..  = 0
..+++  = 3
..+++  = 4

中间的 + 当前未连接，但可能会被稍后的列连接，因此仍需要跟踪。（在这个图中，我还假设了一个上/下/左/右 4 连接。旋转的格子应该真正使用对角连接，但我发现这有点难以可视化，我不完全确定它仍然是一种有效的方法有了这种连接性。）

我很欣赏这个答案并不完整（并且可以使用更多图片/解释），但也许它会促使其他人提供更完整的解决方案。

于 2013-05-26T18:09:29.687 回答