MiniZinc 中的通道是什么?你能提供一个简单的例子来解释通道吗?最后,什么是逆?
What is Channeling in MiniZinc? Can you provide an simple example to explain Channeling? Finally, What is Inverse?
MiniZinc 中的通道是什么?你能提供一个简单的例子来解释通道吗?最后,什么是逆?
两者都用于建立两个数组之间的双向关系。
设 f
为 index_set(f)
等于 1..10
且值在 81..90
中的数组。
那么f
可以看作是一个映射--a.k.a。一个函数-- 从值集 1..10
到值集 81..90
.
逆.
predicate inverse(array [int] of var int: f,
array [int] of var int: invf)
这个约束表示如果 f
是一个将索引 i
映射到值 j
的函数,那么 invf
是一个映射索引 [=22] 的函数=] 到值 i
(反之亦然)。换句话说,数组 invf
使用 f
中的值进行索引,它产生 f
中包含的每个值在 f
中的位置。
int_set_channel。
predicate int_set_channel(array [int] of var int: x,
array [int] of var set of int: y)
约束表示如果 x
是将索引 i
映射到给定集合 j
的函数,则值 i
包含在集合中index j
in y
(反之亦然)。这与 inverse 约束完全相同,只是 y
是集合数组而不是值数组。
根据我的经验,渠道限制 可用于从一个问题视图 转移到另一个问题视图,以便表达其他约束最自然的 ——也是最有效的—— 方式。这种类型的约束可以使用上面描述的全局约束,或者使用基本语言结构来表达。例如,参见 carseq.mzn.
有关更多有用信息和具体示例,请参阅 Section 2.6.6.1 of the docs。
int: n;
array [1..n] of var 1..n: q; % queen is column i is in row q[i]
include "alldifferent.mzn";
constraint alldifferent(q); % distinct rows
constraint alldifferent([ q[i] + i | i in 1..n]); % distinct diagonals
constraint alldifferent([ q[i] - i | i in 1..n]); % upwards+downwards
include "lex_lesseq.mzn";
% Alternative Boolean model:
% Map each position i,j to a Boolean telling us whether there is a queen at i,j
array[1..n,1..n] of var bool: qb;
% Channeling constraint
constraint forall (i,j in 1..n) ( qb[i,j] <-> (q[i]=j) );
% Lexicographic symmetry breaking constraints
constraint
lex_lesseq(array1d(qb), [ qb[j,i] | i,j in 1..n ])
/\ lex_lesseq(array1d(qb), [ qb[i,j] | i in reverse(1..n), j in 1..n ])
/\ lex_lesseq(array1d(qb), [ qb[j,i] | i in 1..n, j in reverse(1..n) ])
/\ lex_lesseq(array1d(qb), [ qb[i,j] | i in 1..n, j in reverse(1..n) ])
/\ lex_lesseq(array1d(qb), [ qb[j,i] | i in reverse(1..n), j in 1..n ])
/\ lex_lesseq(array1d(qb), [ qb[i,j] | i,j in reverse(1..n) ])
/\ lex_lesseq(array1d(qb), [ qb[j,i] | i,j in reverse(1..n) ])
;
% search
solve :: int_search(q, first_fail, indomain_min)
satisfy;
output [ if fix(q[j]) == i then "Q" else "." endif ++
if j == n then "\n" else "" endif | i,j in 1..n]
此处,通道约束 将模型中包含的 n-queens 问题的两个视图联系起来。第一个视图 q
是一维的,并告诉皇后在每列中的行位置。第二个视图 qb
是二维的,它告诉棋盘上的哪一块棋子被某个皇后占据。第一个视图非常适合解决问题的 placement 部分。第二个视图非常适合应用 对称破坏约束 .
MiniZinc 中的通道是什么?你能提供一个简单的例子来解释通道吗?最后,什么是逆?
两者都用于建立两个数组之间的双向关系。
设 f
为 index_set(f)
等于 1..10
且值在 81..90
中的数组。
那么f
可以看作是一个映射--a.k.a。一个函数-- 从值集 1..10
到值集 81..90
.
逆.
predicate inverse(array [int] of var int: f,
array [int] of var int: invf)
这个约束表示如果 f
是一个将索引 i
映射到值 j
的函数,那么 invf
是一个映射索引 [=22] 的函数=] 到值 i
(反之亦然)。换句话说,数组 invf
使用 f
中的值进行索引,它产生 f
中包含的每个值在 f
中的位置。
int_set_channel。
predicate int_set_channel(array [int] of var int: x,
array [int] of var set of int: y)
约束表示如果 x
是将索引 i
映射到给定集合 j
的函数,则值 i
包含在集合中index j
in y
(反之亦然)。这与 inverse 约束完全相同,只是 y
是集合数组而不是值数组。
根据我的经验,渠道限制 可用于从一个问题视图 转移到另一个问题视图,以便表达其他约束最自然的 ——也是最有效的—— 方式。这种类型的约束可以使用上面描述的全局约束,或者使用基本语言结构来表达。例如,参见 carseq.mzn.
有关更多有用信息和具体示例,请参阅 Section 2.6.6.1 of the docs。
int: n;
array [1..n] of var 1..n: q; % queen is column i is in row q[i]
include "alldifferent.mzn";
constraint alldifferent(q); % distinct rows
constraint alldifferent([ q[i] + i | i in 1..n]); % distinct diagonals
constraint alldifferent([ q[i] - i | i in 1..n]); % upwards+downwards
include "lex_lesseq.mzn";
% Alternative Boolean model:
% Map each position i,j to a Boolean telling us whether there is a queen at i,j
array[1..n,1..n] of var bool: qb;
% Channeling constraint
constraint forall (i,j in 1..n) ( qb[i,j] <-> (q[i]=j) );
% Lexicographic symmetry breaking constraints
constraint
lex_lesseq(array1d(qb), [ qb[j,i] | i,j in 1..n ])
/\ lex_lesseq(array1d(qb), [ qb[i,j] | i in reverse(1..n), j in 1..n ])
/\ lex_lesseq(array1d(qb), [ qb[j,i] | i in 1..n, j in reverse(1..n) ])
/\ lex_lesseq(array1d(qb), [ qb[i,j] | i in 1..n, j in reverse(1..n) ])
/\ lex_lesseq(array1d(qb), [ qb[j,i] | i in reverse(1..n), j in 1..n ])
/\ lex_lesseq(array1d(qb), [ qb[i,j] | i,j in reverse(1..n) ])
/\ lex_lesseq(array1d(qb), [ qb[j,i] | i,j in reverse(1..n) ])
;
% search
solve :: int_search(q, first_fail, indomain_min)
satisfy;
output [ if fix(q[j]) == i then "Q" else "." endif ++
if j == n then "\n" else "" endif | i,j in 1..n]
此处,通道约束 将模型中包含的 n-queens 问题的两个视图联系起来。第一个视图 q
是一维的,并告诉皇后在每列中的行位置。第二个视图 qb
是二维的,它告诉棋盘上的哪一块棋子被某个皇后占据。第一个视图非常适合解决问题的 placement 部分。第二个视图非常适合应用 对称破坏约束 .