我得到了以下要求,這些要求需要通過定義一組變量和一組對這些變量的約束來表述為 CSP 問題。但是,我無法為我的問題制定約束和變量。一些信息: 該問題的解決方案是一個賦值列表:[Var, A1, A2, A3] 其中Var是變量A1,A2,A3是有效賦值的有序序列。要求:每個變量都被賦予一個值 problem.valid_assignments()每個變量的第一個賦值在 problem.first_assignments()每個變量的賦值順序都在problem.valid_pairs()(有些賦值不能跟在其他的后面)給定一個整數K,最多只能有K連續的賦值,其中至少有一個不存在問題。k_assignment()給定分配列表中的每個值:problem.assignment必須使用。可用約束:NValues約束:給定一個 的列表required_values,一個上界和下界,確保其值在required_values界之間的變量數。AllDifferent約束:給定一組變量,強制執行它們的不等式。即集合中沒有兩個變量是相等的。NotEqual約束:給定Var1, Var2, 強制執行:Var1!=Var2迄今為止:每個Var域為的變量problem.valid_assignments()每個Var域為的變量problem.first_assignments()甲NValues每個約束Var其范圍[Var],所需的值problem.valid_assignments(Var),下限0,上限len(domain)。附加信息:該解決方案是一個“任務列表”中的每個Var我們回[Var, A1, A2, A3]哪里Var是可變分配,并且A1通過A3是滿足給定約束的有效分配。確切的格式并不重要,因為我只是在尋找一個概念性的解決方案。此外A1, A2, A3(又名 a 的所有賦值Var)顯然必須在該變量的域中。(域可以在變量之間重疊)。valid_pairs()返回元組列表[(A1, A2), (A2,A3)]。約束是這樣的,返回的解決方案列表(如上文詳述)必須具有連續分配,形成此函數給出的有效對。例如,如果解決方案是[Var, A1, A2, A4, A3]并且有效對是[(A1, A2), (A2,A3)]那么解決方案是不正確的,因為(A2, A4) (A4, A3)它不在列表中((A1, A2)但是是一個有效對)。本質上,我們正在尋找弧一致性。
1 回答

阿波羅的戰車
TA貢獻1862條經驗 獲得超6個贊
我們可以使用一個
NValues
約束,其范圍是所有變量,域是每個可能的賦值(為每個賦值創建一個約束)。這確保在設置為具有 1 的上限和下限時分配所有值。我們可以使用
Neq
帶有一些修改的use約束,通過提供有效分配的元組來確保正確的排序。我們可以再次使用
NValues
約束k_assignment
通過傳遞下限 1 和K
域上限來確保需求K_assignments
。以同樣的方式,我們可以將
NValues
約束與域problem.first_assignments()
用于第一次分配。另一個用域problem.valid_assignments()
來填空。
添加回答
舉報
0/150
提交
取消