ラベルとは、RCSPにおいて、経路状態を表現する言葉です。
ドミナンス（Dominance：支配）とは、「ある経路（ラベル）が別の経路よりも明らかに優れているため、劣っている方を探索から除外する」という判断基準のことです。
不要な探索の削減（枝刈り）
あるノードに至る2つのラベル とを比較したとき、全ての指標において、同等以上に優れていて、少なくとも一つが上回るとき、Pruningできます。
もし がすべての指標（コスト、時間など）において 以上に優れており、かつ少なくとも1つの指標で を上回っている場合、「 ｘは ｙを支配(Dominate)する」と言います。
支配されたラベル は、その先をどのように延長しても を延長した経路より良くなることはないため、それ以上探索する必要がなくなり、破棄されます。
＜Min制約をどうする？＞
ラベル設定法や動的計画法において、MIN制約（「〜以上でなければならない」という下限制約）をMAX制約（「〜以下でなければならない」という上限制約）に変換する一般的な手法は、「残りの必要量」に着目する、または「変数の反転」を行うことです。Max制約になれば、「とにかく小さいほうが良い」というDominate Ruleで枝刈り出来ます。
具体的には、以下の2つのアプローチがよく使われます。
1. 「残りの必要量」を状態変数にする（推奨）
「現在の蓄積量」を管理するのではなく、「目標達成までにあとどれくらい必要か」をリソース（ラベル）として管理します。
変換前（MIN制約）:
状態：現在の合計値
制約： （ 以上のリソースが必要）
変換後（MAX制約）:
状態：残りの必要量
初期値：
各ステップ：リソースを消費するごとに を減らす（0以下になったら目標達成）
制約：なし（または が 0 になることを目指す）
これにより、「下限値を突破する」という条件を、「初期値（上限）から減らしていく」というMAX制約に近い形に落とし込めます。
2. 変数の反転（ネガティブ変換）
単純に符号を反転させる方法です。
変換前:
変換後:
ラベル設定法のアルゴリズム内で「リソース消費量」を正の数で扱いたい場合は、「余裕（スラック）」を定義します。
＜問題はMIN-MAX制約＞
MIN-MAX範囲がある場合は、注意が必要で、同じリソースに対して、異なる方向にドミナンスが働くことになります。そのまま実装すると矛盾した枝刈りとなり最適解を失い、最悪は、Infeasibleな結果となります。
単純に、MINまでは、大きいものが強い、MIN以降は、小さいものが強い
とすれば、良いような気がします。しかし、そのロジックで単純に片方を捨ててしまうと、厳密解（最適解）を失う可能性が非常に高いです。
なぜなら、ラベル設定法におけるドミナンスの鉄則は「将来のいかなる拡張に対しても、一方のラベルがもう一方より必ず良い結果をもたらす」と言い切れるときだけ、劣る方を捨てるというものだからです。「Minまでは大きい方が強く、Min以降は小さい方が強い」という切り替え方式では、「将来どちらの制約がネックになるか」が場所によって変わるため、厳密解が消えるリスクがあります。
0 件のコメント:
コメントを投稿