ある種の割当て問題における解法について
スポンサーリンク
概要
- 論文の詳細を見る
有限個の相異なる値x_1, x_2, …, x_nに対して, それぞれの度数をf_1, f_2, …, f_nとする度数分布が与えられているとする. この分布をmクラスに分割するとき, おのおののクラスに属するx_iの最大値で, そのクラスを代表させるものとする. それぞれのクラスごとの度数の和とクラスの代表値との積和を目的関数とし, この目的関数を最小にするような分割を求める問題に対して, 総当たり組合せ法より少ない計算量で解を得る方法について考察した. 分布をあるクラスに分割したときの最適解の持つ諸性質を調べて定理とし, この定理により(m-1)クラスからmクラスに分割したときの最適解の存在範囲を明らかにした. そして, 最適解の存在範囲を限定することにより, Ο(m-n^2)の組合せ計算で最適解を求める解法を提案した.
- 一般社団法人情報処理学会の論文
- 1982-03-15
著者
関連論文
- 高速2値イメージ圧縮伸張LSIの開発 : ファクシミリと画像一般 : 画像通信システム
- 低速小規模マイクロプロセッサを内蔵したサービスプロセッサ
- ある分割問題の動的計画法による高速アルゴリズム
- ある種の割当て問題における解法について
- マイクロ命令の実行時間分布に基づく最適マシンサイクル時間の決定法
- 大形計算機における保全性設計
- KEIO-TOSBAC タイムシェアリシグシステム 入出力制御とスーパーバイザ
- B-2. 動的なFORMAT指定