数理最適化セミナーのご案内

5.11 順序集合クラスOrderedSet

　集合内の要素に順序が定められた順序集合はOrderedSetクラスで表現されます．集合の要素にわたるループを表現する場合には，このOrderedSetクラスが有用です．OrderedSetクラスはSetクラスの機能を全て有しており，加えて次の関数が使用できます．

  • first関数　順序集合の最初の要素を返す
  • last関数　順序集合の最後の要素を返す
  • next関数　次の要素を返す
  • prev関数　前の要素を返す
  • position関数　要素の位置（何番目かを意味する整数）を返す
  • elementAt関数　位置（何番目かを意味する整数）にある要素を返す

　C++の関数としてのフォーマットは以下のようになります．

// OrderedSetのメンバ関数
Element first();    // 最初の要素を返す
Element last();     // 最後の要素を返す
Element next(const Element& i); // 要素iの次の要素を返す
Element prev(const Element& i); // 要素iの前の要素を返す
int position(const Element& i); // 要素iの位置を返す
Element elementAt(int p); // 場所pにある要素を返す

　OrderedSetクラスを利用する事で，漸化式や漸化不等式を取り扱うことが可能です．

　次の例では漸化不等式$x_{p} \le x_{q}$, $x_{q} \le x_{r}$, $x_{r} \le x_{s}$をOrderedSetを利用して記述しています． 

OrderedSet S = "p q r s";
Element i(set = S);
Variable x(index = i);
x[i] <= x[S.next(i)], i != S.last();

　最後の条件式i != S.last()はi == sの場合を除外するためです．上記の例ではnext関数とlast関数を利用しましたが，以下のようにprev関数とfirst関数を利用することもできます． 

OrderedSet S = "p q r s";
Element i(set = S);
Variable x(index = i);
x[S.prev(i)] <= x[i], i != S.first();

　集合の要素が整数ではない場合，上記のようにOrderedSetを用いる必要があります．しかし集合の要素が整数の場合は，次のようにOrderedSetを用いない記述も可能です． 

Set S = "1 2 3 4";
Element i(set = S);
Variable x(index = i);
x[i] <= x[i + 1], i != 4;

　同様に次の記述も可能です．

Set S = "1 2 3 4";
Element i(set = S);
Variable x(index = i);
x[i - 1] <= x[i], i != 1;

　整数以外の要素からなる集合を利用する場合，条件式においてi + 1, i - 1等の要素間の演算が使用できない事が，OrderedSetに頼らざるを得ない主な理由です．

　次の例では，定数a[p], a[q], a[r]にそれぞれ2, 4, 6（2ずつ増加）を設定します． 

OrderedSet S = "p q r";
Element i(set = S);
Element j;
Parameter a(index = i);
for(j = S.first(); j < S; j = S.next(j)){
       a[j] = 2 * S.position(j);
}

　以下のように記述しても同じ意味です．

OrderedSet S = "p q r";
Element i(set = S);
Element j;
Parameter a(index = i);
for(int p = 1; p < S.card() + 1; p++){
       j = S.elementAt(p);
       a[j] = 2 * p;
}

　集合の要素が整数である場合は，次のようにOrderedSetを用いない記述も可能です．以下の例では，定数a[1], a[2], a[3]にそれぞれ2, 4, 6（2ずつ増加）を設定します． 

Set S = "1 2 3";
Element i(set = S);
Parameter a(index = i);
a[i] = 2 * i;

　Setの操作の一部はOrderedSetでも利用できます．例えばaddはOrderedSetに対して適用可能です．SetからOrderedSetを構成する場合は操作addを用いるのが簡便です． 

Set S;
Element i(set = S);
S = "1 2 3";
OrderedSet T;
// i を T に追加する．これにより S と T は同じ要素で構成される．
T.add(i);
5.10.3 切断操作 slice
5.12 数列集合Sequence

 

 

上に戻る