假设我有一个无向多图，即 (G, E) 对，其中 G 是节点的有限集，E 是边的有限集。我正在寻找一种算法，该算法可以在以下约束下为每个节点分配一个字符串值。
1.
每个节点都被赋予一组(可能为空)限制允许值的约束。我希望至少支持以下类型的值约束:
- min-length(x)(该值至少为给定的字符数)，
- max-length(x)(该值最多为给定的字符数)，
- regexp(x)(值符合给定的正则表达式)，
- 数字(值仅由数字组成)。
理想情况下，将来应该可以添加对新型约束的支持。
2.
有两种边:
- 不同，
- 相同，
意味着相关节点应该被分配不同/相同的值(意味着不相等/相等的字符串)。
3.
最后可以为每个节点分配一组(可能为空)以下类型的约束:
- 不同于(x)，
- 等于(x),
意味着给定的节点应该被分配一个不同于或等于给定的值。
我希望算法要么报告不一致(如果不存在这样的评估)，要么返回任何符合标准的评估(理想情况下是一个小的，即分配的值由少量字符组成) (否则)。
请注意，我不希望您为我提供算法的详细描述。如果您能提供任何让我走上正轨的提示，我将不胜感激。
最佳答案
一些建议:
您可以通过将所有由“相同”边连接的节点合并为一个节点来简化问题。 (请注意，此单个节点的约束将是所有单独约束的并集。)
减少的问题似乎与 graph colouring 非常相似因为您需要为每个节点选择标签，以便连接节点的标签不同。
不幸的是，图形着色是 NP 完全的，因此除非您的节点数量非常少，否则您可能很难获得有效的算法
Graph coloring is computationally hard. It is NP-complete to decide if a given graph admits a k-coloring for a given k except for the cases k = 1 and k = 2. In particular, it is NP-hard to compute the chromatic number. The 3-coloring problem remains NP-complete even on planar graphs of degree 4
- 查看 greedy colouring algorithms 可能会有所帮助如果您不一定需要完美的解决方案
关于algorithm - 寻找一种算法来评估图形的节点，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/17454327/