我该如何编码这个问题？ (C++)
我正在编写一个简单的游戏，它将数据集存储在二维网格（如棋盘）中。网格中的每个单元格可以包含一个整数（0 表示该单元格为空）。如果单元格包含数字> 0，就说是“满了”。网格上“填充”的单元格集合称为“配置”。
我的问题是能够“识别”特定的配置，无论单元格的配置位于 MxN 网格中的哪个位置。
这个问题（在我看来）分为以下两个子问题：
以某种方式“规范化”配置的位置（例如将其位置“重新调整”为（0,0），这样最小的矩形包含配置中的所有单元格的左顶点位于 MxN 网格中的 (0,0)
计算某种相似性度量（或者可能只是设置差异？），以确定当前的“标准化”配置是否为已知配置之一（即“已识别”）
我怀疑我需要使用 std::set （在我作为 C++ 编码员的这些年里，迄今为止我还没有使用过的少数 STL 容器之一！）。我非常感谢以前解决过此类问题的任何人的任何想法/提示。任何代码片段、伪代码和/或链接确实非常有用。
I am writing a simple game which stores datasets in a 2D grid (like a chess board). Each cell in the grid may contain a single integer (0 means the cell is empty). If the cell contains a number > 0, it is said to be "filled". The set of "filled" cells on the grid is known as a "configuration".
My problems is being able to "recognize" a particular configuration, regardless of where the configuration of cells are in the MxN grid.
The problem (in my mind), breaks down into the following 2 sub problems:
Somehow "normalising" the position of a configuration (for e.g. "rebasing" its position to (0,0), such that the smallest rectangle containing all cells in the configuration has its left vertice at (0,0) in the MxN grid
Computing some kind of similarity metric (or maybe simply set difference?), to determine if the current "normalised" configuration is one of the known configurations (i.e. "recognized")
I suspect that I will need to use std::set (one of the few STL containers I haven't used so far, in all my years as a C++ coder!). I would appreciate any ideas/tips from anyone who has solved such a problem before. Any code snippets, pseudocode and/or links would be very useful indeed.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（7）
相似性度量是学术研究的一个重要领域。您需要决定您的任务需要什么复杂程度。您可能可以简单地将“模板模式”拖到棋盘上，采用光栅样式，对于每个位置，命中得分+1，未命中得分-1，然后将得分相加。然后找到模板得分最高的位置。这个 Score_max 就是该模板的相似度度量。如果这种方法不充分，那么您可能需要更详细地了解游戏的确切性质。
Similarity metrics are a massive area of academic research. You need to decide what level of sophistication is required for your task. It may be that you can simply drag a "template pattern" across your board, raster style, and for each location score +1 for a hit and -1 for a miss and sum the score. Then find the location where the template got the highest score. This score_max is then your similarity metric for that template. If this method is inadequate then you may need to go in to more detail about the precise nature of the game.
也许您可以使用一些哈希函数来识别配置。由于您需要识别模式，即使它们不在板上的同一位置，因此该散列不应取决于单元格的位置，而应取决于它们的组织方式。
如果将 2D 网格存储在 1D 数组中，则需要找到第一个填充的单元格并从此处开始计算哈希，直到最后一个填充的单元格。
例如：
但是，在某些情况下这不起作用，例如当图案跨行移动时：
因此您需要某种方法来处理这些情况。我还没有任何解决方案，但如果我的日程允许的话，我会尝试找到一些东西！
经过一番思考后，也许您可以对网格使用两种不同的表示形式：一种是将行附加到一维数组中，另一种将列附加到一维数组中。哈希将使用这两种表示来计算，这将（我认为）解决上面引发的问题。
Maybe you could use some hash function to identify configurations. Since you need to recognize patterns even if they are not at the same position on the board, this hash should not depend on the position of the cells but on the way they are organized.
If you store your 2D grid in a 1D array, you would need to find the first filled cell and start calculating the hash from here, until the last filled cell.
Ex:
However, there are cases where this won't work, e.g. when the pattern is shifted across lines:
So you'll need some way of dealing with these cases. I don't have any solution yet, but I'll try to find something if my schedule allows it!
After thinking a bit about it, maybe you could use two different representations for the grid: one where the lines are appended in a 1D array, and another one where the columns are appended in a 1D array. The hash would be calculated with these two representations, and that would (I think) resolve the problem evoked above.
对于小型应用程序来说，这可能有点大材小用，但 OpenCV 有一些出色的图像识别和斑点查找例程。如果将 2D 板视为图像，将整数视为亮度，则应该可以使用该库中的函数。
以及链接：
http://opencv.willowgarage.com/documentation/index.html
This may be overkill for a small application, but OpenCV has some excellent image recognition and blob finding routines. If you treat the 2D board as an image, and the integer as brightness, it should be possible to use functions from that library.
And the link:
http://opencv.willowgarage.com/documentation/index.html
你可以使用神经网络来完成这项工作。
如果您寻找神经网络形状识别，我认为您可以找到有用的东西。你可以找到大量的图书馆可以帮助你，但如果你没有神经网络的经验，这可能有点困难，但我认为这是最简单的方法
you can use a neural network for that job.
if you lookfor neural network shape recognition i think that you can find something usefull. you can find tons of library that may help you but if you have no experiece with NN this could be a little hard, but i think that is the easiest way
听起来您想将棋盘输入经过训练以识别配置的神经网络。
这与图像分类的经典示例非常相似，唯一的复杂之处是您不确切知道您的配置事物将出现在网格中的位置，除非您始终考虑整个网格 - 在这种情况下，经典的 2 层网络应该可以工作。
HTM 神经网络实现立即解决了偏移问题。您可以从 此处开始找到大量现成的实现。显然，您必须对您发现的实现进行大量调整，但根据我的理解，您应该能够准确地实现您所要求的目标。
如果您想进一步研究这条路线，Numenta 论坛将是一个很好的起点。
Sounds like you want to feed your chessboard to a neural network trained to recognize the configuration.
This is very similar to the classic examples of image classification, with the only complication being that you don't know exactly where your configuration thingy will appear in the grid, unless you're always considering the whole grid - in that case a classic 2 layers network should work.
HTM neural networks implementations solve the offset problem out-of-the-box. You can find plenty of ready-to-use implementations starting from here. Obviously you'll have to tweak the heck out of the implementations you'll find but you should be able to achieve exactly what you're asking for to my understanding.
If you want to further investigate this route the Numenta forum will be a good starting point.
这让我想起了使用四叉树的 HashLife。查看有关 HashLife 和四叉树的维基百科页面。
维基百科页面底部还有一个链接，指向有关实际实现此类算法的 DrDobbs 文章：http://www.ddj.com/hpc-high-performance-computing/184406478
我希望这些链接有所帮助。如果没有别的的话，它们读起来很有趣。
This reminds me of HashLife which uses QuadTrees. Check out the wikipedia pages on HashLife and Quadtrees.
There's also a link at the bottom of the Wikipedia page to a DrDobbs article about actually implementing such an algorithm: http://www.ddj.com/hpc-high-performance-computing/184406478
I hope those links help. They're interesting reads if nothing else.
至于问题的第一部分，即 debasing 尝试这样做：
创建一个包含 2 个整数的结构。声明该结构类型的指针。输入（或计算活细胞的数量）并分配足够的存储空间（使用 calloc 等例程）。输入结构中的坐标。计算最小 x 坐标和最小 y 坐标。在宇宙中，将 [x][y]（用户给定值或当前坐标）分配给 [x-minx][y-miny] 虽然从已填充的网格中读取数据时成本较高，但可以工作并有帮助在问题的后续部分。
As to the first part of question,i.e debasing try this:
make a structure with 2 integers .Declare a pointer of that struct type. Input (or compute number of live cells) and assign that much storage (using routines like calloc) .Input the coordinates in the structure. Compute the minimum x coordinate and minimum y coordinate. In the universe assign [x][y] (user given values or current coordinate) to [x-minx][y-miny] Though expensive when reading from an already filled grid,but works and helps in the subsequent part of the question.