最適化セミナーのご案内

5.13 順序集合クラス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;

 添字を付ける事で,集合族を定義することもできます.次の例では,集合族Mを定義しています.M[1]a, b, cから,M[2]d, e, fから構成されています.

Set S="1 2";
Element i(set=S);
Set M(index=i);
M[1]="a b c";
M[2]="d e f";

 

 

上に戻る