組合せ最適化初期割付け作成方式

発明者：
出願人/特許権者：
代理人 (1件)：京本直樹 (外2名)
公報種別：公開公報
出願番号（国際出願番号）：特願平5-105234
公開番号（公開出願番号）：特開平6-314271
出願日： 1993年05月06日
公開日（公表日）： 1994年11月08日
要約：

【要約】【目的】制約伝播を用いることにより未割付けの変数との間の制約を前もって考慮することにより、品質の格段に向上した初期割付けを作成することができる組合せ最適化初期割付け作成方式の提供。【構成】変数集合と候補集合の集合と制約集合と目的関数とを入力するステップ11と、制約集合を変数集合の間で伝播し候補集合が空集合になる変数がなくなるかまたは変数集合が空集合になるまで候補集合の集合を絞り込む制約伝播ステップ(ステップ12、13、14および16)と、変数集合に存在する変数の1つに目的関数を最適化する値を候補集合から選択して割付けるステップ15と、候補集合が空集合になった変数の1つに対して値を割付けるステップ18とを含み、制約伝播ステップとステップ15とからなる組ステップを変数集合が空集合になるまで続行し、その後にステップ18を残りの変数すべてに行なう。

請求項（抜粋）：

変数集合と前記変数集合中の各変数に割付け可能な候補値の集合である候補集合の集合と組合せ割付けの制約の集合である制約集合と組合せ割付けの評価尺度である目的関数とを入力する入力ステップと、前記制約集合を前記変数集合の間で伝播し前記候補集合が空集合になる変数ができた場合にはこの変数を前記変数集合から除外して前記候補集合が空集合になる変数がなくなるかまたは前記変数集合が空集合になるまでこの伝播を続行して前記候補集合を絞り込む制約伝播ステップと、前記制約伝播ステップで前記候補集合の中で空集合になる変数がなくなったときに前記変数集合に存在する変数の1つに対して前記目的関数を最適化する値を前記変数に対応する前記絞り込まれた候補集合から選択して割付け前記変数を前記変数集合から削除する第1の割付けステップと、前記制約伝播ステップで除外された変数の1つに対して前記目的関数を最適化する値を前記除外された変数に対応する前記候補集合から選択して割付ける第2の割付けステップとを含み、前記制約伝播ステップと前記第1の割付けステップとからなる組ステップを前記変数集合が空集合になるまで続行し、その後に前記第2の割付けステップを前記除外された変数すべてに行なうことを特徴とする組合せ最適化初期割付け作成方式。

引用特許：

審査官引用 (4件)

特開昭63-163672
組合せ問題処理装置
公報種別：公開公報出願番号：特願平3-297496 出願人：富士通株式会社
特開平1-240973

全件表示

前のページに戻る