(57)【要約】【課題】従来の状態空間の探索方式では、“着目状態”から遷移可能と定義されている全ての状態の評価を行い、その中で最小の評価関数値を持つ状態への“着目状態”の遷移を繰り返すことにより、最適解を発見しているため、探索効率が悪く、大きな探索回数を必要するという問題があった。【解決手段】“着目状態”から遷移可能と定義されている全ての状態の評価を行う過程で、評価関数値の良い上位Ｍ個の状態を抽出し（処理ブロック５）、これらＭ個の状態への“着目状態”からの遷移により発生するＭ種の状態の変化の内のいくつかを、“着目状態”に対して同時に発生させ、最もよい評価関数値をもつ状態を選出して（処理ブロック８）、“着目状態”の遷移を行う（処理ブロック９）ことにより、“着目状態”の距離１以上の遷移を可能とし、状態空間の探索効率を高める。【選択図】　　　　図１
2004070662.tif 000002
【特許請求の範囲】
【請求項１】
それぞれ変化する複数の要素の組合せを表す状態の集まりである状態空間の中を、一つの状態から他の状態への遷移を繰り返して最良の状態を探索する状態空間の探索方式において、指定された状態を最初の“着目状態”とし、上記“着目状態”から遷移可能と定義される複数の状態の中から評価関数を用いた評価に基づき上位Ｍ個（Ｍは正の整数、ただし上記複数の状態が上記Ｍより小さいときは上記複数の状態をＭとする）の状態を選択する第一の手順、この第一の手順によって選択されたＭ個の状態へ上記“着目状態”からそれぞれ遷移するとき発生するＭ種の変化の内の複数種を、上記“着目状態”に対し同時に発生させた場合に形成される各状態について上記評価関数に基づき評価し、これらの内で最もよい評価関数値をもつ状態を選出する第二の手順、この第二の手順によって選出された最もよい評価関数値をもつ状態へ上記“着目状態”から遷移を行い、新たな“着目状態”とする第三の手順を含むことを特徴とする状態空間の探索方式。
【請求項２】
上記第二の手順は、上記“着目状態”を遷移先候補として初期設定する第四の手順と、遷移先候補に対し、上記“着目状態”から上記Ｍ個の状態の内の一つへと遷移するとき発生する変化を、上記Ｍ個の状態の内の評価関数値のよい順に順次、発生させ、そのつど、上記変化によって形成される状態の評価関数値と上記遷移先候補の評価関数値とを比較し、上記変化によって形成される状態の評価関数値が上記遷移先候補の評価関数値よりよくなった場合に、上記変化によって形成される状態を新たな遷移先候補とする動作を繰り返すことにより、最新の遷移先候補を最もよい評価関数値をもつ状態とする第五の手順とを含むことを特徴とする請求項１記載の状態空間の探索方式。
【請求項３】
上記第五の手順は、上記変化によって形成される状態の評価関数値が上記遷移先候補の評価関数値よりよくなった場合がＫｓ（Ｋｓは、Ｍ＞Ｋｓ＞１を満足する整数）回に達するまで上記動作を繰り返すことを特徴とする請求項２記載の状態空間の探索方式。
【請求項４】
上記第五の手順は、上記変化によって形成される状態の評価関数値が上記遷移先候補の評価関数値よりよくならない場合が連続してＫｆ（Ｋｆは、Ｍ＞Ｋｆ≧１を満足する整数）回に達するまで上記動作を繰り返すことを特徴とする請求項２記載の状態空間の探索方式。
【請求項５】
上記第五の手順は、上記変化によって形成される状態の評価関数値が上記遷移先候補の評価関数値よりよくなった場合がＫｓ回に達するまで、または上記変化によって形成される状態の評価関数値が上記遷移先候補の評価関数値よりよくならない場合が連続してＫｆ回に達するまで上記動作を繰り返すことを特徴とする請求項２記載の状態空間の探索方式。
【請求項６】
上記第五の手順は、上記動作がＫ（Ｋは、Ｍ＞Ｋ＞１を満足する整数）回に達し、かつ上記変化によって形成される状態の評価関数値が上記遷移先候補の評価関数値よりよくならない場合が連続してＫｆ回に達するまで上記動作を繰り返すことを特徴とする請求項２記載の状態空間の探索方式。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
この発明は、それぞれ変化する複数の要素の組合せを表す状態の集まりである状態空間の中を探索し、最良な状態（最適な組合せ）を発見する状態空間の探索方式に関するものである。
【０００２】
【従来の技術】
例えば、「０」または「１」のようにそれぞれ変化する複数の要素を最適に組み合せる状態を探索する従来の状態空間の探索方式は、例えば、特開平５−８１３２５号公報に示されているように、
▲１▼最急降下方向への遷移（最も評価関数値が減少する方向への遷移：“着目状態”から遷移可能と定義されている状態の中で最小の評価関数値を持つ状態への“着目状態”の遷移）を繰り返す。
▲２▼“着目状態”が極小解の場合（”着目状態”から遷移可能と定義されている状態の中に、“着目状態”より小さい評価関数値を持つ状態がない場合）、“着目状態”の評価関数値を増大させ、最急降下方向への“着目状態”の遷移を継続する
という、枠組みにより、最適な状態を発見している。
【０００３】
【発明が解決しようとする課題】
このように従来の状態空間の探索方式では、“着目状態”から遷移可能と定義されている全ての状態の評価を行い、その中で最小の評価関数値を持つ状態への“着目状態”の遷移を行うため、多くの状態の評価を行って、距離１（距離ｎとは、１つの状態からもう１つ状態に到達するために最低ｎ回の状態遷移が必要という意味）の遷移が発生するのみであり、探索の効率が悪いという問題があった。
この発明は、上述のような課題を解決するためになされたものであり、“着目状態”の遷移として、距離２、距離３などの遷移をも可能にし、効率のよい探索を行えるようにした状態空間の探索方式を得ることを目的としている。
【０００４】
【課題を解決するための手段】
この発明に係わる状態空間の探索方式においては、それぞれ変化する複数の要素の組合せを表す状態の集まりである状態空間の中を、一つの状態から他の状態への遷移を繰り返して最良の状態を探索する状態空間の探索方式において、指定された状態を最初の“着目状態”とし、“着目状態”から遷移可能と定義される複数の状態の中から評価関数を用いた評価に基づき上位Ｍ個の状態を選択する第一の手順と、この第一の手順によって選択されたＭ個の状態へ“着目状態”からそれぞれ遷移するとき発生するＭ種の変化の内の複数種を、“着目状態”に対し同時に発生させた場合に形成される各状態について評価関数に基づき評価し、これらの内で最もよい評価関数値をもつ状態を選出する第二の手順と、この第二の手順によって選出された最もよい評価関数値をもつ状態へ“着目状態”から遷移を行い、新たな“着目状態”とする第三の手順を含むものである。
【０００５】
また、第二の手順は、“着目状態”を遷移先候補として初期設定する第四の手順と、遷移先候補に対し、“着目状態”からＭ個の状態の内の一つへと遷移するとき発生する変化を、Ｍ個の状態の内の評価関数値のよい順に順次、発生させ、そのつど、変化によって形成される状態の評価関数値と遷移先候補の評価関数値とを比較し、変化によって形成される状態の評価関数値が遷移先候補の評価関数値よりよくなった場合に、変化によって形成される状態を新たな遷移先候補とする動作を繰り返すことにより、最新の遷移先候補を最もよい評価関数値をもつ状態とする第五の手順とを含むものである。
また、第五の手順は、変化によって形成される状態の評価関数値が遷移先候補の評価関数値よりよくなった場合がＫｓ回に達するまで動作を繰り返すものである。
【０００６】
さらに、第五の手順は、変化によって形成される状態の評価関数値が遷移先候補の評価関数値よりよくならない場合が連続してＫｆ回に達するまで動作を繰り返すものである。
また、第五の手順は、変化によって形成される状態の評価関数値が遷移先候補の評価関数値よりよくなった場合がＫｓ回に達するまで、または変化によって形成される状態の評価関数値が遷移先候補の評価関数値よりよくならない場合が連続してＫｆ回に達するまで動作を繰り返すものである。
【０００７】
加えて、第五の手順は、動作がＫ回に達し、かつ変化によって形成される状態の評価関数値が遷移先候補の評価関数値よりよくならない場合が連続してＫｆ回に達するまで動作を繰り返すものである。
【０００８】
【実施の実施の形態】
実施の形態１．
図１は、この発明の実施の形態１による状態空間の探索方式を示す第一のフローチャートである。
図１において、処理ブロック１では、探索の出発点となる“着目状態”が初期設定され、処理ブロック２では、処理ブロック１で設定された“着目状態”が評価関数を用いて評価され、処理ブロック３では、処理ブロック１で設定された“着目状態”が、最良解の初期値として保存され、処理ブロック４では、以降の繰り返し処理のためのループ数カウンターＬｏｏｐが初期設定される。
【０００９】
処理ブロック５（第一の手順）では、“着目状態”から遷移可能と定義されている全ての状態が評価関数を用いて評価され、評価の良い上位Ｍ個（Ｍは１０以下の正の整数、ただし遷移可能と定義されている状態の数がＭに達しない場合は、遷移可能と定義された状態の数）の状態が抽出される。なお、評価関数値の算出に当たっては、過去にその状態の評価関数値の増大が行われていれば、増大後の評価関数値を採用する。
【００１０】
処理ブロック６では、“着目状態”から遷移可能と定義されている状態の評価関数値の中に“着目状態”より良い（小さい）評価関数値を持つ状態があるか否かが判定され、ある場合には、処理を処理ブロック８に移行し、ない場合（“着目状態”が極小解となっている場合）には、処理を処理ブロック７に移行する。
【００１１】
処理ブロック７では、評価関数値のより良い状態への“着目状態”の遷移を可能とするため、“着目状態”の評価関数値を、“着目状態”から遷移可能な全ての状態の評価関数値の中で最小なものより大きくなるよう増大する。
【００１２】
処理ブロック８（第二の手順）では、処理ブロック５で抽出したＭ個の状態への“着目状態”からの遷移により発生するＭ種の状態の変化の内のいくつか（複数種）を、“着目状態”に対して同時に発生させた場合の状態を評価し、これらの中で最も良い評価関数値を持つ状態を“次の着目状態”として抽出する。なお、評価関数値の算出に当たっては、過去にその状態の評価関数値の増大が行われていれば、増大後の評価関数値を採用する。
【００１３】
処理ブロック９（第三の手順）は、“着目状態”を遷移させる処理であり、“着目状態”とその評価関数値を、処理ブロック８で抽出した“次の着目状態”とその評価関数値に変更する。
【００１４】
処理ブロック１０は、最良解を保存する処理であり、“着目状態”の評価関数値が保存されている最良解の評価関数値よりも小さければ、“着目状態”を最良解として保存する。
【００１５】
処理ブロック１１では、“着目状態”が求めている性質を持つか否かを判定し、満たす場合には、求めている解を発見したとして処理を終了し、満たさない場合には、処理を処理ブロック１２に移行し、処理を継続する。
【００１６】
処理ブロック１２では、処理ブロック５〜処理ブロック１３の繰り返し処理の処理回数が指定上限値Ｌｍａｘを超えたか否かの判定を行い、超えた場合には処理を終了し、超えない場合には、処理を処理ブロック１３に移行し、処理を継続する。
【００１７】
処理ブロック１３では、処理ブロック５〜処理ブロック１３の繰り返し処理のためのループ数カウンターＬｏｏｐを１カウントアップし、処理を処理ブロック５に戻す。
【００１８】
このように、処理ブロック５〜処理ブロック１３の繰り返し処理の中で、“着目状態”から遷移可能と定義されている状態の中から評価の良い上位Ｍ個の状態を抽出し（処理ブロック５）、これらＭ個の状態への“着目状態”からの遷移により発生するＭ種の状態の変化の内のいくつかを“着目状態”に対して同時に発生させた場合の状態の評価を行い、その中で最も良い状態を“次の着目状態”にする（処理ブロック８、処理ブロック９）ことにより、“着目状態”の距離１以上の遷移を可能とし、探索効率の高い探索を可能としている。なお、上記の最も良い状態を選ぶ処理（“次の着目状態”を作る処理）は、Ｍ種の状態変化の全ての組合せ（２Ｍ個）から、１種のみを変化させた組合せ（既に評価済みのＭ個）と、まったく変化させない組合せ（１個）を除いた、（２Ｍ−Ｍ−１）個の状態の評価を行うことにより求まる。
【００１９】
図２は、この発明の実施の形態１による状態空間の探索方式の具体的な問題での働きを示す図である。
図３は、図２と同じ問題に対する従来の状態空間の探索方式の働きを示す図である。
図２は、「６ビットから成る２進数の内、２ビット以上に１が立っていなければならないという条件下で、最小の値を持つ２進数を見つける」問題に対する、実施の形態１による状態空間の探索方式の具体的な働きを“着目状態”の変化を中心に示している。
なお、評価関数値は、評価対象とする２進数の「数値＋ペナルティ（１が立っているビット数が２未満になった場合は１０００、それ以外では０）」とする。また、“着目状態”から遷移可能な状態は、６ビットの内の任意の１ビットの状態を反転させた状態とし、Ｍ＝２（図１処理ブロック５参照）とする。
【００２０】
処理ブロック１で、“着目状態”の初期設定“１１１１１１”を行い、処理ブロック２で、“着目状態”の評価関数値を６３と算出する。次いで、処理ブロック５で、“着目状態”から遷移可能な状態の内のベストＭ（Ｍ＝２）を抽出する。この結果、“０１１１１１”（評価関数値＝３１）と“１０１１１１”（評価関数値＝４７）の二つが抽出される。処理ブロック８で、抽出されたＭ個の状態への“着目状態”からの遷移により発生する状態変化の内のいくつかを“着目状態”に対して同時に発生させた状態のベスト１“００１１１１”（評価関数値＝１５）を抽出し、処理ブロック９で、これを新たな“着目状態”とする。
処理ブロック５に戻り、“着目状態”から遷移可能な状態の内のベストＭ（Ｍ＝２）を抽出する。この結果、“０００１１１”（評価関数値＝７）と“００１０１１”（評価関数値＝１１）の二つが抽出される。次いで、処理ブロック８で、抽出されたＭ個の状態への“着目状態”からの遷移により発生する状態変化の内のいくつかを“着目状態”に対して同時に発生させた状態のベスト１“００００１１”（評価関数値＝３）を抽出し、処理ブロック９で、これを新たな“着目状態”とする。この問題では、この状態が最適解となっている。
図２に示すように、実施の形態１によれば、“着目状態”の距離１以上の遷移が可能となり、この例題では、距離２の２回の遷移で、最適解を発見している。
【００２１】
一方、図３は、上記と同じ問題に対するＭ＝１の場合（従来方式と等価）の“着目状態”の変化を示しており、従来方式では、“着目状態”の遷移が距離１に限られるため、探索効率が悪く、この例題では、最適解の発見に距離１の４回の遷移を要している。
【００２２】
図２に示すような「０」あるいは「１」のように変化する要素を持つ配列に対して、各要素の「０」または「１」を最適に決定する問題は、非常に多く存在し、例えば、需要を満たし最小コストで発電するための発電計画問題は、どの時間帯にどの発電機を「停止状態：０」あるいは「発電状態：１」にすれば良いかを決定する問題となっており、要求される需要に対して過負荷なく送電損失を最小化するための系統計画問題は、どの遮断器を「切状態：０」あるいは「入状態：１」にすれば良いかを決定する問題となっている。このように、本発明の適用可能分野は非常に広範に存在している。
【００２３】
実施の形態１によれば、“着目状態”から遷移可能な状態の評価を行う過程で、評価の良い上位Ｍ個の状態を抽出し、これらの状態への“着目状態”からの遷移により発生するＭ種の状態変化の内のいくつかを、“着目状態”に対して同時に発生させることにより、“着目状態”の距離１以上の遷移が可能となり、探索の効率が向上するという効果が発揮される。
【００２４】
実施の形態２．
図４は、この発明の実施の形態２による状態空間の探索方式を示すフローチャートである。
図４は、図１との相違部分のみを示している。実施の形態２では、図１の処理ブロック８が図４のフローチャートで示す処理に変わる。
【００２５】
図４において、処理ブロック８１（第四の手順）では、“次の着目状態”（遷移先候補）として“着目状態”が初期設定される。
【００２６】
処理ブロック８２では、図１の処理ブロック５で抽出したＭ個の状態の内、未処理で最も評価の高い状態を抽出し、この状態を処理済みとすると共に、“着目状態”からこの状態への遷移により発生する状態の変化を“次の着目状態”に発生させた状態の評価関数値を計算する。
【００２７】
処理ブロック８３では、処理ブロック８２で計算した評価関数値が、“次の着目状態”の評価関数値よりも良いか否かを判定し、良い場合には、処理を処理ブロック８４に移行し、良くない場合には、処理を処理ブロック８５に移行する。
【００２８】
処理ブロック８４は、“次の着目状態”をより良い状態に更新するための処理であり、“次の着目状態”を、処理ブロック８２で評価した状態に更新する。（処理ブロック８２〜処理ブロック８４は、第五の手順を形成する。）
【００２９】
処理ブロック８５は、図１の処理ブロック８に対応する処理の終了を判定するための処理ブロックであり、図１の処理ブロック５で抽出したＭ個の状態の全てが処理ブロック８２で既に処理済とされている場合に、処理を終了し（処理を図１の処理ブロック９に移行し）、処理済みでないものが残っている場合には、処理を処理ブロック８２に戻し処理を継続する。
【００３０】
実施の形態２によれば、このように“次の着目状態”を作ることにより、“次の着目状態”をＭ個の状態の評価により求めることが可能となり、少ない演算量で“着目状態”の距離１以上の遷移が可能な探索を実現することが可能となる。
【００３１】
実施の形態３．
図５は、この発明の実施の形態３による状態空間の探索方式を示すフローチャートである。
図５は、図１との相違部分のみを示している。実施の形態３では、図１の処理ブロック８が図５のフローチャートで示す処理に変わる。
【００３２】
図５において、処理ブロック８１では、“次の着目状態”として“着目状態”が初期設定される。
【００３３】
処理ブロック８１ａでは、“次の着目状態”の更新回数を示すカウンターｋｓを０に初期設定する。
【００３４】
処理ブロック８２では、図１の処理ブロック５で抽出したＭ個の状態の内、未処理で最も評価の高い状態を抽出し、この状態を処理済みとすると共に、“着目状態”からこの状態への遷移により発生する状態の変化を“次の着目状態”に発生させた状態の評価関数値を計算する。
【００３５】
処理ブロック８３では、処理ブロック８２で計算した評価関数値が、“次の着目状態”の評価関数値よりも良いか否かを判定し、良い場合には、処理を処理ブロック８４ａに移行し、良くない場合には、処理を処理ブロック８５ａに移行する。
【００３６】
処理ブロック８４ａでは、“次の着目状態”の更新回数を示すカウンターｋｓを１カウントアップする。
【００３７】
処理ブロック８４は、“次の着目状態”をより良い状態に更新するための処理であり、“次の着目状態”を、処理ブロック８２で評価した状態に更新する。
【００３８】
処理ブロック８５ａでは、“次の着目状態”の更新回数を示すカウンターｋｓが指定値Ｋｓ（Ｋｓは、Ｍ＞Ｋｓ＞１を満足する整数）に達したかを調べ、達した場合には処理を終了し（処理を図１の処理ブロック９に移行し）、達していない場合には、処理を処理ブロック８５に移行する。（処理ブロック８２〜処理ブロック８５ａは、第五の手順を形成する。）
【００３９】
処理ブロック８５は、図１の処理ブロック８に対応する処理の終了を判定するための処理ブロックであり、図１の処理ブロック５で抽出したＭ個の状態の全てが処理ブロック８２で既に処理済とされている場合に、処理を終了し（処理を図１の処理ブロック９に移行し）、処理済みでないものが残っている場合には、処理を処理ブロック８２に戻し処理を継続する。
【００４０】
実施の形態３によれば、このように“着目状態”から“次の着目状態”までの距離がＫｓに達した場合に、これ以上距離の大きい“着目状態”の遷移は不要と判断し、直ちに処理を図１の処理ブロック９に移行することにより、少ない演算量で“着目状態”の距離１以上の遷移が可能な探索を実現する。
【００４１】
実施の形態４．
図６は、この発明の実施の形態４による状態空間の探索方式を示すフローチャートである。
図６は、図１との相違部分のみを示している。実施の形態４では、図１の処理ブロック８が図６のフローチャートで示す処理に変わる。
【００４２】
図６において、処理ブロック８１では、“次の着目状態”として“着目状態”が初期設定される。
【００４３】
処理ブロック８１ｂでは、“次の着目状態”の更新に連続して失敗した回数を示すカウンターｋｆを０に初期設定する。
【００４４】
処理ブロック８２では、図１の処理ブロック５で抽出したＭ個の状態の内、未処理で最も評価の高い状態を抽出し、この状態を処理済みとすると共に、“着目状態”からこの状態への遷移により発生する状態の変化を“次の着目状態”に発生させた状態の評価関数値を計算する。
【００４５】
処理ブロック８３では、処理ブロック８２で計算した評価関数値が、“次の着目状態”の評価関数値よりも良いか否かを判定し、良い場合には、処理を処理ブロック８４ｂ２に移行し、良くない場合には、処理を処理ブロック８４ｂ１に移行する。
【００４６】
処理ブロック８４ｂ１では、“次の着目状態”の更新に連続して失敗した回数を示すカウンターｋｆを１カウントアップする。
【００４７】
処理ブロック８４ｂ２では、“次の着目状態”の更新に連続して失敗した回数を示すカウンターｋｆを０クリアする。
【００４８】
処理ブロック８４は、“次の着目状態”をより良い状態に更新するための処理であり、“次の着目状態”を、処理ブロック８２で評価した状態に更新する。
【００４９】
処理ブロック８５ｂでは、“次の着目状態”の更新に連続して失敗した回数を示すカウンターｋｆが指定値Ｋｆ（Ｋｆは、Ｍ＞Ｋｆ≧１を満足する整数）に達したかを調べ、達している場合には処理を終了し（処理を図１の処理ブロック９に移行し）、達していない場合には、処理を処理ブロック８５に移行する。（処理ブロック８２〜処理ブロック８５ｂは、第五の手順を形成する。）
【００５０】
処理ブロック８５は、図１の処理ブロック８に対応する処理の終了を判定するための処理ブロックであり、図１の処理ブロック５で抽出したＭ個の状態の全てが処理ブロック８２で既に処理済とされている場合に、処理を終了し（処理を図１の処理ブロック９に移行し）、処理済みでないものが残っている場合には、処理を処理ブロック８２に戻し処理を継続する。
【００５１】
実施の形態４によれば、このように“次の着目状態”の更新が連続してＫｆ回失敗した場合に、これ以上の“次の着目状態”の更新は期待し難いと判断し、直ちに処理を図１の処理ブロック９に移行することにより、少ない演算量で“着目状態”の距離１以上の遷移が可能な探索を実現する。
【００５２】
実施の形態５．
図７は、この発明の実施の形態５による状態空間の探索方式を示すフローチャートである。
図７は、図１との相違部分のみを示している。実施の形態５では、図１の処理ブロック８が図７のフローチャートで示す処理に変わる。
【００５３】
図７において、処理ブロック８１では、“次の着目状態”として“着目状態”が初期設定される。
【００５４】
処理ブロック８１ｃでは、“次の着目状態”の更新回数を示すカウンターｋｓを０に初期設定すると共に、更新に連続して失敗した回数を示すカウンターｋｆを０に初期設定する。
【００５５】
処理ブロック８２では、図１の処理ブロック５で抽出したＭ個の状態の内、未処理で最も評価の高い状態を抽出し、この状態を処理済みとすると共に、“着目状態”からこの状態への遷移により発生する状態の変化を“次の着目状態”に発生させた状態の評価関数値を計算する。
【００５６】
処理ブロック８３では、処理ブロック８２で計算した評価関数値が、“次の着目状態”の評価関数値よりも良いか否かを判定し、良い場合には、処理を処理ブロック８４ｃに移行し、良くない場合には、処理を処理ブロック８４ｂ１に移行する。
【００５７】
処理ブロック８４ｂ１では、“次の着目状態”の更新に連続して失敗した回数を示すカウンターｋｆを１カウントアップする。
【００５８】
処理ブロック８４ｃでは、“次の着目状態”の更新回数を示すカウンターｋｓを１カウントアップすると共に、更新に連続して失敗した回数を示すカウンターｋｆを０クリアする。
【００５９】
処理ブロック８４は、“次の着目状態”をより良い状態に更新するための処理であり、“次の着目状態”を、処理ブロック８２で評価した状態に更新する。
【００６０】
処理ブロック８５ｃでは、“次の着目状態”の更新回数を示すカウンターｋｓが指定値Ｋｓに達した場合、あるいは、更新が連続して失敗した回数を示すカウンターｋｆが指定値Ｋｆに達した場合に、処理を終了し（処理を図１の処理ブロック９に移行し）、達していない場合には、処理を処理ブロック８５に移行する。（処理ブロック８２〜処理ブロック８５ｃは、第五の手順を形成する。）
【００６１】
処理ブロック８５は、図１の処理ブロック８に対応する処理の終了を判定するための処理ブロックであり、図１の処理ブロック５で抽出したＭ個の状態の全てが処理ブロック８２で既に処理済とされている場合に、処理を終了し（処理を図１の処理ブロック９に移行し）、処理済みでないものが残っている場合には、処理を処理ブロック８２に戻し処理を継続する。
【００６２】
実施の形態５によれば、このように“次の着目状態”　の更新回数を示すカウンターｋｓが指定値Ｋｓに達した場合、あるいは、更新が連続して失敗した回数を示すカウンターｋｆが指定値Ｋｆに達した場合に、これ以上の“次の着目状態”の更新は期待し難いと判断し、直ちに処理を図１の処理ブロック９に移行することにより、少ない演算量で“着目状態”の距離１以上の遷移が可能な探索を実現する。
【００６３】
実施の形態６．
図８は、この発明の実施の形態６による状態空間の探索方式を示すフローチャートである。
図８は、図１との相違部分のみを示している。実施の形態６では、図１の処理ブロック８が図８のフローチャートで示す処理に変わる。
【００６４】
図８において、処理ブロック８１では、“次の着目状態”として“着目状態”が初期設定される。
【００６５】
処理ブロック８１ｄでは、“次の着目状態”の更新を試みた回数を示すカウンターｋを０に初期設定すると共に、“次の着目状態”の更新に連続して失敗した回数を示すカウンターｋｆを０に初期設定する。
【００６６】
処理ブロック８２ｄでは、次の着目状態”の更新を試みた回数を示すカウンターｋを１カウントアップする。
【００６７】
処理ブロック８２では、図１の処理ブロック５で抽出したＭ個の状態の内、未処理で最も評価の高い状態を抽出し、この状態を処理済みとすると共に、“着目状態”からこの状態への遷移により発生する状態の変化を“次の着目状態”に発生させた状態の評価関数値を計算する。
【００６８】
処理ブロック８３では、処理ブロック８２で計算した評価関数値が、“次の着目状態”の評価関数値よりも良いか否かを判定し、良い場合には、処理を処理ブロック８４ｂ２に移行し、良くない場合には、処理を処理ブロック８４ｂ１に移行する。
【００６９】
処理ブロック８４ｂ１では、“次の着目状態”の更新に連続して失敗した回数を示すカウンターｋｆを１カウントアップする。
【００７０】
処理ブロック８４ｂ２では、“次の着目状態”の更新に連続して失敗した回数を示すカウンターｋｆを０クリアする。
【００７１】
処理ブロック８４は、“次の着目状態”をより良い状態に更新するための処理であり、“次の着目状態”を、処理ブロック８２で評価した状態に更新する。
【００７２】
処理ブロック８５ｄでは、“次の着目状態”の更新を試みた回数を示すカウンターｋが指定値Ｋ（Ｋは、Ｍ＞Ｋ＞１を満足する整数）に達しており、かつ、“次の着目状態”の更新に連続して失敗した回数を示すカウンターｋｆが指定値Ｋｆに達した場合には、処理を終了し（処理を図１の処理ブロック９に移行し）、達していない場合には、処理を処理ブロック８５に移行する。（処理ブロック８２〜処理ブロック８５ｄは、第五の手順を形成する。）
【００７３】
処理ブロック８５は、図１の処理ブロック８に対応する処理の終了を判定するための処理ブロックであり、図１の処理ブロック５で抽出したＭ個の状態の全てが処理ブロック８２で既に処理済とされている場合に、処理を終了し（処理を図１の処理ブロック９に移行し）、処理済みでないものが残っている場合には、処理を処理ブロック８２ｄに戻し処理を継続する。
【００７４】
実施の形態６によれば、このように“次の着目状態”の更新を試みた回数を示すカウンターｋが指定値Ｋに達し、かつ、“次の着目状態”の更新に連続して失敗した回数を示すカウンターｋｆが指定値Ｋｆに達した場合に、これ以上の“次の着目状態”の更新は期待し難いと判断し、直ちに処理を図１の処理ブロック９に移行することにより、少ない演算量で“着目状態”の距離１以上の遷移が可能な探索を実現する。
【００７５】
【発明の効果】
この発明は、以上説明したように構成されているので、以下に示すような効果を奏する。
それぞれ変化する複数の要素の組合せを表す状態の集まりである状態空間の中を、一つの状態から他の状態への遷移を繰り返して最良の状態を探索する状態空間の探索方式において、指定された状態を最初の“着目状態”とし、“着目状態”から遷移可能と定義される複数の状態の中から評価関数を用いた評価に基づき上位Ｍ個の状態を選択する第一の手順と、この第一の手順によって選択されたＭ個の状態へ“着目状態”からそれぞれ遷移するとき発生するＭ種の変化の内の複数種を、“着目状態”に対し同時に発生させた場合に形成される各状態について評価関数に基づき評価し、これらの内で最もよい評価関数値をもつ状態を選出する第二の手順と、この第二の手順によって選出された最もよい評価関数値をもつ状態へ“着目状態”から遷移を行い、新たな“着目状態”とする第三の手順を含むので、“着目状態”から距離１以上の遷移が可能となり、探索の効率が向上するという効果が得られる。
【００７６】
また、第二の手順は、“着目状態”を遷移先候補として初期設定する第四の手順と、遷移先候補に対し、“着目状態”からＭ個の状態の内の一つへと遷移するとき発生する変化を、Ｍ個の状態の内の評価関数値のよい順に順次、発生させ、そのつど、変化によって形成される状態の評価関数値と遷移先候補の評価関数値とを比較し、変化によって形成される状態の評価関数値が遷移先候補の評価関数値よりよくなった場合に、変化によって形成される状態を新たな遷移先候補とする動作を繰り返すことにより、最新の遷移先候補を最もよい評価関数値をもつ状態とする第五の手順とを含むので、効率のよい演算により“着目状態”の距離１以上の遷移が可能な探索を実現することが可能となる。
また、第五の手順は、変化によって形成される状態の評価関数値が遷移先候補の評価関数値よりよくなった場合がＫｓ回に達するまで動作を繰り返すので、変化によって形成される状態の評価関数値が遷移先候補の評価関数値よりよくなった場合の回数により、動作回数を制限して、少ない演算量で“着目状態”の距離１以上の遷移が可能な探索を実現する。
【００７７】
さらに、第五の手順は、変化によって形成される状態の評価関数値が遷移先候補の評価関数値よりよくならない場合が連続してＫｆ回に達するまで動作を繰り返すので、変化によって形成される状態の評価関数値が遷移先候補の評価関数値よりよくならない場合が連続する回数により、動作回数を制限して、少ない演算量で“着目状態”の距離１以上の遷移が可能な探索を実現する。
また、第五の手順は、変化によって形成される状態の評価関数値が遷移先候補の評価関数値よりよくなった場合がＫｓ回に達するまで、または変化によって形成される状態の評価関数値が遷移先候補の評価関数値よりよくならない場合が連続してＫｆ回に達するまで動作を繰り返すので、変化によって形成される状態の評価関数値が遷移先候補の評価関数値よりよくなった場合の回数または変化によって形成される状態の評価関数値が遷移先候補の評価関数値よりよくならない場合が連続する回数により、動作回数を制限して、少ない演算量で“着目状態”の距離１以上の遷移が可能な探索を実現する。
【００７８】
加えて、第五の手順は、動作がＫ回に達し、かつ変化によって形成される状態の評価関数値が遷移先候補の評価関数値よりよくならない場合が連続してＫｆ回に達するまで動作を繰り返すので、動作回数及び変化によって形成される状態の評価関数値が遷移先候補の評価関数値よりよくならない場合が連続する回数により、動作回数を制限して、少ない演算量で“着目状態”の距離１以上の遷移が可能な探索を実現する。
【図面の簡単な説明】
【図１】この発明の実施の形態１による状態空間の探索方式を示すフローチャートである。
【図２】この発明の実施の形態１による状態空間の探索方式の具体的な問題での働きを示す図である。
【図３】図２と同じ問題に対する従来の状態空間の探索方式の働きを示す図である。
【図４】この発明の実施の形態２による状態空間の探索方式を示すフローチャートである。
【図５】この発明の実施の形態３による状態空間の探索方式を示すフローチャートである。
【図６】この発明の実施の形態４による状態空間の探索方式を示すフローチャートである。
【図７】この発明の実施の形態５による状態空間の探索方式を示すフローチャートである。
【図８】この発明の実施の形態６による状態空間の探索方式を示すフローチャートである。
【符号の説明】
１〜１３　処理ブロック、８１〜８５　処理ブロック。
【図１】
2004070662.tif 000003
【図２】
2004070662.tif 000004
【図３】
2004070662.tif 000005
【図４】
2004070662.tif 000006
【図５】
2004070662.tif 000007
【図６】
2004070662.tif 000008
【図７】
2004070662.tif 000009
【図８】
2004070662.tif 000010