prolog - 适用于从记录中提取 OneToMany 关系的约束编程

问题描述

也许有人可以帮助我解决 Prolog 或任何约束编程语言的问题。想象一张项目表（学生与母亲一起做某事的学校项目）。每个项目都有一名或多名儿童参与。对于每个孩子，我们存储它的名字和它的母亲的名字。但是对于每个项目，只有一个包含所有母亲的单元格和一个包含所有孩子的单元格。两个单元格不一定以相同的方式排序。

例子：

+-----------+-----------+------------+
|           |           |            |
|   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     |
|           |           |            |
+-----------+-----------+------------+

我希望这个例子能直观地看到这个问题。正如我所说，两个单元格只包含由分隔符分隔的名称，但不一定以类似的方式排序。因此，对于技术应用程序，您可以将数据转换为：

+-------------+-----------+----------+
|   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）的项目开始的逻辑推理将每个母亲分配给她的所有孩子。

结果：

简有艾玛、斯蒂芬和詹姆斯；

克莱尔有布赖恩和威廉；

索菲亚有伊莎贝拉

我想知道如何使用约束编程来解决这个问题。此外，数据集可能未确定，我想知道是否可以隔离在手动解决时（即手动完成母子分配时）会打破未确定的记录。

标签： prologconstraintsconstraint-programming

解决方案

我不确定我是否理解问题的所有要求，但这是 MiniZinc ( http://www.minizinc.org/ ) 中的约束编程模型。完整模型在这里：http ://hakank.org/minizinc/one_to_many.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;


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。

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
];

该模型使用以下谓词来确保考虑所有母亲与孩子的组合：

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，然后将第 i 个孩子分配给那个特定的母亲。

prolog - 适用于从记录中提取 OneToMany 关系的约束编程

问题描述

解决方案

推荐阅读