特許ウォッチ

公開番号2025027318
公報種別公開特許公報(A)
公開日2025-02-27
出願番号2023132018
出願日2023-08-14
発明の名称演算プログラム、演算方法、および情報処理装置
出願人富士通株式会社
代理人個人
主分類G06N 99/00 20190101AFI20250219BHJP(計算;計数)
要約【課題】計算時間を短縮することができる演算プログラム、演算方法、及び情報処理装置を提供する。
【解決手段】各ノードが少なくともいずれかの他のノードに対してエッジによって接続され、エッジにはそれぞれ重み値が設定されている計算対象について、分割数を指定せずにカット問題計算を行い、得られた計算結果のうち、重み値の合計値が第1条件を満たす計算結果を特定する第1処理と、第1処理で特定された計算結果から、分割数ごとに第2条件を満たす計算結果を特定する第2処理と、第2処理では特定できなかった分割数のそれぞれについて、分割数を指定したカット問題計算を行い、分割数ごとに、重み値の合計値が第3条件を満たす計算結果を特定する第3処理と、各分割数について、第2処理および第3処理で特定された重み値の合計値を所定関数で正規化した正規化値を算出し、正規化値のなかで第4条件を満たす分割数を取得する第4処理と、を実行させる。
【選択図】図7

特許請求の範囲【請求項１】
複数のノードを備え、各ノードが少なくともいずれかの他のノードに対してエッジによって接続され、前記エッジにはそれぞれ重み値が設定されている計算対象について、前記複数のノードを２つのグループに分割する際にカットした前記エッジの前記重み値の合計値を計算するカット問題計算を行う演算プログラムであって、
コンピュータに、
分割される２つのグループに属するノード数である分割数を指定せずに前記カット問題計算を行い、得られた計算結果のうち、前記重み値の合計値が第１条件を満たす計算結果を特定する第１処理と、
前記第１処理で特定された計算結果から、分割数ごとに第２条件を満たす計算結果を特定する第２処理と、
前記第２処理では特定できなかった分割数のそれぞれについて、前記分割数を指定した前記カット問題計算を行い、分割数ごとに、前記重み値の合計値が第３条件を満たす計算結果を特定する第３処理と、
各分割数について、前記第２処理および前記第３処理で特定された前記重み値の合計値を所定関数で正規化した正規化値を算出し、前記正規化値のなかで第４条件を満たす分割数を取得する第４処理と、を実行させることを特徴とする演算プログラム。
続きを表示（約 2,000 文字）【請求項２】
前記第１処理では、得られた計算結果のうち、前記重み値の合計値が最小となる上位所定数の計算結果を特定し、
前記第２処理では、前記第１処理で特定された計算結果から、分割数ごとに前記重み値の合計値が最小となる計算結果を特定し、
前記第３処理では、前記第２処理では特定できなかった分割数のそれぞれについて、分割数を指定した前記カット問題計算を行い、分割数ごとに、重み値の合計値が最小となる計算結果を特定し、
前記第４処理では、各分割数について、前記第２処理および前記第３処理で特定された前記重み値の合計値について前記所定関数で正規化された正規化値を算出し、前記正規化値のなかで最小となる分割数を取得する、ことを特徴とする請求項１に記載の演算プログラム。
【請求項３】
前記第１処理では、得られた計算結果のうち、前記重み値の合計値が最大となる上位所定数の計算結果を特定し、
前記第２処理では、前記第１処理で特定された計算結果から、分割数ごとに前記重み値の合計値が最大となる計算結果を特定し、
前記第３処理では、前記第２処理では取得できなかった分割数のそれぞれについて、分割数を指定した前記カット問題計算を行い、分割数ごとに、重み値の合計値が最大となる計算結果を特定し、
前記第４処理では、各分割数について、前記第２処理および前記第３処理で特定された前記重み値の合計値について前記所定関数で正規化された正規化値を算出し、前記正規化値のなかで最大となる分割数を取得する、ことを特徴とする請求項１に記載の演算プログラム。
【請求項４】
前記所定関数は、前記重み値の合計値を、分割後の一方のグループの前記エッジの総和とカットされた前記エッジの重みの総和との合計で除した値と、分割後の他方のグループの前記エッジの総和とカットされた前記エッジの重みの総和との合計で除した値との合計を算出する関数であることを特徴とする請求項１に記載の演算プログラム。
【請求項５】
前記ノードは、遺伝子配列であり、
前記エッジの重み値は、遺伝子配列同士の相関度であることを特徴とする請求項１に記載の演算プログラム。
【請求項６】
複数のノードを備え、各ノードが少なくともいずれかの他のノードに対してエッジによって接続され、前記エッジにはそれぞれ重み値が設定されている計算対象について、前記複数のノードを２つのグループに分割する際にカットした前記エッジの前記重み値の合計値を計算するカット問題計算を行う演算方法であって、
コンピュータが、
分割される２つのグループに属するノード数である分割数を指定せずに前記カット問題計算を行い、得られた計算結果のうち、前記重み値の合計値が第１条件を満たす計算結果を特定する第１処理と、
前記第１処理で特定された計算結果から、分割数ごとに第２条件を満たす計算結果を特定する第２処理と、
前記第２処理では特定できなかった分割数のそれぞれについて、前記分割数を指定した前記カット問題計算を行い、分割数ごとに、前記重み値の合計値が第３条件を満たす計算結果を特定する第３処理と、
各分割数について、前記第２処理および前記第３処理で特定された前記重み値の合計値を所定関数で正規化した正規化値を算出し、前記正規化値のなかで第４条件を満たす分割数を取得する第４処理と、を実行することを特徴とする演算方法。
【請求項７】
複数のノードを備え、各ノードが少なくともいずれかの他のノードに対してエッジによって接続され、前記エッジにはそれぞれ重み値が設定されている計算対象について、前記複数のノードを２つのグループに分割する際にカットした前記エッジの前記重み値の合計値を計算するカット問題計算を行う情報処理装置であって、
分割される２つのグループに属するノード数である分割数を指定せずに前記カット問題計算を行い、得られた計算結果のうち、前記重み値の合計値が第１条件を満たす計算結果を特定する第１処理と、前記第１処理で特定された計算結果から、分割数ごとに第２条件を満たす計算結果を特定する第２処理と、前記第２処理では特定できなかった分割数のそれぞれについて、前記分割数を指定した前記カット問題計算を行い、分割数ごとに、前記重み値の合計値が第３条件を満たす計算結果を特定する第３処理と、各分割数について、前記第２処理および前記第３処理で特定された前記重み値の合計値を所定関数で正規化した正規化値を算出し、前記正規化値のなかで第４条件を満たす分割数を取得する第４処理と、を実行する演算部を備えることを特徴とする情報処理装置。

