(57)【要約】［課題］組み合わせの生成に伴う加算処理、シフト処理及び比較処理の演算時間の、桁数の増加に伴う増大が少ない組み合わせ生成装置を提供する。［解決手段］本発明の組み合わせ生成装置は、入力ビット列から、反転を行うビットの位置である反転ビット位置と、シフトにより最下位ビットにするビットの位置であるシフトビット位置とを、所定の基準により求め、シフトビット位置のビットを最下位ビットにシフトするのに要するシフト幅を求めるビット位置取得手段と、前記入力ビット列の、前記ビット位置取得手段が求めた反転ビット位置のビットの値と、それより１ビット下位に位置するビットの値とを反転するビット反転手段と、前記ビット反転手段が反転を行ったビット列の、前記反転ビット位置から２ビット下位のビット以下に位置する全てのビットを、前記ビット位置取得手段が求めた前記シフト幅だけシフトするビットシフト手段と、を含む。
2010107102.tif 000002
【特許請求の範囲】
【請求項１】
入力ビット列から、反転を行うビットの位置である反転ビット位置と、シフトにより最下位ビットにするビットの位置であるシフトビット位置とを、所定の基準により求め、シフトビット位置のビットを最下位ビットにシフトするのに要するシフト幅を求めるビット位置取得手段と、
前記入力ビット列の、前記ビット位置取得手段が求めた反転ビット位置のビットの値と、それより１ビット下位に位置するビットの値とを反転するビット反転手段と、
前記ビット反転手段が反転を行ったビット列の、前記反転ビット位置から２ビット下位のビット以下に位置する全てのビットを、前記ビット位置取得手段が求めた前記シフト幅だけシフトするビットシフト手段と、
を含むことを特徴とする組み合わせ生成装置。
【請求項２】
前記ビット位置取得手段は、値が“１”であるビットのうち最も下位に位置するビットである下位ビットの位置を前記シフトビット位置として求め、前記下位ビットよりも上位に位置するビットで、値が“０”であるビットの位置を前記反転ビット位置として求め、
前記ビット反転手段は、前記反転ビット位置に位置するビットのビット値と、それより１ビット下位に位置するビットのビット値とを反転し、
前記ビットシフト手段は、前記反転ビット位置から２ビット下位のビット以下に位置する全てのビットを、前記下位ビットが最下位のビットになるようにシフトする
ことを特徴とする請求項１に記載の組み合わせ生成装置。
【請求項３】
前記入力ビット列から、最上位ビットから前記反転ビット位置より１ビット下位に位置するビットまでのビットの並びが前記入力ビット列と同じであり、他のビットは所定の値である上位ビット列と、前記反転ビット位置より２ビット下位に位置するビットから最下位ビットまでのビットの並びが前記入力ビット列と同じであり、他のビットは所定の値である下位ビット列とを生成し、前記上位ビット列を前記ビット反転手段に入力し、前記下位ビット列を前記ビットシフト手段に入力するビット分割手段と、
前記ビット反転手段から出力されるビット列の、最上位ビットから前記反転ビット位置より１ビット下位に位置するビットまでのビット列と、前記ビットシフト手段から出力されるビット列の、前記反転ビット位置より２ビット下位に位置するビットから最下位ビットまでのビット列とを結合するビット結合手段と、を含み、
前記ビット反転手段と、前記ビットシフト手段とで行われる処理を並列に実行することを特徴とする請求項１又は２に記載の組み合わせ生成装置。
【請求項４】
前記入力ビット列を入力とする、組み合わせ生成が可能か否かを判断するとともに、組み合わせ生成処理の終了条件を設定する入力チェック手段と、
前記終了条件を満たすか否かを判定し、前記終了条件を満たした場合、組み合わせ生成処理を終了し、前記終了条件を満たしていない場合、生成したビット列を次の入力ビット列とする終了判定手段と、
前記入力チェック手段により、組み合わせ生成が可能と判断された前記入力ビット列と、前記終了判定手段が次の入力ビット列としたビット列とから、いずれかのビット列を入力ビット列として選択し、選択した前記入力ビット列を前記ビット位置取得手段に出力するアービターと、を含むことを特徴とする請求項１から３のいずれかに記載の組み合わせ生成装置。
【請求項５】
前記ビット位置取得手段が、
前記入力ビット列の、値が“１”であるビットのうち最も下位に位置するビットを、前記シフトビット位置として求め、前記入力ビット列と同一ビット幅で、前記シフトビット位置より下位の全てのビット値が“１”であるビット列を生成する、ビット値”１”の最下位ビット位置取得手段と、
少なくとも前記シフトビット位置より下位に位置する全てのビットで、前記入力ビット列と、前記ビット値”１”の最下位ビット位置取得手段が生成した前記ビット列との論理和をとり、最上位ビットから前記シフトビット位置のビットまでのビット値が前記入力ビット列と同一であり、前記シフトビット位置より下位のビットのビット値が全て“１”であるビット列を生成する論理和演算手段と、
前記論理和演算手段が生成したビット列から、値が“０”であるビットのうち、最も下位に位置するビットを、前記反転ビット位置として求める、ビット値”０”の最下位ビット位置取得手段と、
を含むことを特徴とする請求項２から４のいずれかに記載の組み合わせ生成装置。
【請求項６】
前記ビット位置取得手段は、入力されたビット列に対して複数ビット同時に処理を行う回路を備えることを特徴とする請求項１から５のいずれかに記載の組み合わせ生成装置。
【請求項７】
前記ビット位置取得手段は、ビット長が、入力されたビット列のビット長以下であるビット列に対してビット位置取得処理を行う部分ビット列処理手段を１つ以上含み、
入力されたビット列を分割し、分割した各部分ビット列を、それぞれ異なる部分ビット列処理手段に入力することで、並列に処理を行う階層構造を備えることを特徴とする請求項１から６のいずれかに記載の組み合わせ生成装置。
【請求項８】
パイプライン化するための１つ以上のパイプラインレジスタを含むことを特徴とする請求項１から７のいずれかに記載の組み合わせ生成装置。
【請求項９】
前記ビットシフト手段から出力される各組み合わせのビット列に対して、コスト計算を行うためのパラメータを用いてコストを計算するコスト計算手段と、
前記コスト計算手段が計算した前記コストを基にして、前記ビット列からビット列を選択する解選択手段と、
を含むことを特徴とする請求項１から８のいずれかに記載の組み合わせ生成装置。
【請求項１０】
入力ビット列から、反転を行うビットの位置である反転ビット位置と、シフトにより最下位ビットにするビットの位置であるシフトビット位置とを、所定の基準により求め、シフトビット位置のビットを最下位ビットにシフトするのに要するシフト幅を求めるビット位置取得手段と、
前記入力ビット列の、前記ビット位置取得手段が求めた反転ビット位置のビットの値と、それより１ビット下位に位置するビットの値とを反転するビット反転手段と、
前記ビット反転手段が反転を行ったビット列の、前記反転ビット位置から２ビット下位のビット以下に位置する全てのビットを、前記ビット位置取得手段が求めた前記シフト幅だけシフトするビットシフト手段と、
を含む組み合わせ生成装置と、
前記ビットシフト手段から出力される各組み合わせのビット列に対して、コスト計算を行うためのパラメータを用いてコストを計算するコスト計算手段と、
前記コスト計算手段が計算した前記コストを基にして、前記ビット列からビット列を選択する解選択手段と、
を含む、前記組み合わせ生成装置によって生成されたビット列から、所定の基準によりビット列を選択する解選択装置と、
を含む、組み合わせ最適化問題求解システム。
【請求項１１】
組み合わせ生成装置が、
入力ビット列から、反転を行うビットの位置である反転ビット位置と、シフトにより最下位ビットにするビットの位置であるシフトビット位置とを、所定の基準により求め、シフトビット位置のビットを最下位ビットにシフトするのに要するシフト幅を求め、
前記入力ビット列の、前記反転ビット位置のビットの値と、それより１ビット下位に位置するビットの値とを反転し、
前記反転を行ったビット列の、前記反転ビット位置から２ビット下位のビット以下に位置する全てのビットを、前記シフト幅だけシフトする、
組み合わせ生成装置による組み合わせ生成方法。
【請求項１２】
組み合わせ生成装置が、
前記ビット位置取得手段は、値が“１”であるビットのうち最も下位に位置するビットである下位ビットの位置を前記シフトビット位置として求め、前記下位ビットよりも上位に位置するビットで、値が“０”であるビットの位置を前記反転ビット位置として求め、
前記ビット反転手段は、前記反転ビット位置に位置するビットのビット値と、それより１ビット下位に位置するビットのビット値とを反転し、
前記ビットシフト手段は、前記反転ビット位置から２ビット下位のビット以下に位置する全てのビットを、前記下位ビットが最下位のビットになるようにシフトする、
請求項１１に記載の組み合わせ生成方法。
【請求項１３】
組み合わせ生成装置が、
入力ビット列から、反転を行うビットの位置である反転ビット位置と、シフトにより最下位ビットにするビットの位置であるシフトビット位置とを、所定の基準により求め、シフトビット位置のビットを最下位ビットにシフトするのに要するシフト幅を求め、
前記入力ビット列の、前記反転ビット位置のビットの値と、それより１ビット下位に位置するビットの値とを反転し、
前記ビット反転手段が反転を行ったビット列の、前記反転ビット位置から２ビット下位のビット以下に位置する全てのビットを、前記シフト幅だけシフトし、
解選択装置が、
前記ビットシフト手段から出力される各組み合わせのビット列に対して、コスト計算を行うためのパラメータを用いてコストを計算し、
計算した前記コストを基にして、前記ビット列からビット列を選択する、
組み合わせ生成装置と解選択装置とを含む組み合わせ最適化問題求解システムによる、組み合わせ最適化問題求解方法。
【請求項１４】
入力ビット列から、反転を行うビットの位置である反転ビット位置と、シフトにより最下位ビットにするビットの位置であるシフトビット位置とを、所定の基準により求め、シフトビット位置のビットを最下位ビットにシフトするのに要するシフト幅を求めるビット位置取得処理と、
前記入力ビット列の、前記ビット位置取得処理により求めた反転ビット位置のビットの値と、それより１ビット下位に位置するビットの値とを反転するビット反転処理と、
前記ビット反転処理により反転を行ったビット列の、前記反転ビット位置から２ビット下位のビット以下に位置する全てのビットを、前記ビット位置取取得処理により求めた前記シフト幅だけシフトするビットシフト処理と、
をコンピュータに実行させるプログラム。
【請求項１５】
前記ビットシフト処理の結果である各組み合わせのビット列に対して、コスト計算を行うためのパラメータを用いてコストを計算するコスト計算処理と、
前記コスト計算処理により計算した前記コストを基にして、前記ビット列からビット列を選択する解選択処理と、
をコンピュータに実行させる、請求項１４に記載のプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ある要素群から、特定の個数の要素を選択するときの組み合わせを生成する組み合わせ生成装置、組み合わせ最適化問題求解システム、組み合わせ生成方法、組み合わせ最適化問題求解方法及びプログラムに関する。
【背景技術】
【０００２】
ある仕事や業務、または処理において、人や計算機、通信帯域といった資源を、定められた条件を満たしつつ割り当てるという資源割り当て問題は、世の中で広く応用されている問題である。
資源割り当て問題の例として、鉄道の乗務員スケジューリング、航空会社におけるエアラインクルースケジューリング、トラックの配送計画などが挙げられる。また、コンテンツ配信ネットワーク上のレプリカデータの配置サーバ決定、ＷＤＭネットワークにおけるマルチキャスト波長割り当て、携帯基地局配置、ルータのルーティングテーブル最小化といった、コンピュータシステム、及び通信ネットワーク（以下、ネットワークと呼称する）の分野でも、資源割り当て問題は適用されている。
ところで、資源割り当て問題は、組み合わせ最適化問題に帰着することができる。組み合わせ最適化問題は、Ｎ個の異なる要素の集まりから構成される要素群から、特定の個数（ｋ個）の要素を選択する場合、コストが最小になるような選び方を求める問題である。
組み合わせ最適化問題は、Ｎやｋの値が増加すると、考えられる組み合わせ（Ｎ個の要素からｋ個の要素を選択するパターン）の総数が爆発的に増加するため、最適解を現実的な時間で求めることが難しい。そのため、一般的にはグリーディ法のような近似解法で近似解を求めることで、現実的な時間で組み合わせ最適化問題を解くことが多い。
しかし、グリーディ法のような、その時点で最もコストの低い要素を選択していく手法では、局所解に陥り、最適解とのコストの差が大きくなる可能性がある、といった問題が存在する。
一方で、組み合わせ最適化問題を解く上で、全ての組み合わせを列挙し、その中で最もコストの低い組み合わせを選択するという列挙法を用いる方法も存在する。全ての組み合わせを調べることにより、常に最適解が得られる。
列挙法では、Ｎやｋの値が増加すると、組み合わせの総数が爆発的に増加するため、現実的な時間で解を求めることが難しいとされてきた。しかし、コンピュータの性能が向上し、調べる組み合わせの範囲に制約を加えることで調べる組み合わせの総数を削減することによって、現実的な時間で最適解を求められる可能性がある。
一般的に、列挙法で組み合わせ最適化問題を解く場合、まず、（１）解の候補（＝組み合わせ）を生成し、次に、（２）生成した解の候補に対して、コストの計算を行い、（３）最もコストの低い候補を最終的な解として選択する。
（１）〜（３）の処理において、（１）の解の生成処理を効率的に行うアルゴリズムが、非特許文献１に記載されている。
非特許文献１のアルゴリズムでは、Ｎ個の要素をＮビット幅の変数として表現し、その中でｋ個のビットの値が１となるビット列を生成することで、Ｎ個の要素からｋ個の要素を選択する組み合わせを生成する。
例えば、８個の異なる要素の集まりから３個の異なる要素を選ぶ場合、８ビットの変数を用い、各ビットを８個の要素に対応させ、００１０００１１のように、８ビット中、３個のビットの値が１であるビット列を生成する。
非特許文献１のアルゴリズムは、値が１であるビットの個数を維持しつつ、ビット列を数値として扱った場合に、現在のビット列より値が大きいビット列の中で最も小さな値を持つビット列を生成する。
下記のコードは、非特許文献１に示されている組み合わせ生成アルゴリズムを、ＰＤＰ−６／１０のアセンブリ言語で記述したプログラムコードである。下記のプログラムコードの左端の番号は行番号であり、Ａ、Ｂ、Ｃ、Ｄはレジスタである。
１：ＭＯＶＥ  Ｂ，Ａ
２：ＭＯＶＮ  Ｃ，Ｂ
３：ＡＮＤ  Ｃ，Ｂ
４：ＡＤＤ  Ａ，Ｃ
５：ＭＯＶＥ  Ｄ，Ａ
６：ＸＯＲ  Ｄ，Ｂ
７：ＬＳＨ  Ｄ，−２
８：ＩＤＩＶＭ  Ｄ，Ｃ
９：ＩＯＲ  Ａ，Ｃ
入力としてレジスタＡに８ビットの値０００００１１１を格納し、上記プログラムコードを実行すると、９行目のコードを実行した時点で、レジスタＡには００００１０１１が格納される。この値は、値が１であるビットの数が３個で、二進数とみなした場合に０００００１１１より値が大きいビット列の中で、最も小さいビット列である。この値を次の入力とすることで、値が１であるビットの個数を維持したまま、ビット列を昇順に生成することができる。
このようなビット列は、Ｎ個の異なる要素からｋ個の要素を選ぶ組み合わせを生成する場合、ＮＣｋ個存在する。例えば、Ｎ＝８、ｋ＝３の場合、８Ｃ３＝５６個の組み合わせが存在する。
非特許文献１のアルゴリズムは、上記のような組み合わせを効率よく生成できるが、組み合わせの総数はＮとｋの値が増加するに従って爆発的に増大する。そのため、ＣＰＵ（Ｃｅｎｔｒａｌ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ）を用いて組み合わせを生成しようとすると、現実的な時間で組み合わせを生成することが難しくなる。
さらに、非特許文献１のアルゴリズムを、ＣＰＵ上でソフトウェアを用いて実現する場合、扱う組み合わせの桁数（＝Ｎ）がＣＰＵの１回の演算で扱えるビット幅を超えると、演算で扱うデータをＣＰＵで扱えるビット幅に分割する必要があるので、組み合わせを生成する時間が増大してしまうという課題もある。
例えば、ＣＰＵが扱える最大演算ビット幅が６４ビットであるとすると、２５６個の要素からなる要素群（Ｎ＝２５６、２５６ビット幅のデータ）を対象として組み合わせの生成を行う場合、６４ビット×４個のように分割する必要がある。この結果、演算を実行する回数も４倍になる。
図２４に、非特許文献１のアルゴリズムに基づくソフトウェアを、ＣＰＵ（Ｉｎｔｅｌ  Ｘｅｏｎ  ３．６ＧＨｚ）にて実行することにより、Ｎ個の要素から４個の要素を選択する組み合わせを生成した場合の実行時間を測定した結果の一例を示す。曲線２４０１は、非特許文献１のアルゴリズムに基づくソフトウェアを前記ＣＰＵで実行した場合のＮと実行時間の関係を表す。
図２４を参照すると、１０２４個の要素から４個の要素を選択する場合の全ての解の候補の生成に１．５日を要していることが分かる。これは、非特許文献１のアルゴリズムで扱うデータが１０２４ビット幅になり、ＣＰＵで１回の演算で扱えるデータのビット幅をはるかに超えていることが原因である。
一方、組み合わせの生成処理をハードウェア化し、ＣＰＵよりも高速に組み合わせを生成する試みも行われている。
非特許文献２には、非特許文献１のアルゴリズムをハードウェア化することによって、ＣＰＵを用いて組み合わせを生成する場合よりも数十倍の速度で処理可能であることが示されている。しかし、非特許文献２で示される性能評価では、扱うデータのビット幅が最大で３２ビットとなっており、よりビット幅を増やした場合の性能評価が行われていない。
そこで、非特許文献１のアルゴリズムを専用ハードウェア化し、扱うデータのビット幅と等しい演算が可能な構成にし、ＦＰＧＡ（Ｆｉｅｌｄ  Ｐｒｏｇｒａｍｍａｂｌｅ  Ｇａｔｅ  Ａｒｒａｙ）を対象デバイスとして性能を測定した。図２４の曲線２４０２は、非特許文献１のアルゴリズムをハードウェア化し、Ｎ個の要素から４個の要素を選択する組み合わせを生成した場合の実行時間の測定結果を表す。１０２４個の要素から４個の要素を選択する場合の組み合わせの生成に４５分程度要し、ＣＰＵを用いた場合に比べて約５０倍の性能向上が確認された（図２４）。
しかし、非特許文献１のアルゴリズムを専用ハードウェア化した場合、そのハードウェアが達成可能な動作周波数に課題が存在する。
表１は、非特許文献１のアルゴリズムをハードウェア化した際のＮと動作周波数の関係を示す。つまり、上記専用ハードウェアが扱える演算ビット幅を変更することで、要素群を構成する要素数の総数Ｎを変化させた場合の最大動作周波数を測定したものである。
表１を参照すると、非特許文献１のアルゴリズムを専用ハードウェア化した場合、Ｎの値が倍になると動作周波数が約半分に落ちることが分かる。これより、Ｎの値が増加するに従って、結局は現実的な時間で組み合わせが生成できなくなってしまうことは明らかである。
【表１】
2010107102.tif 000003
動作周波数が大きく低下する原因は、非特許文献１のアルゴリズムに含まれる、加算処理を行う加算器である。
一般に、加算器は加算する２つの値の各桁と、下位の桁からの桁上げの３つの値を入力として演算を行う（ただし、最下位桁のみ、下位の桁からの桁上げは存在しない）。そのため、下位からの桁上げの値が確定しないと次の桁の計算ができないので、桁数が多くなるに従って加算処理にかかる遅延が大きくなる。
非特許文献２の手法を用いた場合、非特許文献１のアルゴリズムの前記プログラムコードにおける４行目の加算が、それぞれＮビットの値同士の演算になる。このため、非特許文献２の手法は、Ｎが大きくなると演算のための遅延が大きくなり、性能が劣化してしまうという問題を抱えている。
そこで、自身の桁より下位の桁の入力をもとに各桁の計算結果を先読みし、加算処理を短時間で行う桁上げ先読み加算器（キャリールックアヘッドアダー）が用いられる例が多い。
しかし、桁上げ先読み加算器は、桁数が増加するに従って、必要とする回路素子が多くなるため、面積のコストが大きく、その結果、回路の遅延も大きくなってしまう。
一方、非特許文献３には、ビット探索とシフト処理によってビット列の組み合わせの生成を行うカウンタのアルゴリズムが記載されている。非特許文献３に記載のアルゴリズムは、非特許文献１と同等の効果を持つ。
以下に記載のビット列の集合は、長さが６ビットで、値が１であるビットが３個存在するようなビット列を、２進数とみなした場合に値の小さいものから並べた例である。
０００１１１
００１０１１
００１１０１
００１１１０
０１００１１
０１０１０１
０１０１１０
０１１００１
・・・
１１１０００
非特許文献３に記載のカウンタは、このビット列の変化に着目し、次の手順を基本として、組み合わせを生成する。
手順（１）．ビット列中、最右に存在する０１の並びを探索し、１０に変更する。
手順（２）．手順（１）で発見した０１の位置より下位に、値が１のビットが１つ以上連続した並びが存在するかどうかを判定し、存在する場合は、その並びを右端にシフトする。
非特許文献３に記載のカウンタは、手順（１）の０１の並びの探索を以下のようにして行う。ビット列のビット幅をＮとすると、前記カウンタは、Ｎ−１個のプロセッサを用いて、０１の並びを並列に検出する。前記カウンタは、続いて、ビット列を半分に分けたときに下位ビット側に０１の並びが存在すれば、下位側を出力し、存在しなければ、上位側を出力する。非特許文献３に記載のカウンタは、以上の処理を再帰的に行うことで、０１の並びの探索を実現している。
また、非特許文献３には、手順（２）を処理する方法として、素朴な方法、右シフト法、左シフト法、ｋプロセッサ法の４種類の方法が記載されている。非特許文献３には、さらに、これらの４種類の方法をＦＰＧＡ上に実装したことが記載されている。
素朴な方法は、０１の位置より下位のビットを別の記憶領域に保存し、入力ビット幅Ｎに等しい段数のシフタを用いてシフト処理を行う。各段のシフタを通過する間に、いずれかのシフタから、第０ビット（最下位ビット）の値が１になったビット列が出力される。このビット列が出力となる。
素朴な方法は、入力ビット幅Ｎに等しい段数のシフタが必要なので、Ｎが大きくなると、回路規模や回路の遅延が大きくなり、組み合わせを生成するのに要する時間が大きくなるという問題を抱えている。
右シフト法、及び左シフト法は、１個のシフタを使用して、必要な回数だけ１ステップに１ビットずつシフトする手法である。右シフト法及び左シフト法は、用いるシフタが１個であるため、素朴な方法に比べて回路規模は大きくない。しかし、右シフト法及び左シフト法は、１ステップに１ビットずつシフトするので、入力ビット幅Ｎが増加するとシフト回数が増加し、組み合わせを生成するのに要する時間が大きくなるという問題を抱えている。
さらに、素朴な方法、右シフト法及び左シフト法は、事前に何ビットシフトするのかを求めないため、シフト処理ごとに、シフトした結果を出力するかどうかを決めるための比較の処理を行う必要がある。シフトする回数が多くなるほど比較回数も増加するため、入力ビット幅Ｎが増加するに従って、組み合わせを生成するのに要する時間はさらに大きくなる。
一方、ｋプロセッサ法は、値が１であるビットの個数をｋ個とすると、ｋ個の１に対して異なるプロセッサを割り当て、各プロセッサが独立に、自身が割り当てられたビットを、次に生成するビット列の適切なビット位置に移動する処理を行う。
そのため、ｋの値が変わるとハードウェアの構成を変更する必要がある。また、ビットを移動する処理において、Ｎビット同士の値の論理積やＮビットの値のリダクション論理和を行うため、入力ビット幅Ｎが増加すると、回路の遅延が大きくなることが予測される。
一方、非特許文献４には、非特許文献１や非特許文献３と同様の組み合わせを、再帰関数を用いて生成するアルゴリズムである、Ｂａｎｋｅｒ’ｓ  Ｓｅｑｕｅｎｃｅ法が記載されている。Ｂａｎｋｅｒ’ｓ  Ｓｅｑｕｅｎｃｅ法は、２つの処理フェーズから構成されており、最初のフェーズで、どのビットの値を１にするかを指定するための配列を生成する。例えば、ビット列の２番目、３番目、５番目のビットの値を１にする場合、｛５，３，２｝という配列を生成する。Ｂａｎｋｅｒ’ｓ  Ｓｅｑｕｅｎｃｅ法は、次のフェーズで、最初のフェーズで生成した配列で指定されるビットを１にしたビット列を生成する。例えば、８ビット幅のビット列であれば、００１１０１００というビット列を生成する。
列挙法は、非特許文献１、非特許文献２、非特許文献３及び非特許文献４で示されるような組み合わせ生成アルゴリズム及び手法を用いて、組み合わせを生成した後に、各組み合わせについて、コストの計算を行い、最もコストの低い組み合わせを解とする方法である。
また、特許文献１には、ｎ個の要素からｒ個の要素を選ぶ組み合わせの計ｎＣｒ個のパターンの全数を生成する際に、ｎ台の演算装置を使用して独立かつ並列的に動作させて組み合わせを生成する技術が開示されている。
また、特許文献２には、加減算回路により減算された出力値における最上位の‘１’のビットの位置が第何桁目にあるかを検出し、その検出値をシフト量としてシフトする技術が開示されている。
【先行技術文献】
【特許文献】
【０００３】
【特許文献１】特開平０９−１４６９２２号公報
【特許文献２】特開平０５−３１３８５７号公報
【非特許文献】
【０００４】
【非特許文献１】エム・ビーラー（Ｍ．Ｂｅｅｌｅｒ）、ダブリュ・ゴスパー（Ｗ．Ｇｏｓｐｅｒ）、アール・シュレッペル（Ｒ．Ｓｃｈｒｏｅｐｐｅｌ）著、“ＨＡＣＫＭＥＭ”、マサチューセッツ  インスティチュート  オブ  テクノロジー  エー・アイ・ラボラトリー（Ｍａｓｓａｃｈｕｓｅｔｔｓ  Ｉｎｓｔｉｔｕｔｅ  ｏｆ  Ｔｅｃｈｎｏｌｏｇｙ  Ａ．Ｉ．Ｌａｂｏｒａｔｏｒｙ）、エー・アイ・エム―２３９（ＡＩＭ―２３９）、１９７２年、第８１頁、アイテム  １７５（ＩＴＥＭ  １７５）
【非特許文献２】石川  浩行、清水  翔、荒川  豊、山中  直明、斯波  康祐、“並列リコンフィギャラブルプロセッサＤＡＰＤＮＡ−２を用いた集合被覆問題の高速解法”、電子情報通信学会技術研究報告  ＲＥＣＯＮＦ２００７−６２、２００８年、第６７−７２頁
【非特許文献３】山岸  洋平、“ＦＰＧＡを用いたＮＰ完全問題の全解探索法に関する研究”、北陸先端科学技術大学院大学、２００３年
【非特許文献４】ジェイ・ラフリー（Ｊ．Ｌｏｕｇｈｒｙ）、ジェイ・アイ・ヴァン・ヘメルト（Ｊ．Ｉ．ｖａｎ  Ｈｅｍｅｒｔ）、エル・ショーフス（Ｌ．Ｓｃｈｏｏｆｓ）、“Ｅｆｆｉｃｉｅｎｔｌｙ  Ｅｎｕｍｅｒａｔｉｎｇ  ｔｈｅ  Ｓｕｂｓｅｔｓ  ｏｆ  ａ  Ｓｅｔ”、ｈｔｔｐ：／／ｗｗｗ．ａｐｐｌｉｅｄ−ｍａｔｈ．ｏｒｇ／ｓｕｂｓｅｔ．，ｐｄｆ、２０００年、第７−９頁
【発明の開示】
【発明が解決しようとする課題】
【０００５】
しかしながら、上述した列挙法で組み合わせ最適化問題を解く手法には、以下のような組み合わせの生成に関する課題が存在する。
第１の問題点は、生成する組み合わせの桁数の増加に応じて、加算処理による遅延が大きくなる点である。その理由は、非特許文献１における組み合わせ生成手法は、組み合わせの生成に加算処理を行っているからである。非特許文献２のように非特許文献１のアルゴリズムをハードウェア化した場合、生成する組み合わせの桁数が増加すると加算処理を行う加算器の桁上がりの遅延が大きくなる。
第２の問題点は、シフト処理及び比較処理による遅延やステップ数が、桁数に比例して増加する点である。その理由は、非特許文献３における組み合わせ生成手法は、生成する組み合わせの桁数が増加した際に、１ステップに１ビットシフトするというように、処理を１ビットずつ行う手法であるからである。また、１回のシフトごとに、比較処理を行う必要があるからである。
第３の問題点は、ｋの値、すなわち、選び出す要素数を変更すると、ハードウェアの構成を変更しなければならないという点である。その理由は、非特許文献３における組み合わせ生成手法は、１であるビットに対してそれぞれ異なるプロセッサを割り当てるなど、処理をビット毎に行う手法であるからである。
また、特許文献４に記載のＢａｎｋｅｒ’ｓ  Ｓｅｑｕｅｎｃｅ法には、アルゴリズムの効率的なハードウェア化による高速化が難しいという問題がある。その理由は、Ｂａｎｋｅｒ’ｓ  Ｓｅｑｕｅｎｃｅ法は、最初のフェーズで再帰関数を用いているからである。再帰する回数が生成する組み合わせのパターンによって異なるため、Ｂａｎｋｅｒ’ｓ  Ｓｅｑｕｅｎｃｅ法のアルゴリズムの効率的なハードウェア化は難しい。
本発明の目的は、組み合わせの生成に伴う加算処理、シフト処理及び比較処理の演算時間の、桁数の増加に伴う増大が少ない組み合わせ生成装置を提供することにある。
【課題を解決するための手段】
【０００６】
本発明の組み合わせ生成装置は、入力ビット列から、反転を行うビットの位置である反転ビット位置と、シフトにより最下位ビットにするビットの位置であるシフトビット位置とを、所定の基準により求め、シフトビット位置のビットを最下位ビットにシフトするのに要するシフト幅を求めるビット位置取得手段と、前記入力ビット列の、前記ビット位置取得手段が求めた反転ビット位置のビットの値と、それより１ビット下位に位置するビットの値とを反転するビット反転手段と、前記ビット反転手段が反転を行ったビット列の、前記反転ビット位置から２ビット下位のビット以下に位置する全てのビットを、前記ビット位置取得手段が求めた前記シフト幅だけシフトするビットシフト手段と、を含む。
本発明の組み合わせ最適化問題求解システムは、入力ビット列から、反転を行うビットの位置である反転ビット位置と、シフトにより最下位ビットにするビットの位置であるシフトビット位置とを、所定の基準により求め、シフトビット位置のビットを最下位ビットにシフトするのに要するシフト幅を求めるビット位置取得手段と、前記入力ビット列の、前記ビット位置取得手段が求めた反転ビット位置のビットの値と、それより１ビット下位に位置するビットの値とを反転するビット反転手段と、前記ビット反転手段が反転を行ったビット列の、前記反転ビット位置から２ビット下位のビット以下に位置する全てのビットを、前記ビット位置取得手段が求めた前記シフト幅だけシフトするビットシフト手段と、を含む組み合わせ生成装置と、前記ビットシフト手段から出力される各組み合わせのビット列に対して、コスト計算を行うためのパラメータを用いてコストを計算するコスト計算手段と、前記コスト計算手段が計算した前記コストを基にして、前記ビット列からビット列を選択する解選択手段と、を含む、前記組み合わせ生成装置によって生成されたビット列から、所定の基準によりビット列を選択する解選択装置と、を含む。
本発明の組み合わせ生成装置による組み合わせ生成方法は、組み合わせ生成装置が、入力ビット列から、反転を行うビットの位置である反転ビット位置と、シフトにより最下位ビットにするビットの位置であるシフトビット位置とを、所定の基準により求め、シフトビット位置のビットを最下位ビットにシフトするのに要するシフト幅を求め、前記入力ビット列の、前記反転ビット位置のビットの値と、それより１ビット下位に位置するビットの値とを反転し、前記反転を行ったビット列の、前記反転ビット位置から２ビット下位のビット以下に位置する全てのビットを、前記シフト幅だけシフトする。
本発明の組み合わせ生成装置と解選択装置とを含む組み合わせ最適化問題求解システムによる、組み合わせ最適化問題求解方法は、組み合わせ生成装置が、入力ビット列から、反転を行うビットの位置である反転ビット位置と、シフトにより最下位ビットにするビットの位置であるシフトビット位置とを、所定の基準により求め、シフトビット位置のビットを最下位ビットにシフトするのに要するシフト幅を求め、前記入力ビット列の、前記反転ビット位置のビットの値と、それより１ビット下位に位置するビットの値とを反転し、前記ビット反転手段が反転を行ったビット列の、前記反転ビット位置から２ビット下位のビット以下に位置する全てのビットを、前記シフト幅だけシフトし、解選択装置が、前記ビットシフト手段から出力される各組み合わせのビット列に対して、コスト計算を行うためのパラメータを用いてコストを計算し、計算した前記コストを基にして、前記ビット列からビット列を選択する。
本発明のプログラムは、入力ビット列から、反転を行うビットの位置である反転ビット位置と、シフトにより最下位ビットにするビットの位置であるシフトビット位置とを、所定の基準により求め、シフトビット位置のビットを最下位ビットにシフトするのに要するシフト幅を求めるビット位置取得処理と、前記入力ビット列の、前記ビット位置取得処理により求めた反転ビット位置のビットの値と、それより１ビット下位に位置するビットの値とを反転するビット反転処理と、前記ビット反転処理により反転を行ったビット列の、前記反転ビット位置から２ビット下位のビット以下に位置する全てのビットを、前記ビット位置取取得処理により求めた前記シフト幅だけシフトするビットシフト処理と、をコンピュータに実行させる。
【発明の効果】
【０００７】
本発明により、加算処理を行うことなく、シフト処理を効率的に行うことで、桁数の増加に伴う演算時間の増大が少ない、組み合わせ生成が可能となる。
【図面の簡単な説明】
【０００８】
【図１】本発明の第１の実施の形態に係る組み合わせ生成装置１の構成例を示すブロック図である。
【図２】本発明の第１の実施の形態に係る組み合わせ生成装置１の動作の例を示すフローチャートである。
【図３】入力ビット列を００１０１１１０としたときの、第１の実施の形態に係る組み合わせ生成装置１の処理の過程を表す図である。
【図４】本発明の第２の実施の形態に係る組み合わせ最適化問題求解システム１００の構成例を示すブロック図である。
【図５】組み合わせ最適化問題求解システム１００の動作の例を示すフローチャートである。
【図６】本発明の第３の実施の形態に係る組み合わせ生成装置２の構成例を示すブロック図である。
【図７】本発明の第３の実施の形態に係る組み合わせ生成装置２の動作の例を示すフローチャートである。
【図８】本発明の第４の実施の形態に係る組み合わせ生成装置３の構成例を示すブロック図である。
【図９】本発明の第４の実施の形態に係る組み合わせ生成装置３の動作の例を示すフローチャートである。
【図１０】本発明の第５の実施の形態に係る組み合わせ生成装置４の構成例を示すブロック図である。
【図１１】ビット位置取得ブロック２２のブロック図である。
【図１２】本発明の第５の実施の形態に係る組み合わせ生成装置４の、ビット位置取得ブロック２２の動作の例を示すフローチャートである。
【図１３】本発明の第６の実施の形態に係る組み合わせ生成装置５の構成例を示すブロック図である。
【図１４】ビット位置取得ブロック２４のブロック図である。
【図１５】ビット値”１”の最下位ビット位置取得回路１４３のブロック図である。
【図１６】入力ビット列が８ビットの場合に、入力ビット列について、ビットｉのみのビット値を１にしたビット列を出力するように、記憶部１５１４を設定した例である。
【図１７】入力ビット列が８ビットの場合に、入力ビット列について、ビットｉより下位に位置する全てのビットのビット値を“１”にし、ビットｉ以上に位置するビットのビット値を全て“０”にしたビット列を出力するように、記憶部１５１４を設定した例である。
【図１８】入力ビット列が８ビットの場合に、入力ビット列について、値が“０”であるビットのうち、最も下位に位置するビットのビット値のみを“１”にしたビット列を出力するように、記憶部１５１４を設定した例である。
【図１９】本発明の第７の実施の形態に係る組み合わせ生成装置６の構成例を示すブロック図である。
【図２０】ビット位置取得ブロック２６の内部構造を示したものである。
【図２１】５１２ビット幅の入力に対して、ビット位置取得ブロック２６の例を示したものである。
【図２２】本発明の第８の実施の形態に係る組み合わせ生成装置７の構成例を示すブロック図である。
【図２３】Ｎを１０２４まで増加させ、Ｎ個の要素から４個の要素を選択する場合の解の候補を生成する場合の、従来手法との実行時間の比較図である。
【図２４】Ｎを１０２４まで増加させ、Ｎ個の要素から４個の要素を選択する場合の解の候補を生成する場合の、従来手法の実行時間を示したものである。
【符号の説明】
【０００９】
１  組み合わせ生成装置
８  コスト計算モジュール
９  解選択モジュール
１２  入力チェックブロック
１３  アービター
１４  ビット位置取得ブロック
１５  ビット分割ブロック
１６  ビット反転ブロック
１８  ビットシフトブロック
１９  ビット結合ブロック
２０  終了判定ブロック
２８  パイプラインレジスタ
１００  組み合わせ最適化問題求解システム
１４２  ビット値”１”の最下位ビット位置取得ブロック
１４３  ビット値”１”の最下位ビット位置取得回路
１４６  論理和演算ブロック
１４８  ビット値”０”の最下位ビット位置取得ブロック
１４９  ビット値”０”の最下位ビット位置取得回路
２００  解選択装置
１４２０  第一階層
１４２１  ビット探索ブロック
１４２２  第二階層
１４２４  上位位層
１４２６  最上位階層
１５１２  入力部
１５１４  記憶領域
１５１６  マルチプレクサ群
２３０１  非特許文献１のアルゴリズムに基づくソフトウェアを実行した場合の実行時間の測定結果
２３０２  非特許文献１のアルゴリズムをハードウェア化した場合の実行時間の測定結果
２３０３  本発明の第１〜第７の実施形態における組み合わせ生成方法を組み合わせてハードウェア化した組み合わせ生成装置での実行時間の測定結果
２４０１  非特許文献１のアルゴリズムに基づくソフトウェアを実行した場合の実行時間の測定結果
２４０２  非特許文献１のアルゴリズムをハードウェア化した場合の実行時間の測定結果
【発明を実施するための最良の形態】
【００１０】
次に、発明を実施するための最良の形態について図面を参照して詳細に説明する。なお、本発明の実施の形態においては、特に断りのない限り、ｉ及びｊは０オリジンで表現し、要素群を構成する要素数の総数をＮ、その中から選び出す要素数をｋとする。
（第１の実施の形態）
＜構成＞
図１は、本発明の第１の実施の形態に係る組み合わせ生成装置１の構成図である。組み合わせ生成装置１は、ビット位置取得ブロック１４と、ビット反転ブロック１６と、ビットシフトブロック１８と、を備える。
本発明の以下の実施形態では、Ｎ個の要素群からｋ個の要素を選択する。この場合、選択された要素のパターン（組み合わせ）は、各ビットをＮ個の要素のいずれかに１対１で対応させたＮビットのビット列で表される。選択されている要素に対応するビットに設定する値及び、選択されていない要素に対応するビットに設定する値は、それぞれあらかじめ決めておく。ビット列の各ビットの値は、該ビットに対応する要素が選択されているか否かに基づいた値に設定する。
以下、選択された要素に対応するビットの値（ビットの符号）が“１”であり、選択されていない要素に対応するビットの値（ビットの符号）が“０”であるとして説明する。また、ビット列を二進数とみなした場合にそのビット列で表される数値を、ビット列の値と表記する。また、あるビット列（ビット列Ａとする）が他のビット列（ビット列Ｂとする）より大きいとは、ビット列を二進数とみなした場合に、ビット列Ａで表される数値が、ビット列Ｂで表される数値より大きいことを意味する。
しかし、選択された要素に対応するビットの値は“０”に、選択されていない要素に対応するビットの値は“１”にしてもよい。その場合、以下の説明において、“０”と“１”を置き換えればよい。ただし、この場合、二進数の数値とみなしたビット列の値の大小関係は逆になる。
また、ビット列のビットの位置を特定するための番号は、右端のビットを０とした昇順とする。番号ｎのビットは、第ｎビットまたはビットｎまたはビット（ｎ）と表記する。例えば、Ｎ＝８、ｋ＝３で、第０ビット〜第２ビットが選択された要素に対応する場合、ビット列は“０００００１１１”となる。ビット列を数値とみなす場合、ビット列の右端がＬＳＢ（Ｌｅａｓｔ  Ｓｉｇｎｉｆｉｃａｎｔ  Ｂｉｔ、最下位ビット）で、左端がＭＳＢ（Ｍｏｓｔ  Ｓｉｇｎｉｆｉｃａｎｔ  Ｂｉｔ、最上位ビット）であるとする。
組み合わせ生成装置１は、入力１０からビット列（入力ビット列と呼称する）が入力されると、選択された要素に対応するビット（“１”）の数ｋが入力ビット列と同じであり、値が入力ビット列より大きなビット列の中で、最も値が小さいビット列（＞入力ビット列）を生成し、出力６０から出力する。ビット列の“値”とは、上述のように、ビット列を二進数とみなした場合に該ビット列で表される数値のことである。
例えば、組み合わせ生成装置１は、入力１０から８ビットのビット列“０００００１１１”（十進数で７、Ｎ＝８、ｋ＝３）を入力された場合、値が“１”のビットの総数が３で、入力ビット列より値の大きいビット列の中で、最も値が小さいビット列である、“００００１０１１”（十進数で１１）を生成し、出力６０から出力する。
入力１０からは、値が“１”のビットがｋ個存在するＮビット幅のビット列が入力される（ｋ＜Ｎ）。
なお、Ｎビット幅のビット列の入力に関して、Ｎビット幅の入力以外にも、例えば、１ビット幅の入力を用いて、Ｎサイクルの時間で入力する方法などが考えられる。
ビット位置取得ブロック１４は、入力１０及びビット反転ブロック１６に接続される。ビット位置取得ブロック１４は、入力１０から入力される入力ビット列に対して、ビット探索を行い、値が“１”のビットのうち、最も下位に位置するビット（本ビットをビットｉと呼ぶ）を求める。位置取得ブロック１４は、次に、入力ビット列の、ビットｉよりも上位に位置するビットで、値が“０”のビットのうち、最も下位に位置するビット（本ビットをビットｊと呼ぶ）を求める。位置取得ブロック１４は、ビットｉを示す情報と、ビットｊを示す情報と、入力ビット列と、をビット反転ブロック１６に出力する。
ビット反転ブロック１６は、ビット位置取得ブロック１４と、ビットシフトブロック１８との間に接続される。ビット反転ブロック１６は、ビット位置取得ブロック１４から入力される入力ビット列の、ビット（ｊ−１）、及びビットｊの値を反転する。ビット反転ブロック１６は、ビットｉを示す情報と、ビットｊを示す情報と、反転したビット列（反転済ビット列と呼称する）と、をビットシフトブロック１８に出力する。
ビットシフトブロック１８は、ビット反転ブロック１６と、出力６０と、に接続される。ビットシフトブロック１８は、ビット反転ブロック１６から入力される反転済ビット列の、ビット（ｊ−１）より下位のビット、つまり、（ｊ−２）ビット以下をｉビット右シフトする。ビットシフトブロック１８は、右シフトを行ったビット列（シフト済ビット列と呼称する）を、出力６０に出力する。
＜動作＞
次に、図１及び図２を参照して、本実施形態に係る組み合わせ生成装置１の動作について詳細に説明する。図２は、本実施形態に係る組み合わせ生成装置１の動作の例を示すフローチャートである。
入力１０からは、値が“１”のビットがｋ個存在するＮビット幅のビット列が入力される（ｋ＜Ｎ）。組み合わせ生成装置１は、入力１０から入力された入力ビット列とｋ（値が“１“のビット数）が同じで、入力ビット列を数値として扱った場合に入力ビット列より大きいビット列の中で、最も小さいビット列を生成する。
さらに、組み合わせ生成装置１が出力６０から出力したビット列を、入力１０から再度、組み合わせ生成装置１に入力することで、ビット列を順次昇順に、生成することも可能である。
ビット位置取得ブロック１４は、入力１０から入力される入力ビット列に対してビット探索を行い、値が“１”のビットのうち、最も下位のビット（ビットｉ）の位置を求める（ステップＳ１０１）。ここで、ビットｉの位置は、シフトビット位置とも言い、シフトにより最下位ビットに位置する値が“１”のビット、の位置である。次に、ビット位置取得ブロック１４は、入力ビット列の、ビットｉよりも上位に位置し、値が“０”であるビットのうち、最も下位のビット（ビットｊ）の位置を求める（ステップＳ１０２）。ビットｊの位置は、反転ビット位置とも言い、後述する反転を行うビットの位置である。
ビット位置取得ブロック１４は、ビットｉを示す情報と、ビットｊを示す情報と、入力ビット列と、をビット反転ブロック１６に出力する。ビットｉを示す情報は、前述のビットｉの位置と、そのビット値と、ｉをデータとするシフト幅の情報とを含んでもよい。シフト幅は、ビットシフトブロック１８で実行されるシフト量である。ビットｊを示す情報は、ビットｊの位置とそのビット値とを含んでもよい。
ビット位置取得ブロック１４でのビット探索方法の例として、例えば、入力されたビット列を下位ビットから順番に探索し、最初に見つかった、値が“１”のビットをビットｉとし、その次に見つかった、値が“０”のビットをビットｊとするという方法などが考えられる。
ビット反転ブロック１６は、ビット位置取得ブロック１４から入力されるビット列の、ビット（ｊ−１）、及びビットｊの値を反転する（ステップＳ１０３）。ビット反転ブロック１６は、ビットｉを示す情報と、ビットｊを示す情報と、反転を行った反転済ビット列とをビットシフトブロック１８に出力する。
ビットシフトブロック１８は、ビット反転ブロック１６から入力される反転済ビット列の、ビット（ｊ−１）より下位のビット、つまり、（ｊ−２）ビット以下をｉビット右シフトする（ステップＳ１０４）。ビットシフトブロック１８は、右シフトを行ったシフト済ビット列を、出力６０に出力する。
上述した、組み合わせ生成装置１を構成する各ブロックの具体的な動作例について、図３を参照して、以下に説明する。
図３は、図２のフローチャートにおいて、入力ビット列が“００１０１１１０”である場合の、各ステップでの処理を示したものである。なお、図３中の各ステップの番号は、図２の各ステップの番号と対応している。
ビット位置取得ブロック１４は、入力ビット列“００１０１１１０”の、値が“１”であるビットのうち、最も下位に位置するビットｉの位置を求める（ステップＳ１０１）。この例では、ビット１（右から２番目のビット）が、最も下位に位置する値が“１”のビットなので、ｉ＝１となる。
次に、ビット位置取得ブロック１４は、ビットｉより上位に位置するビットの中で最も下位に位置する、値が“０”であるビットの位置（ビットｊ）を求める（ステップＳ１０２）。この例では、ビット４（右から５番目のビット）が、ビットｉより上位で値が“０”のビットのうち最も下位のビットなので、ｊ＝４となる。
続いて、ビット反転ブロック１６が、ビットｊ（ビット４）と、ビット（ｊ−１）（ビット３）の値を反転する（ステップＳ１０３）。
ビットシフトブロック１８は、ビット（ｊ−２）（ビット２）以下のビットをｉビット（１ビット）右シフトする（ステップＳ１０４）。ステップＳ１０４の結果得られるビット列が出力となる。
なお、ｉ、及びｊの表現形式に制限はなく、図３のように数値で表す他に、ビットｉ、及びビットｊの値のみを“１”にしたビット列で表す方法も考えられる。ビット列で表現する場合、図３の例では、ｉ＝“００００００１０”、ｊ＝“０００１００００となる。
＜実施形態の効果＞
次に、本実施形態の効果について説明する。
本実施形態に係る組み合わせ生成装置１では、組み合わせの生成において、加算を行わない。このため、入力ビット列のビット幅が増加しても、組み合わせの生成の遅延の増加を抑制することができる。これは、非特許文献１の加算処理で得られていた効果を、ビット反転処理で達成しており、ビット反転処理は、常にビットｊとビット（ｊ−１）の２ビットの反転処理となる。
また、本実施形態に係る組み合わせ生成装置１では、組み合わせの生成において、シフト処理よりも先にシフト幅を求めているため、シフトするたびに比較を行う必要が無い。従って、本実施形態の組み合わせ生成装置１では、入力ビット列のビット幅が増加しても、組み合わせの生成におけるシフト処理に伴う比較の処理は増加しない。
また、本実施形態に係る組み合わせ生成装置１では、ビット反転処理について、ビット探索処理で得られたビットｊに関する情報を用いてビット反転を行っている。ビットｊに関する情報は、ビットシフト処理においても必要な情報である。本実施形態のような構成をとることで、非特許文献３に記載の方法では必要であった、ビット反転処理だけを目的としたビット探索処理を行う必要が無くなり、組み合わせの生成を効率よく行うことができる。
従って、本実施形態は、入力ビット列のビット幅が増加しても、組み合わせの生成の処理時間の増加を抑制することができると言う効果がある。
また、本実施形態に係る組み合わせ生成装置１は、Ｎ個の要素からｋ個の要素を選ぶ組み合わせを生成する際に、装置の構成がｋの値に依存しない。そのため、本実施形態の組み合わせ生成装置には、Ｎが固定であれば、Ｎ＞ｋの条件を満たす全てのｋに対して、同じ装置を提供することができると言う効果もある。
（第２の実施の形態）
＜組み合わせ最適化問題求解システムの構成＞
次に、本発明の第２の実施形態に係る組み合わせ最適化問題求解システムについて、図面を参照して詳細に説明する。
図４は、本実施形態に係る組み合わせ最適化問題求解システム１００の構成例を示したものである。
図４を参照すると、組み合わせ最適化問題求解システム１００は、組み合わせ生成装置１と、解選択装置２００と、を含み、解選択装置２００は、コスト計算モジュール８と解選択モジュール９を含む。ここで、モジュールとは、ソフトウェア、ハードウェアの少なくともいずれかによって実現される一機能単位である。
組み合わせ生成装置１は、本発明の第１の実施の形態に係る組み合わせ生成装置１と同じである。組み合わせ生成装置１は、入力１０と、コスト計算モジュール８と、接続される。組み合わせ生成装置１は生成した組み合わせを、コスト計算モジュール８に出力する。
コスト計算モジュール８は、入力７０と、組み合わせ生成装置１と、コスト計算モジュール９とに接続される。入力７０からは、コスト計算を行うために用いるパラメータが入力される。パラメータの例として、例えば、ネットワークの分野では、通信帯域や、通信遅延、経路の混雑具合などが挙げられる。
コスト計算モジュール８は、入力７０から入力されるパラメータを用いて、組み合わせ生成装置１が生成した組み合わせのコスト計算を行う。コスト計算モジュール８は、計算したコストを、組み合わせの情報とともに、解選択モジュール９に出力する。ここで、コスト計算とは、例えば、互いに通信しあってアプリケーションを協調実行するノードが複数台接続されるネットワークにおいて、ノード間の通信帯域や、通信の混雑具合、各ノードの性能、消費電力などのパラメータに重み付けなどを行い、各パラメータを合計するといった処理のことである。
解選択モジュール９は、コスト計算モジュール８と、出力９０とに接続される。解選択モジュール９は、コスト計算モジュール８から入力されたコストを比較し、最もコストの低い組み合わせを解として選択する。解選択モジュール９は、選択した解を出力９０に出力する。
＜組み合わせ最適化問題求解システムの動作＞
次に、図４及び図５のフローチャートを参照して、組み合わせ最適化問題求解システム１００の動作について詳細に説明する。図５は、組み合わせ最適化問題求解システム１００の動作の例を示すフローチャートである。
入力１０からは、値が“１”のビットをｋ個含むＮビット幅のビット列が入力される（ｋ＜Ｎ）。組み合わせ生成装置１は、ｋが入力ビット列と同じで、ビット列を数値みなした場合に入力ビット列より値が大きいビット列の中で、最も小さいビット列を生成する（ステップＳ１０）。組み合わせ生成装置１は、生成したビット列をコスト計算モジュール８に出力する。
コスト計算モジュール８は、入力７０から入力されるパラメータを用いて、組み合わせ生成装置１から入力されるビット列のコスト計算を行う（ステップＳ１１）。コスト計算モジュール８は、組み合わせを示す情報とともに、計算したコストを解選択モジュール９に出力する。
なお、組み合わせ生成装置１と、コスト計算モジュール８との間でビット列を受け渡すために、例えば、組み合わせ生成装置１から、どのタイミングで有効なビット列が流れているかを示す信号を、そのビット列と共に、コスト計算モジュール８に出力するなどの方法も考えられる。
また、組み合わせ生成装置１がコスト計算モジュール８に出力する組み合わせを示す情報は、ビット列中、値が“１”のビットの位置を判別できる情報であればよく、例えば、ビット列の代わりに、ビットの位置を示す整数の配列などでもよい。例えば、ビット列“０００１０００１”の代わりに、（０，４）のような整数の配列でも値が“１”のビットの位置を識別することができる。
さらに、組み合わせ最適化問題求解システム１００は、組み合わせ生成装置１の組み合わせの生成速度に合わせて、コスト計算モジュール８の内部で、コストを計算するユニットを１個以上備える。これは、組み合わせ生成装置１によって生成される組み合わせは互いに独立であり、コスト計算を並列に行うことが可能であるためである。
また、組み合わせを１つ生成する処理量は、非特許文献１のアルゴリズムにおいて、高々１０命令程度である。そのため、１つの組み合わせに対するコスト計算の処理量よりも、組み合わせを１つ生成する処理量の方が少ない場合も考えられる。この時、コスト計算モジュール８にコスト計算ユニットを複数備えることで、コスト計算モジュール８が組み合わせ最適化問題を解く処理のボトルネックとなる可能性を排除することができる。
コスト計算モジュール８の内部に、コスト計算ユニットが複数備えられる場合、組み合わせ生成装置１から出力される組み合わせが、どのコスト計算ユニットに入力されるかを指定する仕組みが必要である。
この仕組みには、例えば、組み合わせ生成装置１が組み合わせを出力する際に、出力先のコスト計算ユニットを指定する方法や、コスト計算モジュール８の内部で、入力されたビット列の特定のビットを参照し、それに応じて各コスト計算ユニットに割り振る方法などが考えられる。ここで、ユニットとは、特定の機能を処理する具体的な物を指し、例えば、ＣＰＵなどが該当する。
解選択モジュール９は、コスト計算モジュール８から入力されたコストを比較し、最もコストの低い解を選択し、出力９０に出力する（ステップＳ１２）。
解を出力するタイミングとして、コスト計算モジュール８から入力が行われるたびに、その時点でもっともコストの低い解を出力する方法や、全ての組み合わせについてコストを比較し、最適解が得られた時点で出力する方法などが考えられる。
また、組み合わせ最適化問題求解システム１００の外部に接続されたシステムが、どのタイミングで解が出力されているかを検知することを容易にするために、例えば、解選択モジュール９が解を出力するたびに、解と同時に、有効な解が出力されていることを示す信号を出力することなどが考えられる。
＜実施形態の効果＞
次に、本実施形態に係る組み合わせ最適化問題求解システム１００の効果について詳細に説明する。
本実施形態に係る組み合わせ最適化問題求解システム１００が含む組み合わせ生成装置１は、組み合わせの生成において、加算を行わない。このため、入力ビット列のビット幅が増加しても、組み合わせの生成の遅延の増加を抑制することができる。これは、非特許文献１の加算処理で得られていた効果を、ビット反転処理で達成しており、ビット反転処理は、常にビットｊとビット（ｊ−１）の２ビットの反転処理となるためである。
また、本実施形態に係る組み合わせ最適化問題求解システム１００が含む組み合わせ生成装置１は、組み合わせの生成において、シフト処理よりも先にシフト幅を求めているため、シフトするたびに比較を行う必要が無く、組み合わせの生成における処理量を削減することができる。
また、本実施形態に係る組み合わせ最適化問題求解システム１００が含む組み合わせ生成装置１は、ビット探索処理で得られたビットｊに関する情報を用いてビット反転を行っている。ビットｊに関する情報は、ビットシフト処理においても必要な情報である。そのため、本実施形態のような構成をとることで、非特許文献３で示されていたように、ビット反転処理のためだけにビット探索処理を行う必要が無くなり、組み合わせの生成を効率よく行うことができる。
また、本実施形態に係る組み合わせ最適化問題求解システム１００が含む組み合わせ生成装置１は、Ｎ個の要素からｋ個の要素を選ぶ組み合わせを生成する際に、装置の構成がｋの値に依存しない。そのため、Ｎが固定であれば、Ｎ＞ｋの条件を満たす全てのｋに対して、装置の構成が同じになる。
（第３の実施の形態）
＜構成＞
図６は、本発明の第３の実施の形態に係る組み合わせ生成装置２の構成を表す図である。図６を参照すると、組み合わせ生成装置２は、ビット分割ブロック１５と、ビット結合ブロック１９が、本発明の第１の実施の形態に係る組み合わせ生成装置１と異なり、その他の構成要素は、本発明の第１の実施の形態に係る組み合わせ生成装置１と同一である。本発明の第１の実施の形態に係る組み合わせ生成装置１と同一の構成要素については、図１と同一の符号を付し、詳細な説明を省略する。
入力１０からは、値が“１”のビットがｋ個存在するＮビット幅のビット列が入力される（ｋ＜Ｎ）。
ビット位置取得ブロック１４は、入力１０と、ビット分割ブロック１５と、接続される。ビット位置取得ブロック１４は、本発明の第１の実施の形態に係る組み合わせ生成装置１と同様にビットｉとビットｊを求め、ビットｉを示す情報と、ビットｊを示す情報と、入力ビット列と、をビット分割ブロック１５に出力する。
ビット分割ブロック１５は、ビット位置取得ブロック１４と、ビット反転ブロック１６と、ビットシフトブロック１８と接続される。ビット分割ブロック１５は、ビット位置取得ブロック１４から入力される入力ビット列を、ビット（ｊ−１）以上（Ｕｐｐｅｒ―ビット）と、ビット（ｊ−２）以下（Ｌｏｗｅｒ―ビット）に分割し、ビットｊを示す情報と、Ｕｐｐｅｒ―ビットと、をビット反転ブロック１６に、ビットｉを示す情報と、Ｌｏｗｅｒ―ビットと、をビットシフトブロック１８に出力する。
ビット反転ブロック１６は、ビット分割ブロック１５及びビット結合ブロック１９に接続される。ビット反転ブロック１６は、ビット分割ブロック１５から入力されるＵｐｐｅｒ―ビットの、ビット（ｊ−１）、及びビットｊの値を反転し、反転を行った反転済ビット列をビット結合ブロック１９に出力する。
ビットシフトブロック１８は、ビット分割ブロック１５及びビット結合ブロック１９に接続される。ビットシフトブロック１８は、ビット分割ブロック１５から入力されるＬｏｗｅｒ―ビットを、ｉビット右シフトし、右シフトを行ったシフト済ビット列をビット結合ブロック１９に出力する。
ビット結合ブロック１９は、ビット反転ブロック１６と、ビットシフトブロック１８と、出力６０と接続される。ビット結合ブロック１９は、ビット反転ブロック１６から入力される反転済ビット列と、ビットシフトブロック１８から入力されるシフト済ビット列とを結合し、結合したビット列を出力６０に出力する。
＜動作＞
次に、図６及び図７のフローチャートを参照して、本実施形態に係る組み合わせ生成装置２の動作について詳細に説明する。
図７は、本実施形態に係る組み合わせ生成装置２の動作の例を示すフローチャートである。
入力１０からは、値が“１”のビットがｋ個存在するＮビット幅のビット列が入力される（ｋ＜Ｎ）。
ビット位置取得ブロック１４は、第１の実施の形態と同様にビットｉとビットｊを求め（ステップＳ１０１、ステップＳ１０２）、ビットｉを示す情報と、ビットｊを示す情報と、入力ビット列と、をビット分割ブロック１５に出力する。
ビット分割ブロック１５は、ビット位置取得ブロック１４から入力される入力ビット列を、ビット（ｊ−１）以上（Ｕｐｐｅｒ―ビット）と、ビット（ｊ−２）以下（Ｌｏｗｅｒ―ビット）に分割し（ステップＳ１１１）、ビットｊを示す情報と、Ｕｐｐｅｒ―ビットと、をビット反転ブロック１６に、ビットｉを示す情報と、Ｌｏｗｅｒ―ビットと、をビットシフトブロック１８に出力する。
出力するビット列は、例えば、Ｕｐｐｅ―ビット、Ｌｏｗｅｒ―ビット共にビット幅を入力ビット列と同じにし、Ｕｐｐｅｒ―ビットのビット（ｊ−２）以下のビット値を全て“０”にし、Ｌｏｗｅｒ―ビットのビット（ｊ−１）以上のビット値を全て“０”にしたビット列が挙げられる。
ビット反転ブロック１６は、ビット分割ブロック１５から入力されるＵｐｐｅｒ―ビットの、ビット（ｊ−１）及びビットｊの値を反転し（ステップＳ１１３）、反転を行った反転済ビット列をビット結合ブロック１９に出力する。
ビットシフトブロック１８は、ビット分割ブロック１５から入力されるＬｏｗｅｒ―ビットをｉビット右シフトし（ステップＳ１１２）、右シフトを行ったシフト済ビット列をビット結合ブロック１９に出力する。
右シフトを行ったビット列の上位には、例えば、ビット値“０”を挿入すると、ビット結合ブロック１９で行う処理が簡潔になる。
ビット結合ブロック１９は、ビット反転ブロック１６から入力される反転済ビット列の（ｊ−１）ビット以上と、ビットシフトブロック１８から入力されるシフト済ビット列の（ｊ−２）ビット以下とを結合し（ステップＳ１１４）、結合したビット列を出力６０に出力する。
ステップＳ１１１により、Ｕｐｐｅｒ―ビットのビット（ｊ−２）以下のビット値及びＬｏｗｅｒ―ビットのビット（ｊ−１）以上のビット値が全て“０”になっている。ビットシフトブロック１８で、シフト済ビット列の上位にビット値”０”が挿入されているならば、ステップＳ１１４の処理は、ステップＳ１１２及びステップＳ１１３からの入力ビット列の論理和をとることで実現できる。これは、ステップＳ１１２の処理の結果、Ｌｏｗｅｒ―ビットのビット（ｊ−１）以上のビット値は全て“０”であり、ステップＳ１１３の処理では、Ｕｐｐｅｒ―ビットのビット（ｊ−２）以下のビット値は全て“０”のままであることによる。
＜実施形態の効果＞
次に、本実施形態に係る組み合わせ生成装置２の効果について詳細に説明する。
本実施形態に係る組み合わせ生成装置２の、ビット反転ブロック１６と、ビットシフトブロック１８が行う処理は、ビット単位で見ると完全に排他である。そこで、本実施形態の組み合わせ生成装置２は、２つに分割した入力ビット列を、それぞれビット反転ブロック１６およびビットシフトブロック１８に入力し、ビット反転ブロック１６とビットシフトブロック１８を並列に動作させる。そのため、本発明の第１の実施の形態に係る組み合わせ生成装置１と比べて、組み合わせの生成処理に要する時間を短縮できるという効果が得られる。
（第４の実施の形態）
＜構成＞
図８は、本発明の第４の実施の形態に係る組み合わせ生成装置３の構成図である。組み合わせ生成装置３は、入力チェックブロック１２と、アービター１３と、終了判定ブロック２０とが、本発明の第１の実施の形態に係る組み合わせ生成装置１と異なり、その他の構成要素は、本発明の第１の実施の形態に係る組み合わせ生成装置１と同様である。本発明の第１の実施の形態に係る組み合わせ生成装置１と同様の構成要素については、図１と同一の符号を付し、詳細な説明を省略する。
＜動作＞
図８及び図９のフローチャートを参照して、本実施形態に係る組み合わせ生成装置３の動作について詳細に説明する。図９は、本実施形態に係る組み合わせ生成装置３の動作の例を示すフローチャートである。
入力１１からは、値が“１”のビットがｋ個存在するＮビット幅のビット列（ｋ＜Ｎ）、またはＮとｋ、またはｋが入力される。さらに、組み合わせの生成を終了する条件も入力される。
入力チェックブロック１２は、入力１１と、アービター１３と、終了判定ブロック２０と、出力８３０と、接続される。
入力チェックブロック１２は、組み合わせ生成装置３がビジー状態でない場合に、入力１１から、入力を受け付ける。入力を受け付けられない場合は、それを示す信号を出力８３０から出力する。以下、入力チェックブロック１２が入力を受け付けることができる場合について説明する。
入力がＮビット幅のビット列の場合、入力チェックブロック１２は、入力のＮビット幅のビット列に対して、所定の基準により、組み合わせが生成可能かどうかの判定を行う。組み合わせが生成できない場合、入力チェックブロック１２は、組み合わせの生成を行わないことを示す信号を出力８３０に出力する（ステップＳ１２１、ＮＯ）。組み合わせが生成可能な場合、入力チェックブロック１２は、入力ビット列をアービター１３に出力し、終了判定ブロック２０に、組み合わせの生成処理を終了する条件を設定する（ステップＳ１２１、ＹＥＳ）。
組み合わせの生成処理を終了する条件として、例えば、ビットシフトブロック１８から出力されたビット列が特定の値になった場合、組み合わせを特定の個数生成した場合、などが挙げられる。
組み合わせが生成できない入力の例として、例えば、入力ビット列のビット値が全て“０“の場合のように、ビットｉが求められない場合がある。また、入力ビット列の値が”１“であるビットの個数がｋ個で、入力ビット列の上位ｋビットが”１“（＝値が”１“であるビットがｋ個のビット列の最大値）である場合のように、ビットｊが求められない場合が挙げられる。また、終了条件が不正な場合にも、ビット列の生成を行わないようにすることもできる。終了条件が不正な例として、例えば、「生成する組み合わせのｋの値と異なる個数の１を含むビット列と一致した場合に終了する」という条件が挙げられる。
次に、入力チェックブロックへの入力が、ビット列ではなく、Ｎとｋである場合について説明する。この場合、入力チェックブロック１２は、Ｎ及びｋに対して、所定の基準により、組み合わせが生成可能かどうかの判定を行う。組み合わせが生成できない場合、入力チェックブロック１２は、組み合わせの生成を行わないことを示す信号を出力８３０に出力する（ステップＳ１２１、ＮＯ）。組み合わせが生成可能な場合、入力チェックブロック１２は、Ｎとｋから初期ビット列を生成し、生成したビット列をアービター１３に出力し、終了判定ブロック２０に、組み合わせの生成処理を終了する条件を設定する（ステップＳ１２１、ＹＥＳ）。
組み合わせが生成できない入力の例として、例えば、Ｎ、またはｋのいずれかが“０”の場合、ｋ≧Ｎの場合が挙げられる。また、終了条件が不正な場合にも、ビット列の生成を行わないようにすることもできる。
次に、入力チェックブロックへの入力が、ｋである場合について説明する。入力チェックブロック１２は、あらかじめ扱えるビット幅Ｎが決まっている場合、入力をｋのみとすることができる。この場合、入力チェックブロック１２は、入力のｋに対して、所定の基準により、組み合わせが生成可能かどうかの判定を行う。組み合わせが生成できない場合、入力チェックブロック１２は、組み合わせの生成を行わないことを示す信号を出力８３０に出力する（ステップＳ１２１、ＮＯ）。組み合わせが生成可能な場合、入力チェックブロック１２は、ｋから初期ビット列（Ｎビット幅）を生成し、生成したビット列５３０をアービター１３に出力し、終了判定ブロック２０に、組み合わせの生成処理を終了する条件を設定する（ステップＳ１２１、ＹＥＳ）。
組み合わせが生成できない入力の例として、例えば、ｋが“０”の場合、ｋ≧Ｎの場合が挙げられる。また、終了条件が不正な場合にも、ビット列の生成を行わないようにすることもできる。
アービター１３は、入力チェックブロック１２と、ビット位置取得ブロック１４と、終了判定ブロック２０と接続される。アービター１３は、入力チェックブロック１２と、終了判定ブロック２０のそれぞれから入力されるビット列５３０，７３０から、ビット位置取得ブロック１４に出力するビット列を選択する（ステップＳ１２３）。
組み合わせ生成装置３は、終了判定ブロック２０に設定される終了条件を満たすまで、組み合わせを生成し続ける。組み合わせの生成が終了するまでは、アービター１３が、終了判定ブロック２０から入力されるビット列７３０をビット位置取得ブロック１４に出力することで、組み合わせ生成装置３は、連続して組み合わせを生成する。
そこで、アービター１３では、例えば、組み合わせ生成装置３で組み合わせの生成を行っていない場合に、入力チェックブロック１２からの入力ビット列５３０を、ビット位置取得ブロック１４に出力するといった入力ビット列の制御が必要になる。
アービター１３は、組み合わせの生成を行っている間、組み合わせ生成装置３がビジー状態であるとし、それを示す信号４３０を入力チェックブロック１２に出力する。
ビット位置取得ブロック１４は、アービター１３と、ビット反転ブロック１６と接続される。ビット位置取得ブロック１４は、アービター１３から入力されたビット列から、本発明の第１の実施の形態に係る組み合わせ生成装置１と同様にビットｉ及びビットｊを求め、ビットｉを示す情報と、ビットｊを示す情報と、アービター１３から入力されたビット列と、をビット反転ブロック１６に出力する（ステップＳ１０１、ステップＳ１０２）。
ビット反転ブロック１６は、本発明の第１の実施の形態に係る組み合わせ生成装置１と同様に、ビット位置取得ブロック１４から入力されたビット列のビットｊとビット（ｊ−１）の値を反転する（ステップＳ１０３）。ビット反転ブロック１６は、ビットｊとビット（ｊ−１）の値を反転したビット反転済ビット列をビットシフトブロック１８に出力する。
ビットシフトブロック１８は、ビット反転ブロック１６と、終了判定ブロック２０と接続される。ビットシフトブロック１８は、本発明の第１の実施の形態に係る組み合わせ生成装置１と同様に、ビット反転ブロック１６から入力される反転済ビット列に対して、右シフト処理を行う（ステップＳ１０４）。ビットシフトブロック１８は、右シフトを行ったシフト済ビット列を終了判定ブロック２０に出力する。
終了判定ブロック２０は、入力チェックブロック１２と、アービター１３と、ビットシフトブロック１８と、出力６０と接続される。終了判定ブロック２０は、ビットシフトブロック１８から入力されるビット列を出力６０に出力し、また、ビット列の生成を終了するかどうかを判定する（ステップＳ１２２）。終了判定ブロック２０は、ビット列の生成を終了する場合（ステップＳ１２２、ＹＥＳ）、ビット列の生成を終了することを示す信号も出力６０に出力する。終了判定ブロック２０は、ビット列の生成を継続する場合（ステップＳ１２２、ＮＯ）、ビットシフトブロック１８から入力されたビット列を、ビット列の生成を継続することを示す信号と共に、アービター１３に出力する。
なお、ビット列の生成を終了する場合、それを示す信号をアービター１３に出力することで、組み合わせの生成を終了することをアービター１３に通知することも考えられる。
終了判定ブロック２０は、入力チェックブロック１２から入力された、組み合わせの生成を終了する条件により、組み合わせの生成処理を終了するか否かを判定する。組み合わせの生成処理を終了する条件として、上述した通り、例えば、ビットシフトブロック１８から入力されたビット列が特定の値になった場合、組み合わせを特定の個数生成した場合、などが挙げられる。そのため、終了判定ブロック２０には、生成した組み合わせの個数を数えるためのカウンタや、比較のための手段、記憶装置が必要となる。
＜実施形態の効果＞
次に、本実施形態係る組み合わせ生成装置３の効果について詳細に説明する。
本実施形態に係る組み合わせ生成装置３は、入力チェックブロック１２を備え、入力チェックブロック１２が組み合わせを生成できるか否かを判定することにより、組み合わせが生成できない場合を排除することができる。組み合わせ生成装置３は、さらに、入力チェックブロック１２内部で入力された情報をもとにビット列の生成を行うことにより、組み合わせ生成装置に対する入力の形式に、ビット列以外のものを用いることができる。
また、本実施形態に係る組み合わせ生成装置３は、終了判定ブロック２０を含み、終了判定ブロック２０が入力した終了判定条件に基づいて組み合わせの生成を終了する。これにより、本実施形態に係る組み合わせ生成装置３は、任意の個数の組み合わせを生成することや、組み合わせの生成を任意の時点で止めることが可能となる。組み合わせ生成装置３は、さらに、生成した組み合わせを表すビット列を、次に組み合わせを生成する際の入力とし、繰り返し組み合わせの生成を行う。このことにより、組み合わせ生成装置３は、入力１０から組み合わせを生成するための入力を一度行うだけで、組み合わせを次々に生成することが可能となる。
（第５の実施の形態）
＜構成＞
図１０は、本発明の第４の実施の形態に係る組み合わせ生成装置４の構成図である。組み合わせ生成装置４は、ビット位置取得ブロック２２が、本発明の第１の実施の形態に係る組み合わせ生成装置１と異なり、その他の構成要素については、本発明の第１の実施の形態に係る組み合わせ生成装置１と同様である。本発明の第１の実施の形態に係る組み合わせ生成装置１と同様の構成要素については、図１と同一の符号を付し、詳細な説明を省略する。
図１１は、ビット位置取得ブロック２２のブロック図である。図１１を参照すると、ビット位置取得ブロック２２は、ビット値“１”の最下位ビット位置取得ブロック１４２と、論理和演算ブロック１４６と、ビット値“０”の最下位ビット位置取得ブロック１４８とを含む。
＜動作＞
図１１及び図１２のフローチャートを参照して、ビット位置取得ブロック２２の動作について詳細に説明する。
図１２は、本実施形態に係る組み合わせ生成装置４の、ビット位置取得ブロック２２の動作の例を示すフローチャートである。
入力１０からは、値が“１”のビットがｋ個存在するＮビット幅のビット列が入力される（ｋ＜Ｎ）。
ビット値“１”の最下位ビット位置取得ブロック１４２は、入力１０と、論理和演算ブロック１４６と接続される。ビット値“１”の最下位ビット位置取得ブロック１４２は、入力１０から入力される入力ビット列に対してビット探索を行い、ビットｉを求める（ステップＳ１０２０）。
また、ビット値“１”の最下位ビット位置取得ブロック１４２は、入力ビット列の、ビットｉより下位の全てのビットのビット値を“１”にしたビット列を生成する（ステップＳ１０２１）。ビット値“１”の最下位ビット位置取得ブロック１４２は、入力ビット列、ビットｉを示す情報と共に、ビットｉより下位の全てのビットのビット値を“１”にしたビット列を論理和演算ブロック１４６に出力する。
ここで、ビット値“１”の最下位ビット位置取得ブロック１４２が生成するビット列の、ビットｉ及びビットｉより上位のビットの値は、入力ビット列の対応するビットの値と同じではなく、“０”にしてもよい。また、前記ビットｉ及びビットｉより上位のビットの値は、任意の値でもよい。しかし、前記ビットｉより下位の全てのビットのビット値を“１”にしたビット列の、ビットｉ以上のビット位置の各ビットの値を、全て“０”か、入力ビット列の値をそのままにしたものにすると、論理和演算ブロック１４６で行う処理が簡潔になる。
以下、ビット値“１”の最下位ビット位置取得ブロック１４２が生成する、ビットｉより下位の全てのビットのビット値を“１”にしたビット列を、下位ビットマスクビット列と表記する。
なお、ステップＳ１０２０とステップＳ１０２１は、ステップＳ１０２０の後にステップＳ１０２１を実行しても、ステップＳ１０２０とステップＳ１０２１を同時に実行してもよい。後者の場合、例えば、入力ビット列を下位ビットからチェックし、ビットｉが見つかるまで、チェックしたビットのビット値を“１”にするといった方法で、ステップＳ１０２０と、ステップＳ１０２１を同時に実行することができる。
論理和演算ブロック１４６は、ビット値“１”の最下位ビット位置取得ブロック１４２と、ビット値“０”の最下位ビット位置取得ブロック１４８と接続される。論理和演算ブロック１４６は、ビット値“１”の最下位ビット位置取得ブロック１４２から入力される２つのビット列の論理和をとる（ステップＳ１０２２）。論理和演算ブロック１４６は、入力ビット列、ビットｉを示す情報と共に、論理和をとったビット列をビット値“０”の最下位ビット位置取得ブロック１４８に出力する。
下位ビットマスクビット列の、ビットｉ以上のビット位置の各ビットの値が、全て０か、入力ビット列の対応するビットと同じ値である場合、論理和演算ブロック１４６は、入力ビット列及び下位ビットマスクビット列の全てのビットで論理和をとり、ビット列を生成する。一方、下位ビットマスクビット列の、ビットｉ以上のビット位置の各ビットの値を、他の値にした場合、ビットｉより下位のビットでのみ論理和をとり、他のビットは入力ビット列と同一の値であるビット列を生成する。
ビット値“０”の最下位ビット位置取得ブロック１４８は、論理和演算ブロック１４６と、出力３００と接続される。ビット値“０”の最下位ビット位置取得ブロック１４８は、論理和演算ブロック１４６で論理和をとったビット列の、値が“０”であるビットのうち、最も下位に位置するビットを求める（ステップＳ１０２３）。このビットがビットｊに相当する。得られたビットｊを示す情報を、入力ビット列と、ビットｉを示す情報と共に、出力３００に出力する。
＜実施形態の効果＞
次に、本実施形態に係る組み合わせ生成装置４の効果について詳細に説明する。
本実施形態に係る組み合わせ生成装置４では、ビット位置取得ブロック２２を備えることにより、ビットｉ、及びビットｊを容易に求めることが可能となり、本発明の第１の実施の形態に係る組み合わせ生成装置１と比べて、組み合わせ生成装置の構成を簡潔にすることができる。
特に、ビットｊについては、「ビットｉより上位に位置するビットのうち」という条件がつくため、ビット探索の開始位置がビット列によって変化する。これを、ビット値”１”の最下位ビット位置取得ブロック１４２と、論理和演算ブロック１４６により、入力ビット列のビットｉ以下のビット値を全て１にすることによって、「ビットｉより上位に位置するビットのうち」という条件を排除することが可能となる。
（第６の実施の形態）
＜構成＞
図１３は、本発明の第６の実施の形態に係る組み合わせ生成装置５の構成図である。組み合わせ生成装置５は、ビット位置取得ブロック２４が、本発明の第１の実施の形態に係る組み合わせ生成装置１と異なり、その他の構成要素については、本発明の第１の実施の形態に係る組み合わせ生成装置１と同様である。本発明の第１の実施の形態に係る組み合わせ生成装置１と同様の構成要素については、図１と同一の符号を付し、詳細な説明を省略する。
図１４は、ビット位置取得ブロック２４のブロック図である。図１４を参照すると、ビット位置取得ブロック２４は、ビット値“１”の最下位ビット位置取得回路１４３と、ビット値”０”の最下位ビット位置取得回路１４９が、本発明の第５の実施の形態に係る組み合わせ生成装置４の、ビット位置取得ブロック２２と異なり、その他の構成要素については、本発明の第５の実施の形態に係る組み合わせ生成装置４の、ビット位置取得ブロック２２と同様である。本発明の第５の実施の形態に係る組み合わせ生成装置４の、ビット位置取得ブロック２２と同様の構成要素については、図１１と同一の符号を付し、詳細な説明を省略する。
図１５は、ビット値”１”の最下位ビット位置取得回路１４３のブロック図である。図１５を参照すると、ビット値”１”の最下位ビット位置取得回路１４３は、入力１０から入力ビット列を入力する入力部１５１２と、出力値を設定する記憶部１５１４と、出力を選択するマルチプレクサ群１５１６と、を備える出力選択回路である。入力部１５１２は、たとえば、ｎビットのシフトレジスタである。マルチプレクサ群１５１６は、入力部１５１２からの各ビットの出力に基づいて、記憶部１５１４からの出力を選択する。
＜動作＞
本実施形態に係る組み合わせ生成装置５の、ビット位置取得ブロック２４の動作は、本発明の第５の実施の形態に係る組み合わせ生成装置４の、ビット位置取得ブロック２２と同様であり、フローチャートも図１２と同様であるため、動作の説明に図１２を用いる。
ビット値”１”の最下位ビット位置取得回路１４３は、入力ビット列の各ビットの値に応じて、マルチプレクサ群１５１６を構成するマルチプレクサの出力を制御し、記憶部１５１４に格納されている出力値のいずれかを、入力ビット列と共に、出力１５２に出力する。
図１５に示すビット値”１”の最下位ビット位置取得回路１４３（出力選択回路）は、図１２のステップ１０２０と、ステップ１０２１の処理のために用いる。次に、ビット値”１”の最下位ビット位置取得回路１４３の具体例について説明する。
図１６は、入力ビット列が８ビットの場合に、入力ビット列を入力し、ビットｉのビット値のみを“１”にしたビット列を出力するように、記憶部１５１４を設定した例である。このような設定を行うことで、ビットｉを容易に求めることが可能となる。
図１７は、入力ビット列が８ビットの場合に、入力ビット列を入力し、ビットｉより下位に位置する全てのビットのビット値を“１”にし、ビットｉ以上のビット位置のビットのビット値を全て“０”にしたビット列を出力するように、記憶部１５１４を設定した例である。このような設定を行うことで、論理和演算ブロック１４６の処理が簡潔になる。なお、図１７では、入力が“０“の場合に”１１１１１１１１“を出力するように設定されており、このような特殊な値を用いて、例外の検出を行うこともできる。
ビット値”０”の最下位ビット位置取得回路１４９も、ビット値”１”の最下位ビット位置取得回路１４３と同様に、図１５の構成をとる。
図１８は、入力ビット列が８ビットの場合に、入力ビット列の、値が“０”であるビットのうち、最も下位に位置するビットのビット値のみを“１”にしたビット列を出力するように、記憶部１５１４を設定した例である。このような設定をおこなうことで、ビットｊを容易に求めることが可能となる。
また、本第５の実施形態は、図６に示す本発明の第３の実施形態に係る組み合わせ生成装置２の、ビット分割ブロック１５に対して適用することで、ビット分割を容易にすることが可能である。
ビット列を分割する場合、入力に対してマスクをかけ、分割するのが一般的である。ビット分割ブロック１５が、ビット値“１”のビット位置取得ブロック２４に対して、ビット（ｊ−１）より下位のビットのビット値が全て“１”であり、ビット（ｊ−１）以上のビットのビット値が全て“０”であるビット列を出力するような設定を行うことで、ビット（ｊ−２）以下のビットのみを取り出すためのマスクを得ることができる。同様に、ビット分割ブロック１５が、ビット値“１”のビット位置取得ブロック２４に対して、ビット（ｊ−１）以上のビットのビット値が全て１であり、ビット（ｊ−２）以下のビットのビット値が全て０であるビット列を出力するような設定を行うことで、ビット（ｊ−１）以上のビットのみを取り出すためのマスクを得ることができる。
＜実施形態の効果＞
次に、本実施形態に係る組み合わせ生成装置５の効果について詳細に説明する。
本実施形態に係る組み合わせ生成装置５では、ビット値”１”の最下位ビット位置取得回路１４３や、ビット値”０”の最下位ビット位置取得回路１４９を、マルチプレクサを用いた出力選択回路で構成することで、１ステップでビットｉやビットｊを求めることができ、組み合わせの生成に要するステップ数を削減することができる。また、複数ビットを同時に処理可能であるため、処理に要するステップ数が入力ビット列のビット幅に比例しなくなるという効果がある。
（第７の実施の形態）
＜構成＞
図１９は、本発明の第７の実施の形態に係る組み合わせ生成装置６の構成図である。組み合わせ生成装置６は、ビット位置取得ブロック２６が、本発明の第１の実施の形態に係る組み合わせ生成装置１と異なり、その他の構成要素については、本発明の第１の実施の形態に係る組み合わせ生成装置１と同様である。本発明の第１の実施の形態に係る組み合わせ生成装置１と同様の構成要素については、図１と同一の符号を付し、詳細な説明を省略する。
本実施形態に係る組み合わせ生成装置６は、入力ビット列について、ビット分割を行い、ビット探索を並列に実行可能としていることを特徴とする。
図２０は、ビット位置取得ブロック２６の内部構造を示したものである。図２０を参照すると、ビット位置取得ブロック２６は、木構造状の階層構造を形成しており、入力１０からビット列が入力される第一階層１４２０と、第一階層１４２０より１階層上位に位置する第二階層１４２２と、第二階層１４２２より上位に位置する、任意の階層数から構成される上位階層１４２４と、最上位階層１４２６と、を備える。
入力されるビット列の長さによっては、ビット位置取得ブロック２６は、第一階層１４２０のみから構成され、第一階層１４２０に、入力１０と、出力３００が接続される場合や、第一階層１４２０と、第二階層１４２２から構成され、第二階層１４２０に、出力３００が接続される場合も考えられる。
第一階層１４２０には、ビット探索ブロック１４２１が１個以上存在する。第二階層１４２２、及び上位階層１４２４には、ビット探索ブロック１４２５が各階層に１個以上存在する。最上位階層１４２６には、ビット探索ブロック１４２７が１個存在する。
必要な階層数や、最上位階層１４２６を除く各階層に何個のビット探索ブロックが必要かは、入力ビット列のビット幅や、各層のビット探索ブロックが、何個の下位層のビット探索ブロックと接続されるかによって決まる。
各階層内のビット探索ブロックが扱うデータのビット幅（ｍとする）が全て同じである場合、入力ビット列のビット幅をＮ０とすると、第一階層のビット探索ブロック１４２１の個数Ｎ１は、Ｎ０÷ｍ個となる。ここで、ｍはＮ０の約数であるとする。第二階層のビット探索ブロック１４２５の個数Ｎ２は、第二階層の各ビット探索ブロック１４２５に第一階層のビット探索ブロック１４２１がＰ１個接続されるとすると、Ｎ１÷Ｐ１個となる。ここで、Ｐ１はＮ１の約数であるとする。このようにして、各階層に何個のビット探索ブロックが必要かを求めることができる。
図２１は、５１２ビット幅の入力に対して、ビット位置取得ブロック２６の例を示したものである。図２１では、階層構造として８分木を用いており、階層数はｌｏｇ８５１２＝３となる。
図２１のように、Ｎ０＝５１２、ｍ＝８、Ｐ１＝８の場合、第一階層のビット探索ブロック１４２１の個数Ｎ１は、５１２÷８＝６４個となり、第二階層のビット探索ブロック１４２５の個数Ｎ２は、６４÷８＝８個となる。
なお、ここでは同じ階層の各ビット探索ブロックが扱うデータのビット幅を固定にしたが、ビット探索ブロック間で異なるビット幅を扱ってもよく、そのようにするとｍやＰｘがＮｘなどの約数でなくとも、任意の値を採ることができるようになる。
＜動作＞
第一階層１４２０は、入力１０及び第二階層１４２２に接続される。入力１０は、第一階層１４２０の内部で所定のビット幅に分割される。入力１０から入力される入力ビット列は、前記所定のビット幅の複数のビット列に分割される。分割された各ビット列はそれぞれ異なるビット探索ブロック１４２１に入力される。ビット探索ブロック１４２１は、それぞれ、分割されたビット列ごとにビットｉを求め、結果を第二階層１４２２に出力する。
第二階層１４２２は、第一階層１４２０と、上位階層１４２４と接続される。第一階層からの入力は、入力ビット列中の対応する位置に応じてグループ化され、ビット探索ブロック１４２５に入力される。各ビット探索ブロック１４２５はビットｉを求め、求めた結果を上位階層１４２４に出力する。
例えば、図２１の例では、第一階層１４２０の各ビット探索ブロック１４２１には、入力ビット列の０〜７ビット、８〜１５ビット、・・・、５０４〜５１１ビット、というように入力ビット列が分割されて入力される。図２１の例では、第一階層のビット探索ブロックが８個、第二階層の各ビット探索ブロックに接続されるため、第二階層では、入力ビット列の０〜６３ビット、６４〜１２７ビット、・・・、４４８〜５１１ビットというように、６４ビット単位で分割されて処理される。
出力されるデータの形式の例として、例えば、ビットｉの値のみを“１”にしたビット列や、ビットｉのビット位置を示す整数値などが挙げられる。
上位階層１４２４は、自階層より１つ下の階層及び１つ上の階層に接続される。１つ下の階層からの入力に対して、第二階層１４２２で行われる前記の処理と同じ処理を実行し、１つ上の階層に出力する。
最上位階層１４２６は、１つ下の上位階層１４２４に接続される。最上位階層１４２６は、１つ下の上位階層１４２４からの入力に対して、第二階層１４２２で行われる前記の処理と同一の処理を実行し、出力３００に出力する。
各階層間にレジスタは必須ではないが、階層数が増加すると遅延が増大するため、遅延を小さくするために各階層間にレジスタを配置し、複数サイクルでビットｉを求めるという手法も採ることができる。
ビットｊについても、ビットｉと同様に求めることができる。なお、上位階層になるほど、１つのビット探索ブロックで扱うビット幅が増加するため、下位のビット探索ブロックからの入力についてリダクション論理和を取り、ビット列中に“１”を含むかどうかということを示す情報に変換することで、扱うビット幅を減らすことができる。
図２１の例では、第一階層１４２０から第二階層１４２２に入力される８個の８ビットの出力値、それぞれについてリダクション論理和を取り、８個の１ビットの情報に変換して、第二階層に入力する。この処理により、各ビット探索ブロック１４２１からの出力が０か、０でないかという情報に変換される。その８個の１ビットの値に対してビットｉの探索と同様の処理を行う。この処理で得られる結果は、８個の入力のいずれにビットｉが含まれるかというものである。該当する第一階層１４２０のビット探索ブロック１４２１からの入力と、リダクション論理和の結果を上位階層１４２４に出力する。
つまり、第二階層１４２２の各ビット探索ブロック１４２５では、第一階層１４２０のどの８ビットにビットｉが含まれているかという情報と、該当する８ビットを上位階層１４２４に出力する。上階層１４２４や、最上位階層１４２６でも、同様のリダクション演算を行う。
このようにすることで、上位階層１４２４や、最上位階層１４２６で行うビット探索処理を大幅に削減することができる。
最終的に得られる結果は、図２１の例では、第一階層１４２０のビット探索ブロック１４２１のいずれかから出力された８ビットのデータ（入力ビット列の一部）と、その８ビットが入力ビット列中のどのビット位置であるかという情報である。ビット位置を示す情報を用いることで、ビットｉ、及びビットｊのビット位置を得ることができる。
＜実施形態の効果＞
次に、本実施形態に係る組み合わせ生成装置６の効果について詳細に説明する。
本実施形態に係る組み合わせ生成装置６では、ビット位置取得ブロック２６を階層構造とすることで、入力ビット列に対して、並列にビット探索を行うことができる。これにより、入力ビット列のビット幅が増加しても、処理ステップ数が入力ビット列のビット幅に比例することなく、ビットｉやビットｊを高速に探索することができる。
（第８の実施の形態）
＜構成＞
図２２は、本発明の第８の実施の形態に係る組み合わせ生成装置７の構成図である。組み合わせ生成装置７は、パイプラインレジスタ２８が、本発明の第１の実施の形態に係る組み合わせ生成装置１と異なり、その他の構成要素については、本発明の第１の実施の形態に係る組み合わせ生成装置１と同様である。本発明の第１の実施の形態に係る組み合わせ生成装置１と同様の構成要素については、図１と同一の符号を付し、詳細な説明を省略する。
＜動作＞
本実施形態に係る組み合わせ生成装置７は、本発明の第１の実施の形態に係る組み合わせ生成装置１にパイプラインレジスタを加えたものであり、ビット位置取得ブロック１４、ビット反転ブロック１６、ビットシフトブロック１８を、各パイプラインステージとし、組み合わせの生成をパイプラインで生成可能としたものである。
各ブロックの処理の遅延の長さによっては、例えば、ビット位置取得ブロック１４内部にもパイプラインレジスタを設け、ビット位置取得ブロック１４を複数のパイプラインステージで構成することや、ビット反転ブロック１６とビットシフトブロック１８を同一のパイプラインステージとすることも考えられる。
＜実施形態の効果＞
次に、本実施形態に係る組み合わせ生成装置７の効果について詳細に説明する。
本実施形態に係る組み合わせ生成装置７では、パイプラインレジスタ２８を備えることで、組み合わせの生成のための各処理をパイプラインで実行可能としている。これにより、組み合わせ生成装置の動作速度を上げることができ、組み合わせの生成を本発明の第１の実施の形態に係る組み合わせ生成装置１と比べて、高速に行うことができる。また、パイプラインの段数と同じ数だけ、組み合わせの生成処理を並列に実行することが可能となり、その点でも組み合わせの生成速度を上げることができる。
なお、本発明の第１〜第８の実施例を組み合わせて、組み合わせ生成装置を実施することも可能である。
例えば、本発明の第７の実施の形態に係る組み合わせ生成装置６におけるビット探索ブロックに、本発明の第６の実施の形態に係る組み合わせ生成装置５における図１５の回路を適用することなどが可能である。
本発明の実施形態に係る組み合わせ生成装置（図１、図６、図８、図１０、図１３、図１９、図２２）は、入力ビット列から、特定の条件を満たすビットのビット位置を求めるビット位置取得手段（図１の１４、図６の１４、図８の１４、図１０の２２、図１３の２４、図１９の２６、図２２の１４）と、前記ビット位置取得手段で求めたビット位置をもとに、特定の位置のビット値を反転するビット反転手段（図１の１６、図６の１６、図８の１６、図１０の１６、図１３の１６、図１９の１６、図２２の１６）と、前記ビット位置取得手段で求めたビット位置をもとに、前記ビット反転手段で求めたビット列の、特定のビットを特定のビット幅だけシフトするビットシフト手段（図１の１８、図６の１８、図８の１８、図１０の１８、図１３の１８、図１９の１８、図２２の１８）と、を備えている。
従って、加算処理を行う手段を用いずに組み合わせを生成することから、第１の目的を達成することができる。また、選び出す要素数に依存したブロックが存在せず、入力に対して一定の処理を行うことができる。
また、組み合わせ生成装置（図１３）におけるビット位置取得手段（図１３の２４）は、入力されたビット列に対して、複数ビット同時に処理を行うことができる回路（図１５）を、備えている。
従って、組み合わせの生成処理に要するステップ数が入力ビット幅に比例しなくなる。
また、組み合わせ生成装置（図１９）におけるビット位置取得手段（図１９の２６）は、入力されたビット列を分割して、並列に処理することができる構造（図２０）を、備えている。
従って、組み合わせの生成処理に要するステップ数が入力ビット幅に比例しなくなる。
以上、実施の形態を説明したが、特許請求の範囲に定義された本発明の広範囲な趣旨および範囲から逸脱することなく、これら実施の形態や具体例に様々な修正および変更が可能である。また、本発明に係る処理をコンピュータに実行させるためのプログラムなどが格納された記憶媒体も本発明を構成する。
また、本発明におけるプログラムは、組み合わせ生成装置による入力ビット列から反転を行うビットの反転ビット位置と、シフトを行うビットのシフトビット位置と、シフトビット位置のビットを最下位ビットにシフトするのに要するシフト幅とを求めるビット位置取得処理と、ビット位置取得処理によって求めた反転ビット位置のビットのビット値と、それより１ビット下位に位置するビットのビット値を反転するビット反転処理と、ビット反転処理によって求めたビット列について、反転ビット位置から２ビット下位のビット以下に位置する全てのビットを、ビット位置取得処理によって求めたシフト幅だけシフトするビットシフト処理と、解選択装置によるビットシフト処理から出力される各組み合わせのビット列に対して、コスト計算を行うためのパラメータを用いてコストを計算するコスト計算処理と、コスト計算処理によって計算されたコストを基にして所望のビット列を選択する解選択処理と、をコンピュータに実行させることを特徴とする。
【実施例】
【００１１】
上述した各実施形態を例に説明した本発明の活用例として、世の中に存在する、組み合わせ最適化問題に分類される諸問題を高速に解くのに適用可能であることが挙げられる。
表２に本発明の実施の形態に係る組み合わせ生成装置をハードウェア化した場合に、扱える演算ビット幅を変更することで、要素群を構成する要素数の総数Ｎを変化させて、最大動作周波数を測定した結果を示す。この測定においては、本発明の第１〜第８の実施形態に係る組み合わせ生成装置を組み合わせて、ハードウェア化を行った。
【表２】
2010107102.tif 000004
表２を参照すると、表１に示した、非特許文献１をハードウェア化した場合に比べて、Ｎの値が増加しても動作周波数の低下を抑えられており、非特許文献１のアルゴリズムを専用ハードウェア化した場合に比べて、Ｎが１０２４の場合に約１０倍の性能向上を示している。この性能はＣＰＵ（Ｉｎｔｅｌ  Ｘｅｏｎ  ３．６ＧＨｚ）の性能の約５００倍となる。
また、図２３に、Ｎを１０２４まで増加させ、Ｎ個の要素から４個の要素を選択する場合の解の候補を生成する場合の、各手法の実行時間を示す。２３０１は、非特許文献１のアルゴリズムに基づくソフトウェアを前記ＣＰＵで実行した場合の実行時間の測定結果である。２３０２は、非特許文献１のアルゴリズムをハードウェア化した場合の実行時間の測定結果である。２３０１及び２３０２は、それぞれ、図２４の２４０１及び２４０２と同じである。一方、２３０３は、本発明の第１〜第７の実施形態における組み合わせ生成方法を組み合わせてハードウェア化した組み合わせ生成装置での実行時間の測定結果である。
本実施例の実行時間の測定結果によると、本発明の組み合わせ生成装置は、ハードウェア化を行うことで、ソフトウェアで実行する場合と比較して、大幅な高速化が可能である。
以上、実施形態及び実施例を参照して本願発明を説明したが、本願発明は上記実施形態及び実施例に限定されるものではない。本願発明の構成や詳細には、本願発明のスコープ内で当業者が理解し得る様々な変更をすることができる。
この出願は、２００９年３月１８日に出願された日本出願特願２００９−０６６２２８を基礎とする優先権を主張し、その開示の全てをここに取り込む。
【図１】
2010107102.tif 000005
【図２】
2010107102.tif 000006
【図３】
2010107102.tif 000007
【図４】
2010107102.tif 000008
【図５】
2010107102.tif 000009
【図６】
2010107102.tif 000010
【図７】
2010107102.tif 000011
【図８】
2010107102.tif 000012
【図９】
2010107102.tif 000013
【図１０】
2010107102.tif 000014
【図１１】
2010107102.tif 000015
【図１２】
2010107102.tif 000016
【図１３】
2010107102.tif 000017
【図１４】
2010107102.tif 000018
【図１５】
2010107102.tif 000019
【図１６】
2010107102.tif 000020
【図１７】
2010107102.tif 000021
【図１８】
2010107102.tif 000022
【図１９】
2010107102.tif 000023
【図２０】
2010107102.tif 000024
【図２１】
2010107102.tif 000025
【図２２】
2010107102.tif 000026
【図２３】
2010107102.tif 000027
【図２４】
2010107102.tif 000028
【国際調査報告】
2010107102.tif 000029
2010107102.tif 000030