1

假设我有一个无向多重图,即 (G, E) 对,其中 G 是节点的有限集,E 是边的有限集。我正在寻找一种算法,该算法将在以下约束下为每个节点分配一个字符串值。

1.

每个节点都有一组(可能是空的)限制允许值的约束。我想至少支持以下类型的值约束:

  • min-length(x) (该值至少是给定的字符数),
  • max-length(x) (该值最多为给定的字符数),
  • regexp(x)(值符合给定的正则表达式),
  • 数字(该值仅由数字组成)。

理想情况下,将来应该可以添加对新类型约束的支持。

2.

有两种类型的边缘:

  • 不同的,
  • 相同的,

意味着应该为相关节点分配不同/相同的值(意味着不相等/相等的字符串)。

3.

最后,可以为每个节点分配一组(可能为空)以下类型的约束:

  • 不同于(x),
  • 等于(x),

意味着给定节点应该被分配一个不同于或等于给定值的值。


我希望算法要么报告不一致(如果不存在这样的评估),要么返回任何符合标准的评估(理想情况下是一个小的,即分配的值由少量字符组成的)(否则) .


请注意,我不希望您为我提供算法的详细描述。如果您能提供任何提示,让我走上正轨,我将不胜感激。

4

1 回答 1

1

几点建议:

  • 您可以通过将由“相同”边连接的所有节点组合成一个节点来简化问题。(请注意,此单个节点的约束将是所有单个约束的并集。)

  • 减少的问题似乎与图形着色非常相似,因为您需要为每个节点选择标签,以便连接节点的标签不同。

  • 不幸的是,图形着色是 NP 完全的,因此除非您的节点数量非常少,否则您可能很难获得有效的算法

图形着色在计算上很困难。除了 k = 1 和 k = 2 的情况外,决定给定图是否允许给定 k 的 k 着色是 NP 完全的。特别是,计算色数是 NP 困难的。即使在 4 次平面图上,3 着色问题仍然是 NP 完全的

于 2013-07-03T17:56:54.777 回答