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

発明の詳細な説明【技術分野】
【0001】
本発明は、探索技術に関する。
続きを表示(約 1,000 文字)【背景技術】
【0002】
様々な情報処理システムの挙動を決定する際に、組み合わせ最適化問題の解が求められることがある。組み合わせ最適化問題は、しばしば、充足可能性(Satisfiability,SAT)問題として定式化される。
【0003】
充足可能性問題は、複数の節の論理積である命題論理式に含まれる複数の変数各々の変数値を真又は偽に設定することで、命題論理式が真となる変数値の組み合わせを解として求める問題である。
【0004】
充足可能性問題に関して、最適解を高速かつ効率的に探索する解探索システムが知られている(例えば、特許文献1を参照)。AmoebaSATアルゴリズムを活用したFPGA(Field-Programmable Gate Array)ベースのSATソルバも知られている(例えば、非特許文献1を参照)。
【先行技術文献】
【特許文献】
【0005】
国際公開第2022/097460号
【非特許文献】
【0006】
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.
【発明の概要】
【発明が解決しようとする課題】
【0007】
非特許文献1に記載されたAmoebaSATアルゴリズムは、ハードウェア実装に対する高い並列性と高い実現可能性を有する。しかしながら、AmoebaSATアルゴリズムを活用したSATソルバにより、充足可能性問題における解探索を行う場合、解が得られるまでに長い時間がかかることがある。
【0008】
なお、かかる問題は、AmoebaSATアルゴリズムを活用したSATソルバに限らず、複数の制約条件を含む制約情報を充足する解を探索する様々な解探索において生ずるものである。
【0009】
1つの側面において、本発明は、複数の制約条件を含む制約情報を充足する解を探索する解探索を高速化することを目的とする。
【課題を解決するための手段】
【0010】
1つの案では、探索プログラムは、以下の処理をコンピュータに実行させる。
(【0011】以降は省略されています)

この特許をJ-PlatPatで参照する

関連特許

個人
暗号化記憶媒体
27日前
個人
求人支援システム
16日前
カゴメ株式会社
営農支援プログラム
1か月前
カゴメ株式会社
営農支援プログラム
1か月前
カゴメ株式会社
営農支援プログラム
1か月前
カゴメ株式会社
営農支援プログラム
1か月前
株式会社ワコム
電子ペン
2日前
アスエネ株式会社
水管理の方法
1か月前
株式会社ワコム
電子ペン
1か月前
株式会社ワコム
電子ペン
28日前
シャープ株式会社
情報出力装置
14日前
東洋電装株式会社
操作装置
2日前
東洋電装株式会社
操作装置
2日前
東洋電装株式会社
操作装置
2日前
大日本印刷株式会社
作業台
1か月前
CKD株式会社
遠隔支援システム
1か月前
株式会社寺岡精工
システム
1か月前
日本信号株式会社
料金精算システム
12日前
株式会社カロニマ
情報発信システム
6日前
トヨタ紡織株式会社
検査装置
23日前
BH株式会社
商品販売システム
1か月前
株式会社アジラ
異常行動検出システム
23日前
シーアンドアールエム株式会社
広告装置
9日前
個人
特許審査支援ボットおよびボットシステム
13日前
株式会社mov
情報処理システム
22日前
個人
AI営業システム
26日前
個人
スマートフォンにおける使用料金削減方法
13日前
富士フイルム株式会社
タッチセンサ
9日前
株式会社セガ
情報処理装置及びプログラム
29日前
株式会社and.d
商品の推奨方法
1日前
トヨタ自動車株式会社
文字認識装置
23日前
個人
取引システム、取引方法及び取引プログラム
今日
トヨタ自動車株式会社
文字抽出方法
9日前
ソニーグループ株式会社
装置
1か月前
株式会社セガ
情報処理装置及びプログラム
29日前
シャープ株式会社
ウェアラブル機器
16日前
続きを見る