约束编程，适合从记录中提取一对多关系 [英] Constraint programming suitable for extracting OneToMany relationships from records
问题描述
也许有人可以帮助我解决Prolog或任何约束编程语言的问题。想象一个项目表（学校项目，学生与母亲一起做些事情）。每个项目都有一个或多个孩子参加。对于每个孩子，我们存储其名称和其母亲的名称。但是对于每个项目，只有一个单元格包含所有母亲，而一个单元格包含所有孩子。
Maybe someone can help me to solve a problem with Prolog or any constraint programming language. Imagine a table of projects (school projects where pupils do something with their mothers). Each project has one or more children participating. For each child we store its name and the name of its mother. But for each project there is only one cell that contains all mothers and one cell that contains all children. Both cells are not necessarily ordered in the same way.
示例：
+-----------+-----------+------------+
| | | |
| Project | Parents | Children |
| | | |
+-----------+-----------+------------+
| | | |
| 1 | Jane; | Brian; |
| | Claire | Stephen |
| | | |
+-----------+-----------+------------+
| | | |
| 2 | Claire; | Emma; |
| | Jane | William |
| | | |
+-----------+-----------+------------+
| | | |
| 3 | Jane; | William; |
| | Claire | James |
| | | |
+-----------+-----------+------------+
| | | |
| 4 | Jane; | Brian; |
| | Sophia; | James; |
| | Claire | Isabella |
| | | |
+-----------+-----------+------------+
| | | |
| 4 | Claire | Brian |
| | | |
+-----------+-----------+------------+
| | | |
| 5 | Jane | Emma |
| | | |
+-----------+-----------+------------+
我希望这个例子能使问题可视化。正如我所说的，两个单元格仅包含用定界符分隔的名称，但不一定以类似的方式进行排序。因此，对于技术应用程序，您可以将数据转换为：
I hope this example visualizes the problem. As I said both cells only contain the names separated by a delimiter, but are not necessarily ordered in a similar way. So for technical applications you would transform the data into this:
+-------------+-----------+----------+
| Project | Name | Role |
+-------------+-----------+----------+
| 1 | Jane | Mother |
+-------------+-----------+----------+
| 1 | Claire | Mother |
+-------------+-----------+----------+
| 1 | Brian | Child |
+-------------+-----------+----------+
| 1 | Stephen | Child |
+-------------+-----------+----------+
| 2 | Jane | Mother |
+-------------+-----------+----------+
| 2 | Claire | Mother |
+-------------+-----------+----------+
| 2 | Emma | Child |
+-------------+-----------+----------+
| 2 | William | Child |
+-------------+-----------+----------+
| | | |
| |
| And so on |
每个项目的父母和子女人数相等。因此，对于每笔交易，我们都有n个母亲和n个孩子，每个母亲恰好属于一个孩子。有了这些限制，就可以从仅涉及一个孩子（即4和5）的项目开始，通过逻辑推理将每个母亲分配给她的所有孩子。
The number of parents and children is equal for each project. So for each deal we have n mothers and n children and each mother belongs to exactly one child. With these constraints it is possible to assign each mother to all of her children by logical inference starting with the projects that involve only one child (i.e. 4 and 5).
结果：
简有艾玛，斯蒂芬和詹姆斯；
Jane has Emma, Stephen and James;
克莱尔有布莱恩和威廉；
Claire has Brian and William;
Sophia拥有Isabella
Sophia has Isabella
我想知道如何使用约束编程来解决这个问题。此外，数据集可能不确定，我想知道是否有可能隔离出记录，这些记录在手动求解时（即当手动完成母子分配时）会破坏不确定性。
I am wondering how this can be solved using constraint programming. Additionally, the data set might be underdetermined and I am wondering if it is possible to isolate records that, when solved manually (i.e. when the mother-child assignments are done manually), would break the underdetermination.
推荐答案
我不确定我是否了解问题的所有要求，但这是MiniZinc中的约束编程模型（ http://www.minizinc.org/ ）。完整模型在此处： http://hakank.org/minizinc/one_to_many.mzn 。
I'm not sure if I understand all the requirements of the problem, but here is a constraint programming model in MiniZinc (http://www.minizinc.org/). The full model is here: http://hakank.org/minizinc/one_to_many.mzn .
最新注释：项目约束的第一个版本在不正确的地方。我删除了不正确的代码。
LATER NOTE: The first version of the project constraints where not correct. I have removed the incorrect code . See the edit history for the original answer.
enum mothers = {jane,claire,sophia};
enum children = {brian,stephen,emma,william,james,isabella};
% decision variables
% who is the mother of this child?
array[children] of var mothers: x;
solve satisfy;
constraint
% All mothers has at least one child
forall(m in mothers) (
exists(c in children) (
x[c] = m
)
)
;
constraint
% NOTE: This is a more correct version of the project constraints.
% project 1
(
( x[brian] = jane /\ x[stephen] = claire) \/
( x[stephen] = jane /\ x[brian] = claire)
)
/\
% project 2
(
( x[emma] = claire /\ x[william] = jane) \/
( x[william] = claire /\ x[emma] = jane)
)
/\
% project 3
(
( x[william] = claire /\ x[james] = jane) \/
( x[james] = claire /\ x[william] = jane)
)
/\
% project 4
(
( x[brian] = jane /\ x[james] = sophia /\ x[isabella] = claire) \/
( x[james] = jane /\ x[brian] = sophia /\ x[isabella] = claire) \/
( x[james] = jane /\ x[isabella] = sophia /\ x[brian] = claire) \/
( x[brian] = jane /\ x[isabella] = sophia /\ x[james] = claire) \/
( x[isabella] = jane /\ x[brian] = sophia /\ x[james] = claire) \/
( x[isabella] = jane /\ x[james] = sophia /\ x[brian] = claire)
)
/\
% project 4(sic!)
( x[brian] = claire) /\
% project 5
( x[emma] = jane)
;
output [
"\(c): \(x[c])\n"
| c in children
];
唯一的解决方案是
brian: claire
stephen: jane
emma: jane
william: claire
james: jane
isabella: sophia
Edit2：这是一个更通用的解决方案。有关完整模型，请参见 http://hakank.org/minizinc/one_to_many.mzn 。
Here is a more general solution. See http://hakank.org/minizinc/one_to_many.mzn for the complete model.
include "globals.mzn";
enum mothers = {jane,claire,sophia};
enum children = {brian,stephen,emma,william,james,isabella};
% decision variables
% who is the mother of this child?
array[children] of var mothers: x;
% combine all the combinations of mothers and children in a project
predicate check(array[int] of mothers: mm, array[int] of children: cc) =
let {
int: n = length(mm);
array[1..n] of var 1..n: y;
} in
all_different(y) /\
forall(i in 1..n) (
x[cc[i]] = mm[y[i]]
)
;
solve satisfy;
constraint
% All mothers has at least one child.
forall(m in mothers) (
exists(c in children) (
x[c] = m
)
)
;
constraint
% project 1
check([jane,claire], [brian,stephen]) /\
% project 2
check([claire,jane],[emma,william]) /\
% project 3
check([claire,jane],[william,james]) /\
% project 4
check([claire,sophia,jane],[brian,james,isabella]) /\
% project 4(sic!)
check([claire],[brian]) /\
% project 5
check([jane],[emma])
;
output [
"\(c): \(x[c])\n"
| c in children
];
此模型使用以下谓词来确保考虑母亲和孩子的所有组合：
This model use the following predicate to ensure that all the combinations of mothers vs children are considered:
predicate check(array[int] of mothers: mm, array[int] of children: cc) =
let {
int: n = length(mm);
array[1..n] of var 1..n: y;
} in
all_different(y) /\
forall(i in 1..n) (
x[cc[i]] = mm[y[i]]
)
;
它使用全局约束 all_different（y）确保 mm [y [i]] 是 mm 的母亲之一，然后分配`我是那个特定母亲的孩子。
It use the global constraint all_different(y) to ensure that mm[y[i]] is one of the mothers in mm, and then assign the `i'th child to that specific mother.
这篇关于约束编程，适合从记录中提取一对多关系的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
