特許ウォッチ

公開番号2024067646
公報種別公開特許公報(A)
公開日2024-05-17
出願番号2022177880
出願日2022-11-07
発明の名称探索プログラム、探索システム、及び探索方法
出願人富士通株式会社
代理人個人,個人,個人
主分類G06N 99/00 20190101AFI20240510BHJP(計算;計数)
要約【課題】複数の制約条件を含む制約情報を充足する解を探索する解探索を高速化する。
【解決手段】コンピュータは、複数の制約条件を含む制約情報を充足する解の候補となる解候補を生成する。コンピュータは、複数の制約条件のうち解候補が充足する制約条件の個数に基づいて、解候補に含まれる複数の変数値各々が変更される確率を制御する制御パラメータを決定する。コンピュータは、制御パラメータに基づいて、解候補に含まれる複数の変数値各々を変更するか否かを決定する。コンピュータは、解候補に含まれる複数の変数値各々を変更するか否かに基づいて、解に含まれる複数の変数値の組み合わせを探索する。
【選択図】図2
特許請求の範囲【請求項１】
複数の制約条件を含む制約情報を充足する解の候補となる解候補を生成し、
前記複数の制約条件のうち前記解候補が充足する制約条件の個数に基づいて、前記解候補に含まれる複数の変数値各々が変更される確率を制御する制御パラメータを決定し、
前記制御パラメータに基づいて、前記複数の変数値各々を変更するか否かを決定し、
前記複数の変数値各々を変更するか否かに基づいて、前記解に含まれる複数の変数値の組み合わせを探索する、
処理をコンピュータに実行させるための探索プログラム。
続きを表示（約 810 文字）【請求項２】
前記制御パラメータを決定する処理は、
前記複数の制約条件の個数に対する前記解候補が充足する制約条件の個数の比率を求める処理と、
前記比率が所定値よりも大きい場合、前記制御パラメータの値を前記確率が減少するような値に変更する処理と、
を含むことを特徴とする請求項１記載の探索プログラム。
【請求項３】
前記制御パラメータを決定する処理は、前記複数の制約条件の個数に対する、前記解候補よりも前に生成された別の解候補が充足する制約条件の個数の比率に基づいて、前記所定値を決定する処理をさらに含むことを特徴とする請求項２記載の探索プログラム。
【請求項４】
制約情報に含まれる複数の制約条件のうち、前記制約情報を充足する解の候補となる解候補が充足する制約条件の個数に基づいて、前記解候補に含まれる複数の変数値各々が変更される確率を制御する制御パラメータを決定する決定部と、
前記制御パラメータに基づいて、前記複数の変数値各々を変更するか否かを決定し、前記複数の変数値各々を変更するか否かに基づいて、前記解に含まれる複数の変数値の組み合わせを探索する探索部と、
を備えることを特徴とする探索システム。
【請求項５】
複数の制約条件を含む制約情報を充足する解の候補となる解候補を生成し、
前記複数の制約条件のうち前記解候補が充足する制約条件の個数に基づいて、前記解候補に含まれる複数の変数値各々が変更される確率を制御する制御パラメータを決定し、
前記制御パラメータに基づいて、前記複数の変数値各々を変更するか否かを決定し、
前記複数の変数値各々を変更するか否かに基づいて、前記解に含まれる複数の変数値の組み合わせを探索する、
処理をコンピュータが実行することを特徴とする探索方法。

発明の詳細な説明【技術分野】
【０００１】
本発明は、探索技術に関する。
続きを表示（約 1,000 文字）【背景技術】
【０００２】
様々な情報処理システムの挙動を決定する際に、組み合わせ最適化問題の解が求められることがある。組み合わせ最適化問題は、しばしば、充足可能性（Satisfiability，ＳＡＴ）問題として定式化される。
【０００３】
充足可能性問題は、複数の節の論理積である命題論理式に含まれる複数の変数各々の変数値を真又は偽に設定することで、命題論理式が真となる変数値の組み合わせを解として求める問題である。
【０００４】
充足可能性問題に関して、最適解を高速かつ効率的に探索する解探索システムが知られている（例えば、特許文献１を参照）。AmoebaSATアルゴリズムを活用したＦＰＧＡ（Field-Programmable Gate Array）ベースのＳＡＴソルバも知られている（例えば、非特許文献１を参照）。
【先行技術文献】
【特許文献】
【０００５】
国際公開第２０２２／０９７４６０号
【非特許文献】
【０００６】
A. H. N. Nguyen et al., “FPGA-Based Hardware/Software Co-Design of a Bio-Inspired SAT Solver”, in IEEE Access, vol. 8, pages 49053-49065, 2020.
【発明の概要】
【発明が解決しようとする課題】
【０００７】
非特許文献１に記載されたAmoebaSATアルゴリズムは、ハードウェア実装に対する高い並列性と高い実現可能性を有する。しかしながら、AmoebaSATアルゴリズムを活用したＳＡＴソルバにより、充足可能性問題における解探索を行う場合、解が得られるまでに長い時間がかかることがある。
【０００８】
なお、かかる問題は、AmoebaSATアルゴリズムを活用したＳＡＴソルバに限らず、複数の制約条件を含む制約情報を充足する解を探索する様々な解探索において生ずるものである。
【０００９】
１つの側面において、本発明は、複数の制約条件を含む制約情報を充足する解を探索する解探索を高速化することを目的とする。
【課題を解決するための手段】
【００１０】
１つの案では、探索プログラムは、以下の処理をコンピュータに実行させる。
（【００１１】以降は省略されています）

関連特許