8

我需要比较许多图表（最多几百万个图表比较），我想知道最快的方法是什么。

图的顶点最多可以有 8 个邻居/边，顶点的值可以是 0 或 1。旋转图仍然是相同的图，每个图都有相同数量的顶点。

图表可能如下所示：

图表示例

现在，我通过从第一个图中获取一个顶点并将其与第二个图中的每个顶点进行比较来比较图。如果我找到相同的顶点，那么我检查两个顶点的邻居是否相同，然后重复此操作，直到我知道图形是否相同。

这种方法太慢了。在不丢弃肯定不同的图的情况下，比较数千个图与大约一百个顶点需要 40 多秒。

我正在考虑为每个图表计算唯一值，然后只比较值。我试图这样做，但我只设法提出如果相等则图形可能相等的值，如果值不同则图形也不同。
如果我的程序比较这些值，那么它会在大约 2.5 秒内计算所有内容（这仍然太慢）。

将顶点添加到该图并更新边的最佳/最快方法是什么？现在我正在存储这个图，std::map< COORD, Vertex >因为我认为搜索顶点更容易/更快。
COORD 是游戏板上的顶点位置（顶点的位置与比较图形无关），顶点是：

struct Vertex
{
    Player player; // Player is enum, FIRST = 0, SECOND = 1
    Vertex* neighbours[8];
};

此图表示 Gomoku 的当前棋盘状态，在棋盘边缘环绕，棋盘大小为 n*n，其中 n 最大为 2^16。

我希望我在写这篇文章时没有犯太多错误。我希望有一个人可以帮助我。

4

4 回答 4

5

首先，您需要将每个图转换为一致的表示，这样做的自然方法是创建图的有序表示。

第一级排序是通过根据邻居的数量进行分组来实现的。

然后，通过将其邻居值（0 和 1）映射到二进制数上，对具有相同数量邻居的每组节点进行排序，然后使用该二进制数在组节点之间强制执行顺序。

然后，您可以使用散列函数以有序形式迭代每个组的每个节点。然后可以使用散列值来提供加速查找

于 2013-04-04T19:30:40.987 回答
3

您要解决的问题称为图同构。

问题出在 NP 中（尽管不知道它是否是 NP-Complete）并且没有找到它的多项式时间算法。

您描述的算法似乎需要指数时间。

于 2013-04-04T19:21:31.380 回答
1

我很抱歉，因为我还没有能力发表评论。这并不完全是一个答案，而是一个可能的优化建议。

我建议尝试记忆（存储所有发现不同的顶点对），以便下次比较这两个顶点时，您只需进行简单的查找和回复。这可能会提高性能（或恶化性能），具体取决于您拥有的图表类型。

于 2013-04-04T19:14:21.057 回答
0

您已经发现，检查同构可以通过检查一个边框的所有 n*n 移位乘以另一个边框的 8 次旋转来完成，因此具有O(n^3)复杂性。

这可以简化为O(n^2)。让我们只在一个方向上移动，比如移动x轴。然后我们只需要找到合适的y-offset。为此，我们将两个图的元素连接如下：

. . 1 .            0 . . 3
0 1 . .     =>     0 1 2 .     =>     0 3 0 1 2 0 2
. 0 . .            0 . 2 .
_______            
1 2 3 4            ^---- a 0 indicates start of a row

我们得到两个大小的数组，n我们必须检查一个是否是另一个的循环置换。为此，我们将数组 a 与其自身连接并搜索另一个。

例如，如果两个数组是a=0301202并且我们使用 KMP 或类似方法进行b=0203012搜索0203012，它会及时运行（我们可以摆脱整个预处理，因为第一个数组总是相同的）。03012020301202O(n + 2n)=O(n)

将此O(n)x-check 与ny-shifts 和8旋转相结合O(n^2)，通过使用O(n)额外的空间来提供整体复杂性。

于 2013-04-04T20:08:55.123 回答