0

長さの異なる 2 つの配列 (型: int) があります。配列 a の各数値に対して、配列 b で最も近い数値を見つけるにはどうすればよいでしょうか (おそらく構文エラーのため、以下は機能しません)。

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

1 に答える 1

1

("m" と "n" の値やその他の既知/固定値など、可能な限り多くの情報を含む完全なモデルで常に役立ちます。また、エラー メッセージについて言及すると、一般的に役立ちます。)

あなたのモデルには不明な点がいくつかあるので、少し推測する必要があります。

「結果」は、定義した配列ではなく、実際には単一の決定変数であるべきだと思います。それからあなたは書くことができます

var int: results = sum([abs(a[i] - b[j])| i in 1..m, j in 1..n]);

また

var int: results;
...
constraint results = sum([abs(a[i] - b[j])| i in 1..m, j in 1..n]);

また、このモデルは 2 つの定数配列 "a" と "b" (定数値を入力する必要があります) を定義するだけなので、現状では特に興味深いものではありません。それらの少なくとも 1 つは決定変数を意図していると思います。決定変数の配列は、「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",
  ];

2015 年 11 月 19 日更新:

要件を完全に理解しているかどうかはわかりませんが、ここにバリエーションがあります。sum ループは "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 の各要素に最も近い値でなければなりません。

ここで、「results」の各値は、同じインデックス (「i」) を持つ「a」の値に対応します。つまり、

 % ...
 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 (2015-11-20)

2番目のコメントについて、2D（あなたが書いた3Dバージョンではありません）について、ここにモデルがあります。これは、上記のモデルの 2 番目の解釈に基づいています。より大きな次元に拡張するには、次元を変更してループ変数を追加するだけです。

これは、おそらく元の質問に反して、「a」と「results」の次元が同一であると仮定していることに注意してください。そうでない場合、2 番目の解釈は意図したものにはなりません。また、「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
];

これの1つの最適な解決策はこれです：

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
于 2015-11-18T16:54:26.697 に答える