6

我有许多可变大小的列表，其中包含具有属性 foo 的同一类的实例，并且对于每个列表，我必须应用以下规则：

  • 如果有一个元素 foo=A 则 [B,C,D] 中不能有带有 foo 的元素
  • 如果有一个元素 foo=X 必须至少有一个 foo 在 [Y,Z]
  • 可以在 MIN 和 MAX 元素之间存在 foo=BAR

结合以上三个规则可能足以表达我需要的任何类似约束。这有点像软件包中的依赖项检查，但我有数量并且缺少版本:)

一种天真的方法是：

R_CONFLICT={ A: [B,C,D] }
R_DEPENDS ={ X: [ [Y,Z], W, .. } # means: A depends on either Y or Z, and W
R_MIN     ={BAR: n, BAZ: m}
R_MAX     ={BAR: o, BAZ: p}
# now just loop over lists to check them..

这是约束编程的问题吗？我实际上不需要解决某些问题来获得结果，我需要根据一些约束验证我的列表并检查它们是否满足。你会如何分类这个问题，你会如何解决它？

对于它的价值，我正在用 Python 进行编码，但我欢迎一个通用的编程答案:) 如果事实证明我必须深入研究约束编程，我可能会从尝试python-constraint开始。

4

1 回答 1

4

简短的回答 - 是的，这可以使用约束编程来检查，实际上你是在提供一个解决方案并根据约束检查它，而不是让求解器搜索潜在域以找到匹配的解决方案。哪种类型的约束编程过度，特别是如果你使用 Python 可以很容易地检查这些条件。

我在这台机器上没有 Python，因此此代码中可能存在拼写错误/错误，但它显示了您所追求的内容，而无需参与约束编程。

conflict = set([B, C , D])
foos = set([x.foo for x in list])
if A in foos:
    if len(foos & conflict): #Set intersection
         return false

len([x for x in list where x.foo == BAR]) #Gives you number of occurances of BAR

基本上我会说除非约束会变得更加复杂，或者你想要找到解决方案而不是仅仅测试我会坚持使用代码而不是约束编程。

于 2010-09-13T14:35:57.867 回答