■ 組合せ演算 (KV File: conbinex_xxx 

⇒ TO Home Page
内容

ランダムな数値の入った有限個の箱から値を選び、その組合せ合計が任意の数値になる様な要素を捜します。
ここでは、その数値の入った箱を16個用意しました。また、16個の箱の中から任意の要素を選び、それを使って組合せを行う方法も実験できます。

16個の要素から任意の組合せを導には2の16乗−1回(65535回)の演算回数が必要になります。使用するKV-3000では195msほどかかりま した。
全ての要素を調べる必要のない場合、例えば任意の8個の要素でよい場合は2の8乗−1回(255回)の演算量で済みます。

導く答の計算方法は2種類あります。1つは、求める任意の数に一番近いもの(差分が一番小さいもの。求める数より小さくても大きくてもOK。)
2つ目は、求める数と許容上限を設定して、その範囲に入る最も小さいもの。

実験用に乱数発生ルーチンも実装しています。

このサンプルは他と 独立したプロジェクト にしました。また。
下の「●コードをダウンロード」からダウンロードしてください。検証用のモニタデバイスは「●登録モニタをダウンロード」からダウンロードしてください。
また、実行速度の関係で シミュレーションは不可能 ですので、実機で検証をお願いします。
選択した任意の要素の組合せパターンの変化を確認するモジュールもあります。こちらはシミュレーションでも差支えなく実験できると思います。

●PDFを表示  ●コードをダウンロード   ●登録モニタをダウンロード
◆ 組合せ演算実験モジュール 【 Combination 】 

00004
・[乱数発生]をセットすると16個の組合せ要素[@FM0]〜[@FM15]に乱数が代入されます。
・[組合開始]をセットすると、与えた条件で組合せ演算を行います。

00013
・サブルーチン10で組合せ演算を実行します。
・変数にMRを使うと、KV-3000では処理時間が0.05μsec速くなります。
CMD Ref
・結果パターン[@MR300]をリセットします。
・目標値[EM0]を演算用目標値[@MR400]に代入します。
・[LR000]が偽の時、差分が一番小さいモードです。結果を求める初期値(差分)[@MR800]は1ワードが取り得る最大値65535を代入しま す。
・[LR000]が真であれば、目標〜上限の範囲に入る最も小さいものを求めるモードで、上限値を初期値として結果に代入します。

00016
・基本になる要素のパターン[@MR000]で初期値を”FFFFhex” にしています。
・有効要素パターン[@MR100]と上の[@MR000]との論理積を[@MR200]に代入します。この[@MR200]のビットが立っている箇所に 対応する数値が、加算されていきます。
・LOOP回数を決めるため、ビットが立っている箇所の数を調べます。
・今回は実証しませんが、組合せパターンのビットの数の範囲を制限して演算する事もできます。そのため、有効要素数が設定ビット数の下限[EM2]未満な らラベル2へ飛び、終了します。
・今回は初期値で下限を1、上限を16としています。
・LOOP回数[@MR600]を計算します。繰返し回数は2の有効ビット数乗−1なので”0000 0000 0000 0001bin” を上位へ有効ビット数分シフトし(×2をビット数分するのと同等)−1します。

00021
・これも組合せ要素個数制限のためのコードです。個数が範囲外なら加算を止めて、ラベル3へ飛び、次の組合せパターンを作ります。

00023
・組合せ結果を”0”にして、立っているビットに対応した位置[@MR200]〜[@MR215]の要素の数値[@FM0]〜[@FM15]を加算しま す。
・[@MR200]〜[@MR215]の16ビット分記述しています。インデックス修飾で記述もできますが、処理時間がかかり過ぎるので、バラバラに書き ます。
・インデックス修飾のコードも、コメントアウトしていますので、実証してみてください。要素数16個の時、スキャンタイムオーバーが出ました。

00046
・組合せパターンに従って加算された値を[@MR700]に代入します。

00048
・差分が一番小さいものを求めるモードです。
・基本的には最初の「LDA @MR700」は不要です。処理時間を短くできます。(レジスタに加算結果が有るので)
・組合せ結果から目標値を引き、差分を求めます。差分が負数の時は「NEG」命令で符号を反転します。
※差分を求める場合「ABS.S」命令を使用すると、符号付変数として処理され(0〜32767)の範囲でしか処理できません。
・今回の差分(レジスタ)と前回の差分[@MR800]を比較し、今回が小さければ[@MR800]に代入し、現在の加算結果と組合せパターンを最終結果 に代入します。
※ 初回の前回差分は13行目で”65535”(16ビットの最大値)が代入されています。

00050
・許容上限範囲に入る最小値を求めるモードです。
・基本的には最初の「LDA @MR700」は不要です。処理時間を短くできます。(レジスタに加算結果が有るので)
・組合せ加算値が目標[@MR400]〜目標+上限[@MR500]の範囲内ならば、組合せ加算値と最終加算結果を比較し、 現在値の方が小さければ最終加算結果に現在値を代入します。また、今回の組合せパターンも最終結果に代入します。
※ 初回の最終加算結果は14行目で目標+上限が代入されています。

00051
・次回の組合せパターンを生成します。組合せ個数範囲外時もここへジャンプします。
・現在のパターンをデクリメントします。デクリメントに減算命令を使うと「DEC」命令を使うより処理時間を短くできます。この様な演算量が多い処理は注 意が必要です。
KV-3000の場合
SUB:0.02μs
DEC:0.13μs
パターン生成にインクリメントを使うと有効要素の組合せ ができません。
・デクリメントされたパターンと有効要素パターンの論理積をとって次回の組合せパターンとします。
・この時のパターンの変化は『StepCheck』のジュールで確認できます。


00075
・パラメータのデフォルトです。
・乱数生成値範囲[AREA]を最大値”256”に設定しています。生成ルーチン内で”0”を排除しています。
・要素数を16個に設定しています。(1ワード分)
・組合せ結果の個数制限を1〜16個にしています。(制限なし)
・要素数が16なので要素パターンは”FFFFhex” になります。
・有効要素パターンを”11110111bin” に設定しています。

00083
・83行目以降に参照するデバイスを記述しました。
・ビットデバイスはカーソルを合わせ、ダブルクリックでON-OFFできます。
・複数デバイスを選択して、右クリック ⇒ 登録モニタウィンドウ でモニタできます。
「ENDH」以下には自由に落書きができます。回路が成立していなくても変換エラーは起きません。モニタも可能です。
この領域に記述しても、PLCには転送されません。

◇ テスト操作
Screen01
・上の画面にある登録モニタウィンドウを用意しています。 ●登録モニタをダウンロード からダウンロードしてください。
・[乱数派生]をセットすると[@FM0]〜[@FM15]に乱数が代入されます。
・乱数生成範囲[AREA]で、生成範囲を変更できます。
・目標[EM0]、上限範囲[EM1]に数値を入れて、[組合開始]をセットすると演算が開始します。
・[@MR300]に組合せパターンが、[@MR600]に組合せ加算値が代入されます。
・[LR000]が真なら上限ありモード、偽の時は差分最少モードで動作します。

Screen02
・組合せ要素を16ビットにして実行した場合、上の画面の様に、約195msスキャンにかかります。

Screen03
・組合せ要素を16ビットにして、組合せ加算をインデックス修飾するとスキャンタイムオーバーになりました。

・色んな条件でテストしてください。

◆ 有効要素パターンチェックモジュール 【 StepCheck 】

00003
・[Reload]をセットると組合せパターン[@MR200]に有効要素パターン[@MR200]が代入されます。

00004
・[MANUAL]が真の時、[RUN]をセットすると1ステップづつ実行します。
・[MANUAL]が偽の時、500ms毎に実行されます。

00007
・組合せパターンをデクリメントして有効要素パターンとの論理積を自分自身に戻します。
・組合せパターンが16ビットの範囲を超えた場合は、有効要素パターンを組合せパターンに代入します(サブルーチン1)



◇ テスト操作
00022
・83行目以降に参照するデバイスを記述しました。
・ビットデバイスはカーソルを合わせ、ダブルクリックでON-OFFできます。
・複数デバイスを選択して、右クリック ⇒ 登録モニタウィンドウ でモニタできます。
「ENDH」以下には自由に落書きができます。回路が成立していなくても変換エラーは起きません。モニタも可能です。
この領域に記述しても、PLCには転送されません。

・初期値では[MANUAL]は真ですので、[RUN]をダブルクリックでセットする度に1ステップ進みます。
・[MANUAL]をリセットすれば、自動で実行されます。

・初期値の有効要素パターンは”1011 1001bin” になっています。後から変更も可能です。
・有効要素パターン箇所のみデクリメントされていく様子を確認してください。

●PDFを表示  ●コードをダウンロード   ●登録モニタをダウンロード