У меня есть два массива (тип: int) разной длины. Как мне найти ближайшее число в массиве b для каждого числа в массиве a (следующее не работает, хотя, вероятно, из-за синтаксической ошибки):
int: m;
int: n;
array [1..m] of int: a;
array [1..n] of int: b;
array[1..m] of int: results;
results = [abs(a[i] - b[j])| i in 1..m, j in 1..n];
solve minimize results;
output ["Solution: ", show(results)];
(Это всегда помогает получить полную модель с максимально возможным объемом информации, например, значениями «m» и «n» и другими известными / фиксированными значениями. Кроме того, в целом помогает упоминание сообщений об ошибках.)
В вашей модели есть пара неизвестных вещей, поэтому я должен немного угадать.
Я предполагаю, что «результаты» действительно должны быть единственной переменной решения, а не массивом, как вы его определили. Тогда вы можете написать
var int: results = sum([abs(a[i] - b[j])| i in 1..m, j in 1..n]);
or
var int: results;
...
constraint results = sum([abs(a[i] - b[j])| i in 1..m, j in 1..n]);
Кроме того, в нынешнем виде модель не особенно интересна, поскольку она просто определяет два постоянных массива «a» и «b» (которые должны быть заполнены постоянными значениями). Я предполагаю, что по крайней мере одна из них должна быть переменными решения. Массив переменных решения должен быть объявлен с помощью «var int» (или лучше: что-то вроде «var 1..size», где 1..size - это область возможных значений в массиве).
Вот пример работающей модели, которая может быть, а может и не быть похожей на то, что вы имеете в виду:
int: m = 10;
int: n = 10;
array [1..m] of int: a = [1,2,3,4,5,6,7,8,9,10];
array [1..n] of var 1..10: b;
var int: results = sum([abs(a[i] - b[j])| i in 1..m, j in 1..n]);
solve minimize results;
output [
"Solution: ", show(results),"\n",
"a: ", show(a), "\n",
"b: ", show(b), "\n",
];
Обновление 19.11.2015:
Не уверен, что полностью понимаю требования, но вот вариант. Обратите внимание, что цикл суммирования вообще не использует массив «b», только «a» и «results». Чтобы гарантировать, что значения в «результатах» выбраны из «b», область «результатов» представляет собой просто набор значений в «b».
int: m = 10;
int: n = 10;
array [1..m] of int: a = [1,2,3,4,5,6,7,8,9,10];
array [1..n] of int: b = [5,6,13,14,15,16,17,18,19,20];
% decision variables
% values only from b
array[1..m] of var {b[i] | i in 1..n}: results;
var int: z; % to minimize
constraint
z >= 0 /\
z = sum(i in 1..m) (
sum(j in 1..m) (abs(a[i]-results[j]))
% (abs(a[i]-results[i])) % alternative interpretation (see below)
)
;
solve minimize z;
output [
"z: ", show(z), "\n",
"results: ", show(results),"\n",
"a: ", show(a), "\n",
"b: ", show(b), "\n",
];
В Gecode есть это для оптимального решения:
z: 250
results: [5, 5, 5, 5, 5, 5, 5, 5, 5, 5]
a: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
b: [5, 6, 13, 14, 15, 16, 17, 18, 19, 20]
Другой решатель (Opturion CPX) имеет решение, более похожее на ваш вариант:
z: 250
results: [6, 6, 5, 5, 5, 6, 6, 6, 5, 5]
a: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
b: [5, 6, 13, 14, 15, 16, 17, 18, 19, 20]
Обратите внимание, что оба решения имеют одинаковое оптимальное целевое значение ("z") 250.
Однако существует альтернативная интерпретация требования (из вашего комментария):
для каждого элемента в a выберите соответствующее значение из b - это значение должно быть самым близким по значению к каждому элементу в a.
где каждое значение в «результатах» соответствует только значению в «а» с тем же индексом («i»), т. е.
% ...
constraint
z >= 0 /\
z = sum(i in 1..m) (
(abs(a[i]-results[i]))
)
;
Тогда решение будет (Gecode):
z: 19
results: [5, 5, 5, 5, 5, 6, 6, 6, 6, 13]
a: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
b: [5, 6, 13, 14, 15, 16, 17, 18, 19, 20]
Затем выбирается последнее значение в «results» (13), так как оно ближе к 10 (последний элемент в «a»).
Обновление 2 (20 ноября 2015 г.)
Что касается второго комментария о 2D (а не о 3D-версии, которую вы написали), вот модель. Он основан на второй интерпретации модели, представленной выше. Расширение его до более крупных размеров - это просто вопрос изменения размеров и добавления переменных цикла.
Обратите внимание, что это предполагает - возможно, вопреки вашему первоначальному вопросу - что размеры «a» и «results» идентичны. Если это не так, вторая интерпретация не может быть той, которую вы намереваетесь. Также я изменил значения в «a» и «b», чтобы сделать его более интересным. :-)
int: m = 3;
int: n = 3;
array [1..m,1..n] of int: a = [|1,2,3|4,5,6|7,8,9|];
array [1..m,1..n] of int: b = [|5,6,13|14,15,16,|7,18,19|];
% decision variables
% values only from b
array[1..m,1..n] of var {b[i,j] | i in 1..m, j in 1..n}: results;
var int: z;
constraint
z >= 0 /\
z = sum(i in 1..m, j in 1..n) (
(abs(a[i,j]-results[i,j]))
)
;
solve minimize z;
output [ "z: ", show(z), "\n" ]
++["results:"]++
[
if j = 1 then "\n" else " " endif ++
show_int(2,results[i,j])
| i in 1..m, j in 1..n
]
++["\na:"]++
[
if j = 1 then "\n" else " " endif ++
show_int(2,a[i,j])
| i in 1..m, j in 1..n
]
++["\nb:"]++
[
if j = 1 then "\n" else " " endif ++
show_int(2,b[i,j])
| i in 1..m, j in 1..n
];
Одно из оптимальных решений - это:
z: 13
results:
5 5 5
5 5 6
7 7 7
a:
1 2 3
4 5 6
7 8 9
b:
5 6 13
14 15 16
7 18 19
