特許
J-GLOBAL ID：200903065994623869
汎用初期割付作成方式
発明者：
,
出願人/特許権者：
代理人 (1件)：
加藤 朝道
公報種別：公開公報
出願番号（国際出願番号）：特願平8-356887
公開番号（公開出願番号）：特開平10-187655
出願日： 1996年12月26日
公開日（公表日）： 1998年07月21日
要約：
【要約】【課題】変数の集合と変数集合中の各変数に割付け可能な候補値の集合である候補集合の集合と、変数の値に関する様々な条件と重要度を持つ制約の集合と、組合せ割付けの評価尺度である目的関数が与えられ、変数集合の全変数に対して目的関数を最適化する値を割付ける制約伝播を用いた自動初期割付作成方式の提供。【解決手段】与えられた変数の集合、候補集合の集合、制約条件の集合、目的関数をもとに、初期割付けを作成する際、制約伝播手段において制約集合を上記変数集合の間で伝播し候補集合が空集合になる変数ができた場合に、調整割り付け手段において、候補集合が空集合になる変数に対して目的関数を最適化する値を対応する候補集合から選択して割付け、割付け済み変数の各変数の割付け値を変更することにより違反制約の解消を試みることにより、品質の高い初期割り付けを作成することを可能とする。
請求項（抜粋）：
変数の集合と、前記変数集合中の各変数に割り付け可能な候補値の集合である候補集合の集合と、変数の値に関する様々な条件と重要度を持つ制約の集合と、組合せ割り付けの評価尺度であり、制約違反状況を基準に計算される目的関数と、が与えられ、前記変数集合の全変数に対して、前記目的関数を最適化する値を割り付ける自動割り付け作成方式において、(a)変数集合と、候補集合の集合と、制約集合と、目的関数と、を入力する入力ステップと、(b)制約伝播を用い前記変数集合の変数に対して制約違反なしに値を割り付ける無違反割り付けステップと、(c)前記無違反割り付けステップが違反なしに値を割り付けることができなくなった変数の集合に対して、違反を認めて、値を割り付ける違反割り付けステップと、を含み、前記無違反割り付けステップが、(b-1)前記制約集合を前記変数集合の間で伝播する制約伝播ステップと、(b-2)前記変数集合に存在する変数の1つに対して前記候補集合から値を選択して割り付ける通常割り付けステップと、(b-3)指定された変数に対して制約を違反する値を割り付け、割り付け済み変数の値の変更処理により制約違反の解消を行う調整割り付けステップと、(b-4)前記調整割り付けステップで制約違反解消が行えなかった場合に、変数を保留する変数保留ステップと、を含み、全ての変数が割り付け済み変数か保留変数になるまで、上記各ステップの処理を繰り返し、前記制約伝播ステップが、(b-1-1)前記制約集合を前記変数集合の間で伝播し前記候補集合が空集合になる変数ができた場合には前記調整割り付けステップに処理を渡し、前記候補集合が空集合になる変数がない場合には前記通常割り付けステップに処理を渡し、(b-1-2)前記通常割り付けステップが、前記変数集合に存在する変数の1つに対して前記目的関数を最適化する値を前記変数に対応する前記絞り込まれた候補集合から選択して割り付け、前記変数を割り付け済み変数とし、前記調整割り付けステップが、(b-3-1)割り付け済み変数集合の中の各変数の値を保存し、(b-3-2)前記候補集合が空集合になる変数に対して、前記目的関数を最適化する値を、前記候補集合が空集合になった変数に対応する前記候補集合から選択して割り付け、(b-3-3)割り付け済み変数の割り付け値を変更することにより違反制約の解消を試み、前記目的関数を最適化し、(b-3-4)制約違反が解消した場合には、前記候補集合が空集合になった変数を割り付け済み変数集合に登録し、割り付け済み変数集合の各変数からの制約伝播を再び行い、(b-3-5)制約違反を解消できなかった場合には、前記変数保留ステップに処理を渡し、前記変数保留ステップが、(b-4-1)割り付け済み変数集合の各変数の割り付けを保存した割り付けに戻し、(b-4-2)前記候補集合が空集合になった変数を前記変数集合から除外し、保留変数集合に追加する、ことを特徴とする汎用初期割付作成方式。
引用特許：
前のページに戻る
