- html - 出于某种原因,IE8 对我的 Sass 文件中继承的 html5 CSS 不友好?
- JMeter 在响应断言中使用 span 标签的问题
- html - 在 :hover and :active? 上具有不同效果的 CSS 动画
- html - 相对于居中的 html 内容固定的 CSS 重复背景?
练习是:
n个人想要拍一张合影。每个人都可以给出他或她旁边的偏好想要放置在照片上。要解决的问题是找到满足最大数量的放置位置偏好。
到目前为止我编写的代码:
include "globals.mzn";
% input variables
int: n;
int: n_prefs;
array[1..n_prefs, 1..2] of var 1..n: prefs;
% FDV:s
array [1..n] of var 1..n: photo_arrangement;
var 0..n_prefs: cost;
constraint
all_different(photo_arrangement)
% MORE Constraints
solve maximize cost;
output [show( photo_arrangement )]
n是照片中的人数
n_prefs 是首选项的数量
prefs 是包含所有首选项的矩阵
主要思想是拥有一个包含人员 1 到 n 的数组,以及我们想要最大化的成本变量。如何根据偏好更改成本变量?
最佳答案
这是一种方法。 (更新:实际上,现在有三个具有相同基本思想的不同模型。)
include "globals.mzn";
% input variables
int: n;
int: n_prefs;
array[1..n_prefs, 1..2] of 1..n: prefs;
% FDV:s
array [1..n] of var 1..n: photo_arrangement;
% the positions of each person in photo_arrangement
array [1..n] of var 1..n: pa_inv = inverse(photo_arrangement);
% to see what preferences that are satisfied
array[1..n_prefs] of var int: prefs_sat;
var 0..n_prefs: cost;
constraint
all_different(photo_arrangement)
/\
forall(p in 1..n_prefs) (
% note: we use the inverse of photo_arrangement for indexing since we
% want to compare the positions of the two persons prefs[p,1] and prefs[p,2]
prefs_sat[p] = if abs(pa_inv[prefs[p,1]]-pa_inv[prefs[p,2]]) = 1 then 1 else 0 endif
)
/\
cost = sum(prefs_sat)
;
solve :: int_search(photo_arrangement, first_fail, indomain_split, complete) maximize cost;
output [
"cost: \(cost)\nphoto_arrangement: \(photo_arrangement)\n(pa_inv: \(pa_inv))\n"
] ++
[
show([prefs[p,i] | i in 1..2]) ++ ": " ++ show(prefs_sat[p]) ++ "\n"
| p in 1..n_prefs
];
% data
n = 9;
n_prefs = 17;
prefs = [| 1,3 | 1,5 | 1,8 | 2,5 | 2,9 | 3,4 | 3,5 | 4,1 | 4,5 | 5,6 | 5,1 | 6,1 | 6,9 | 7,3 | 7,8 | 8,9 | 8,7 |];
要点是使用额外的数组( pa_inv
),即 inverse
的photo_arrangement
并显示每个人的位置。这意味着我们可以使用pa_inv[1]
得到人1的位置,从而可以计算出pa_inv[prefs[p,1]
的位置差和pa_inv[prefs[p,2]
(如果两个人位于彼此之间,则为 1)。 prefs_sat
数组显示是否满足首选项 (1) 或不满足 (0)。
有 20 个最佳解决方案和 10 个满意的偏好。一种最佳解决方案是:
cost: 10
photo_arrangement: [2, 5, 1, 4, 3, 7, 8, 9, 6]
(pa_inv: [3, 1, 5, 4, 2, 9, 6, 7, 8])
[1, 3]: 0
[1, 5]: 1
[1, 8]: 0
[2, 5]: 1
[2, 9]: 0
[3, 4]: 1
[3, 5]: 0
[4, 1]: 1
[4, 5]: 0
[5, 6]: 0
[5, 1]: 1
[6, 1]: 0
[6, 9]: 1
[7, 3]: 1
[7, 8]: 1
[8, 9]: 1
[8, 7]: 1
几分钟后更新:
这是另一种使用 element
的方法函数而不是使用 inverse
,这意味着我们不需要 pa_inv
大批。 forall
上面代码中的循环可以替换为:
%
forall(p in 1..n_prefs) (
prefs_sat[p] = if abs(element([prefs[p,1],photo_arrangement)-element(prefs[p,2],photo_arrangement)) = 1 then 1 else 0 endif
)
%
几天后更新:还有另一种(可以说更简单)模型,与之前的方法类似,但它在输出中使用“逆”部分。
include "globals.mzn";
int: n;
int: n_prefs;
array[1..n_prefs, 1..2] of 1..n: prefs;
array [1..n] of var 1..n: photo_arrangement;
var 0..n_prefs: cost;
constraint
all_different(photo_arrangement) /\
cost = sum(p in 1..n_prefs) (
if abs(photo_arrangement[prefs[p,1]]-photo_arrangement[prefs[p,2]]) = 1 then 1 else 0 endif
)
;
solve :: int_search(photo_arrangement, first_fail, indomain_split, complete) maximize cost;
output [
"cost: \(cost)\nphoto_arrangement: \(photo_arrangement)\n",
"positions:\n"
] ++ [
if fix(photo_arrangement[j]) = i then show(j) ++ " " else "" endif
| i,j in 1..n
];
n = 9;
n_prefs = 17;
prefs = [| 1,3 | 1,5 | 1,8 | 2,5 | 2,9 | 3,4 | 3,5 | 4,1 | 4,5 | 5,6 | 5,1 | 6,1 | 6,9 | 7,3 | 7,8 | 8,9 | 8,7 |];
解决办法是
cost: 10
photo_arrangement: [8, 1, 5, 6, 7, 9, 4, 3, 2]
positions:
2 9 8 7 3 4 5 1 6
关于minizinc - 了解迷你锌,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/47078402/
我想在 MiniZinc 中用相同的项目创建两个数组,不一定按相同的顺序。在这里,A0 中的每一项也应该在 A1 : array[1..3] of var int:A0; array[1..3] of
假设我想计算 {1,2,..100} 的 80 个元素子集的数量,使它们的总和为 3690。 我有以下模型: array[1..100] of var 0..1: b; constraint (sum
我看到 MiniZinc Handbook 中的各个地方都使用了 $ (主要在 Reference Manual 部分),但我一直找不到定义。有人可以向我解释一下吗?谢谢。 最佳答案 MiniZinc
在斑马谜题 ( http://rosettacode.org/wiki/Zebra_puzzle#MiniZinc ) 的解决方案中,有一个约束条件,规定其中一只宠物必须是斑马: var 1..5:
在斑马谜题 ( http://rosettacode.org/wiki/Zebra_puzzle#MiniZinc ) 的解决方案中,有一个约束条件,规定其中一只宠物必须是斑马: var 1..5:
我正在尝试解决 MiniZinc 中的一个练习,其中部分排序关系由二维数组给出: enum NODE = { A, B, C, D, E }; int : SOURCE = 1; int : TARG
我正在熟悉 MiniZinc 的基础知识。因此,借助 MiniZinc IDE,我编写了如下代码片段 solve satisfy; string: s1 = "hello"; string: s2 =
锌规范是这样说的: If no output item is present, the implementation should print all the global variables and
MiniZinc 中的 channel 是什么?你能提供一个简单的例子来解释 channel 吗?最后,什么是逆? 最佳答案 两者都用于建立两个数组之间的双向关系。 设 f 是一个数组,index_s
FlatZinc 文档说 只有非标谓词必须在 FlatZinc 模型的顶部声明: Predicates used in the model that are not standard FlatZinc
我有一个二维网格,其中某些单元格值会产生不同的分数,我想通过为单元格分配值来最大化分数。是否可以跟踪求解器在求解过程中尝试的每个网格?下面是模型的一个片段,只是为了演示这个想法。 int: i_cou
picat求解器 (v. 2.6#2) 指出示例模型 knights.mzn包含在 minizinc 存储库中,特此复制粘贴: % RUNS ON mzn20_fd % RUNS ON mzn-fzn
尝试学习 minizinc,但在完成示例之后,我是否可以确认,如果我想获得多个输出,或者有一种更“自然的 minizinc”方式来获得它,我实际上必须编写一些程序语言。 例如,假设我想让所有不同的数字
练习是: n个人想要拍一张合影。每个人都可以给出他或她旁边的偏好想要放置在照片上。要解决的问题是找到满足最大数量的放置位置偏好。 到目前为止我编写的代码: include "globals.mzn";
我正在尝试编写一个带有嵌套循环的输出语句,以及在外部级别的重要输出。如果 Minizinc 有一个顶级 for 命令,我会做类似的事情 for (f in Foo) ( output(["Foo:
我想检查 1 到 5 之间的哪个数字没有出现在数组组中,并将这个(或多个)数字放在另一个数组中。 g=2; set of int: GROUPS = 1..g; groups = [{1, 3}, {
问题 给定一个 MiniZinc 字符串数组: int: numStats; set of int: Stats = 1..numStats; array[Stats] of string: stat
我有一个变量,它应该只在特定条件下有一个值,所以我想它需要是一个可选变量。如果满足该条件,则可选变量应限制为集合的元素。 问题是,MiniZinc 似乎不喜欢可选变量和集合。 如何重写,使 MiniZ
我如何使用嵌套 for 循环(就像下面 java 所做的那样)在 Minizinc 中生成/填充数组? int[][] input1 = {{1,1,1}, {3,3,3}, {5,5,5} }; i
我正在使用 minizinc 和 gecode 以分布式方式解决最小化问题。我有多个分布式服务器,它们使用相同的输入来解决相同的模型,并且我希望所有服务器都能获得相同的解决方案。 问题是模型有多个解决
我是一名优秀的程序员,十分优秀!