用于将向量与 "don't cares?" 合并的快速数据结构
Fast data structure for merging vectors with "don't cares?"
我有一个相当大的集合，包含 n 个具有整数坐标的 d 维向量（d 大约为 50），除了在某些情况下坐标是一个特殊的哨兵 "don't care" 值，我将表示经过 *。我正在尝试找到一种有效的算法，用于将所有比较相等的向量合并在一起，其中 "equal" 表示 "each pair of coordinates in the vectors match, assuming that * entries can match anything." 例如，给定这些行向量：
[* 1 2 * *]
[1 1 * 2 *]
[2 1 3 * 1]
[2 * 3 * *]
[1 * 3 4 *]
我们将它们分成这些集群：
[* 1 2 * *], [1 1 * 2 *]
[2 1 3 * *], [2 * 3 * *]
[1 * 3 4 *]
要求是所有聚类中的所有向量都必须成对等效。可能有很多方法可以将满足这些条件的事物聚类在一起，因此对于 "not too many" 的一些松散定义，应该有 "not too many" 个聚类。
当然可以通过成对比较所有向量并将匹配的向量配对，然后重复此操作直到所有向量聚类。另一种选择（我们目前正在使用的那个）是从它自己的集群中的第一个向量开始，然后对于每个向量按顺序检查它是否匹配任何现有的集群或者它是否需要进入自己的集群。这些方法要么是二次的，要么是 运行 在时间上与向量数乘以簇数的乘积成正比，这对于我们的应用程序来说不够快。
是否有解决此特定问题的有效算法？
所以看起来这个问题是 NP-hard - 不仅是 NP-hard，它还是 NP-hard 之一=34=]NP-很难得到近似答案的难题。
为了说明这一点，这里是从色数问题（给定一个图形，给它着色所需的最少颜色数是多少？）到这个问题的快速简化。我将举例说明。假设我们有这张图：
A -- B -- C
| | |
D -- E -- F
我将从这张图开始，形成一组带有 "don't cares" 的向量，这样每个簇对应一组节点，它们之间没有边 运行（一个独立的集合).总的来说，每个聚类将代表一组可以赋予相同颜色的节点，因此找到最小聚类对应于找到图的色数。
由于图中有六个节点，每个向量将有六个分量。我们将为图中的每个节点形成一个向量。例如，节点 A 的向量将为
[ 0 1 * 1 * * ]
向量的列依次指代节点 A、B、C、D、E 和 F。A 列中的 0 表示 "this is the vector for A."B 列中的 1 和D 表示 "there are edges from this node to nodes B and D." 其他列中的 * 表示 "there aren't any edges running between this node and those other nodes." 如果我们为图中的所有节点形成向量集，我们将得到：
A B C D E F
A: [ 0 1 * 1 * * ]
B: [ 1 0 1 * 1 * ]
C: [ * 1 0 * * 1 ]
D: [ 1 * * 0 1 * ]
E: [ * 1 * 1 0 1 ]
F: [ * * 1 * 1 0 ]
现在，想象一下尝试对这些向量进行聚类。请注意，如果您采用任意两个相邻节点（例如 B 和 E），它们的向量将不匹配，因为 B 向量在 B 列中有一个 0，而 E 向量在 B 列中有一个 1。但是，如果您采用任何不相邻的节点，那么它们将匹配，因为
- 节点本身的列在一个向量中有 0 而在另一个向量中有 *，因为每个向量都标记有它是哪个节点并且它们之间没有边 运行，并且
- 每个向量中的每一列都是 1 或 *。
总的来说，这意味着一组向量对应于一组节点，它们之间没有边 运行，因此找到最小聚类可以为图形着色。在这种情况下，请注意，通过使 A、C 和 E 为相同颜色而 B、D 和 F 为另一种颜色，原始图形可以是二色的。如果我们查看向量，它们可以聚类为 A、C 和 E 以及 B、D 和 F：
A B C D E F
A: [ 0 1 * 1 * * ]
C: [ * 1 0 * * 1 ]
E: [ * 1 * 1 0 1 ]
B: [ 1 0 1 * 1 * ]
D: [ 1 * * 0 1 * ]
F: [ * * 1 * 1 0 ]
更一般地说，给定一个有 n 个节点的图，形成 n 个这种形式的向量，其中每个向量对应一个节点，该节点的列中有一个 0，每个相邻节点的列中有一个 1，和所有其他列中的 *。最小簇数对应原图的色数，这个缩减可以在多项式时间内完成。
问题是找到图的最小色数的问题是 NP-hard 并且没有已知的近似算法可以接近常数因子近似。因此，除非 P = NP.
否则我描述的原始问题可能没有好的近似算法
有可能我需要解决的问题的特殊情况恰好更容易近似，所以我可能 post 提出一个后续问题，其中包含我正在尝试做的事情的更多细节。
我有一个相当大的集合，包含 n 个具有整数坐标的 d 维向量（d 大约为 50），除了在某些情况下坐标是一个特殊的哨兵 "don't care" 值，我将表示经过 *。我正在尝试找到一种有效的算法，用于将所有比较相等的向量合并在一起，其中 "equal" 表示 "each pair of coordinates in the vectors match, assuming that * entries can match anything." 例如，给定这些行向量：
[* 1 2 * *]
[1 1 * 2 *]
[2 1 3 * 1]
[2 * 3 * *]
[1 * 3 4 *]
我们将它们分成这些集群：
[* 1 2 * *], [1 1 * 2 *]
[2 1 3 * *], [2 * 3 * *]
[1 * 3 4 *]
要求是所有聚类中的所有向量都必须成对等效。可能有很多方法可以将满足这些条件的事物聚类在一起，因此对于 "not too many" 的一些松散定义，应该有 "not too many" 个聚类。
当然可以通过成对比较所有向量并将匹配的向量配对，然后重复此操作直到所有向量聚类。另一种选择（我们目前正在使用的那个）是从它自己的集群中的第一个向量开始，然后对于每个向量按顺序检查它是否匹配任何现有的集群或者它是否需要进入自己的集群。这些方法要么是二次的，要么是 运行 在时间上与向量数乘以簇数的乘积成正比，这对于我们的应用程序来说不够快。
是否有解决此特定问题的有效算法？
所以看起来这个问题是 NP-hard - 不仅是 NP-hard，它还是 NP-hard 之一=34=]NP-很难得到近似答案的难题。
为了说明这一点，这里是从色数问题（给定一个图形，给它着色所需的最少颜色数是多少？）到这个问题的快速简化。我将举例说明。假设我们有这张图：
A -- B -- C
| | |
D -- E -- F
我将从这张图开始，形成一组带有 "don't cares" 的向量，这样每个簇对应一组节点，它们之间没有边 运行（一个独立的集合).总的来说，每个聚类将代表一组可以赋予相同颜色的节点，因此找到最小聚类对应于找到图的色数。
由于图中有六个节点，每个向量将有六个分量。我们将为图中的每个节点形成一个向量。例如，节点 A 的向量将为
[ 0 1 * 1 * * ]
向量的列依次指代节点 A、B、C、D、E 和 F。A 列中的 0 表示 "this is the vector for A."B 列中的 1 和D 表示 "there are edges from this node to nodes B and D." 其他列中的 * 表示 "there aren't any edges running between this node and those other nodes." 如果我们为图中的所有节点形成向量集，我们将得到：
A B C D E F
A: [ 0 1 * 1 * * ]
B: [ 1 0 1 * 1 * ]
C: [ * 1 0 * * 1 ]
D: [ 1 * * 0 1 * ]
E: [ * 1 * 1 0 1 ]
F: [ * * 1 * 1 0 ]
现在，想象一下尝试对这些向量进行聚类。请注意，如果您采用任意两个相邻节点（例如 B 和 E），它们的向量将不匹配，因为 B 向量在 B 列中有一个 0，而 E 向量在 B 列中有一个 1。但是，如果您采用任何不相邻的节点，那么它们将匹配，因为
- 节点本身的列在一个向量中有 0 而在另一个向量中有 *，因为每个向量都标记有它是哪个节点并且它们之间没有边 运行，并且
- 每个向量中的每一列都是 1 或 *。
总的来说，这意味着一组向量对应于一组节点，它们之间没有边 运行，因此找到最小聚类可以为图形着色。在这种情况下，请注意，通过使 A、C 和 E 为相同颜色而 B、D 和 F 为另一种颜色，原始图形可以是二色的。如果我们查看向量，它们可以聚类为 A、C 和 E 以及 B、D 和 F：
A B C D E F
A: [ 0 1 * 1 * * ]
C: [ * 1 0 * * 1 ]
E: [ * 1 * 1 0 1 ]
B: [ 1 0 1 * 1 * ]
D: [ 1 * * 0 1 * ]
F: [ * * 1 * 1 0 ]
更一般地说，给定一个有 n 个节点的图，形成 n 个这种形式的向量，其中每个向量对应一个节点，该节点的列中有一个 0，每个相邻节点的列中有一个 1，和所有其他列中的 *。最小簇数对应原图的色数，这个缩减可以在多项式时间内完成。
问题是找到图的最小色数的问题是 NP-hard 并且没有已知的近似算法可以接近常数因子近似。因此，除非 P = NP.
否则我描述的原始问题可能没有好的近似算法有可能我需要解决的问题的特殊情况恰好更容易近似，所以我可能 post 提出一个后续问题，其中包含我正在尝试做的事情的更多细节。