3

我正在编写一个简单的游戏，它将数据集存储在 2D 网格（如棋盘）中。网格中的每个单元格可能包含一个整数（0 表示单元格为空）。如果单元格包含一个大于 0 的数字，则称其为“已填充”。网格上的一组“填充”单元称为“配置”。

我的问题是能够“识别”特定的配置，而不管单元格的配置在 MxN 网格中的什么位置。

这个问题（在我看来）分为以下两个子问题：

  1. 以某种方式“规范化”配置的位置（例如，将其位置“重新定位”为（0,0），这样包含配置中所有单元格的最小矩形的左顶点在 MxN 网格中的（0,0）

  2. 计算某种相似性度量（或者可能只是设置差异？），以确定当前的“标准化”配置是否是已知配置之一（即“已识别”）

我怀疑我将需要使用 std::set （在我作为 C++ 编码员的所有岁月里，我还没有使用过的为数不多的 STL 容器之一！）。我将不胜感激之前解决过此类问题的任何人的任何想法/提示。任何代码片段、伪代码和/或链接都会非常有用。

4

7 回答 7

3

相似度指标是学术研究的一个重要领域。您需要确定您的任务所需的复杂程度。可能您可以简单地将“模板图案”拖过您的棋盘，光栅样式，并且对于每个位置得分 +1 表示命中，-1 表示未命中，然后将得分相加。然后找到模板得分最高的位置。然后这个 score_max 就是该模板的相似度指标。如果这种方法不合适，那么您可能需要更详细地了解游戏的确切性质。

于 2009-10-07T10:30:09.973 回答
1

也许您可以使用一些哈希函数来识别配置。由于即使模式不在棋盘上的同一位置，您也需要识别模式，因此此哈希不应取决于单元格的位置，而应取决于它们的组织方式。

如果您将 2D 网格存储在 1D 数组中，则需要找到第一个填充的单元格并从这里开始计算哈希，直到最后一个填充的单元格。

前任：

-----------------
|   |   |   |   |
-----------------
|   | X | X |   |
-----------------
|   |   | X |   |
-----------------
|   |   |   |   |
-----------------

----------------+---------------+---------------+----------------
|   |   |   |   |   | X | X |   |   |   | X |   |   |   |   |   |
----------------+---------------+---------------+----------------
                    |_______________________|
                                |
               Compute hash based on this part of the array

但是，在某些情况下这不起作用，例如当模式跨行移动时：

-----------------
|   |   |   | X |
-----------------
| X |   |   |   |
-----------------              Different configuration in 2D.
| X |   |   |   |
-----------------
|   |   |   |   |
-----------------

----------------+---------------+---------------+----------------
|   |   |   | X | X |   |   |   | X |   |   |   |   |   |   |   |
----------------+---------------+---------------+----------------
            |_______________________|
               Seems similar in 1D

所以你需要一些方法来处理这些情况。我还没有任何解决方案，但如果我的日程安排允许，我会尝试找到一些东西！

在考虑了一下之后，也许您可​​以对网格使用两种不同的表示形式：一种是将线附加到一维数组中，另一种是将列附加到一维数组中。哈希将使用这两种表示来计算，这将（我认为）解决上述问题。

于 2009-10-07T12:24:39.243 回答
0

至于问题的第一部分，即贬低试试这个：

用 2 个整数创建一个结构。声明该结构类型的指针。输入（或计算活细胞数量）并分配那么多存储空间（使用 calloc 等例程）。输入结构中的坐标。计算最小 x 坐标和最小 y 坐标。在宇宙中，将 [x][y] （用户给定值或当前坐标）分配给 [x-minx][y-miny] 虽然从已填充的网格中读取时很昂贵，但在问题的后续部分中有效并有所帮助.

于 2013-06-16T17:18:38.877 回答
0

这让我想起了使用 QuadTrees 的 HashLife。查看有关 HashLife 和 Quadtrees 的维基百科页面。

Wikipedia 页面底部还有一个链接，指向 DrDobbs 关于实际实现这种算法的文章：http ://www.ddj.com/hpc-high-performance-computing/184406478

我希望这些链接有所帮助。如果没有别的，它们很有趣。

于 2009-11-13T18:05:47.137 回答
0

这对于一个小型应用程序来说可能是多余的，但是 OpenCV 有一些出色的图像识别和 blob 查找例程。如果您将 2D 板视为图像，将整数视为亮度，则应该可以使用该库中的函数。

和链接： http: //opencv.willowgarage.com/documentation/index.html

于 2009-10-07T09:41:22.677 回答
0

听起来您想将棋盘输入经过训练以识别配置的神经网络。

这与图像分类的经典示例非常相似，唯一的复杂之处是您不知道您的配置将出现在网格中的确切位置，除非您总是考虑整个网格- 在这种情况下是经典 2层网络应该工作。

HTM 神经网络实现开箱即用地解决了偏移问题。从这里开始，您可以找到大量现成的实现。显然，您将不得不调整您将找到的实现，但您应该能够准确地实现您所要求的我的理解。

如果您想进一步研究这条路线，Numenta 论坛将是一个很好的起点。

于 2009-10-07T09:45:22.323 回答
0

你可以使用神经网络来完成这项工作。

如果您寻找神经网络形状识别，我认为您可以找到有用的东西。您可以找到大量可能对您有所帮助的库，但如果您对 NN 没有经验，这可能会有点困难，但我认为这是最简单的方法

于 2009-10-07T09:51:11.997 回答