発明の詳細な説明【技術分野】
【０００１】
本件は、演算プログラム、演算方法、および情報処理装置に関する。
続きを表示（約 1,800 文字）【背景技術】
【０００２】
計算対象に対して、最小カット問題または最大カット問題を計算する手法が開示されている（例えば、特許文献１，２参照）。
【先行技術文献】
【特許文献】
【０００３】
特開２０２０－００４３８７号公報
特開２０２１－０８１８６３号公報
【発明の概要】
【発明が解決しようとする課題】
【０００４】
しかしながら、最小カット問題や最大カット問題を計算しようとすると、長時間を要する。
【０００５】
１つの側面では、本件は、計算時間を短縮することができる演算プログラム、演算方法、および情報処理装置を提供することを目的とする。
【課題を解決するための手段】
【０００６】
１つの態様では、演算プログラムは、複数のノードを備え、各ノードが少なくともいずれかの他のノードに対してエッジによって接続され、前記エッジにはそれぞれ重み値が設定されている計算対象について、前記複数のノードを２つのグループに分割する際にカットした前記エッジの前記重み値の合計値を計算するカット問題計算を行う演算プログラムであって、コンピュータに、分割される２つのグループに属するノード数である分割数を指定せずに前記カット問題計算を行い、得られた計算結果のうち、前記重み値の合計値が第１条件を満たす計算結果を特定する第１処理と、前記第１処理で特定された計算結果から、分割数ごとに第２条件を満たす計算結果を特定する第２処理と、前記第２処理では特定できなかった分割数のそれぞれについて、前記分割数を指定した前記カット問題計算を行い、分割数ごとに、前記重み値の合計値が第３条件を満たす計算結果を特定する第３処理と、各分割数について、前記第２処理および前記第３処理で特定された前記重み値の合計値を所定関数で正規化した正規化値を算出し、前記正規化値のなかで第４条件を満たす分割数を取得する第４処理と、を実行させる。
【発明の効果】
【０００７】
計算時間を短縮することができる。
【図面の簡単な説明】
【０００８】
（ａ）および（ｂ）は複数のノードを備えるグラフを例示する図である。
ノード数ｎが８個である場合について説明するための図である。
（ａ）および（ｂ）はカットの例を表す図である。
（ａ）および（ｂ）は計算結果を例示する図である。
階層的クラスタリングを例示する図である。
求解に要する時間を例示する図である。
Ｍ個の総和Ｅが登録されたリストを例示する図である。
解ｘの推移を例示する図である。
（ａ）は情報処理装置の全体構成を例示するブロック図であり、（ｂ）は情報処理装置のハードウェア構成を例示するブロック図である。
（ａ）は情報処理装置が処理１を実行する場合の動作の一例を表すフローチャートであり、（ｂ）はリストＬ１を例示する図である。
（ａ）は情報処理装置が処理２を実行する場合の動作の一例を表すフローチャートであり、（ｂ）はリストＬ２を例示する図である。
情報処理装置が処理３を実行する場合の動作の一例を表すフローチャートである。
（ａ）は情報処理装置が処理４を実行する場合の動作の一例を表すフローチャートであり、（ｂ）はリストＬ３を例示する図である。
比較例に係る処理を例示するフローチャートである。
ＱＵＢＯ形式を例示する図である。
【発明を実施するための形態】
【０００９】
実施例の説明に先立って、最大カット問題（ＭａｘＣｕｔ問題）および最小カット問題（ＭｉｎＣｕｔ問題）の概要について説明する。
【００１０】
最大カット問題とは、重み付きグラフに対して頂点(ノード)を２つのグループに分割する問題であって、２つのグループに分割した際にカットされたエッジの重みの総和が最大となるように分割する問題のことである。最小カット問題とは、重み付きグラフに対して頂点(ノード)を２つのグループに分割する問題であって、２つのグループに分割した際にカットされたエッジの重みの総和が最小となるように分割する問題のことである。
（【００１１】以降は省略されています）

関連特許