組合せ問題の並列処理のための組合せ全数生成
スポンサーリンク
概要
- 論文の詳細を見る
n個の要素からr個を選択する組合せの全数をm台のプロセッサで並列処理するためのアルゴリズムを論じる. 具体的には, 従来からある辞書式順序の概念を拡張した辞書式階差順序の概念を提案し, これに基づいて組合せ全数並列生成アルゴリズムを構成する. n=mの場合について, 辞書式階差順序により構成したn並列処理アルゴリズムにより, 同時刻における各要素へのアクセス頻度を一様にできることを示す. また, n≠mの場合について, n並列アルゴリズムの出力を機械的に順に割り付けることにより, 同時刻における同一要素へのアクセス頻度の最大値を, ほぼrm/nに保つことができることを示す. 更に, n=mの場合について, 組合せの生成効率と要素数/選択数の関係を分析する. 最後に, 提案手法の並列処理における意義を辞書式順序との比較で論じる.
- 社団法人電子情報通信学会の論文
- 1997-01-25
著者
関連論文
- 不変量地図による3次元物体記述と物体認識
- インバリアントマップを用いたロバストな物体認識
- 可変フィルタによるハフ変換の高精度化
- 組合せ問題の並列処理のための組合せ全数生成
- 単眼視姿勢推定における基本問題の計量的可解性判定
- 基本要素の段階的対応付けによる単眼視物体姿勢推定
- 既知構造の単眼視姿勢推定における基本問題
- International Conference on Computer Vision (ICCV'93)
- 単眼視回転推定に関する木構造基本問題の統一的解法
- 線分対の中心投影とその逆変換
- 金谷健一 著, "画像理解 : 3次元認識の数理", 森北出版, A5判, 210p., \2,980 (消費税込み), 1990
- 単眼視画像からの3次元情報復元 : 中心投影の逆問題とその解法
- n球包含問題の近似解法
- CG専用計算機SIGHTによる細胞分裂アニメーション : 医用画像と画像一般 : 画像処理・画像応用
- CG専用計算機SIGHT-2を用いたHDTVアニメーションシステム
- CG計算機SIGHTの性能解析
- CG計算機SIGHTの性能評価
- 3次元ベクトル演算の並列実行に関する考察
- 動的部分木を用いた光線追跡法 - そのアルゴリズムと高速化効果の評価 -
- 3次元ベクトル演算の並列実行に関する考察
- 3次元ベクトル演算の並列実行に関する考察
- コンピュータグラフィックス用プロセッサの動向 (コンピュータグラフィックス)
- 81-33 VLSI性能からみたバンヤン(Banyan)ネットワークとクロスバネットワークの比較評価
- 81-19 シミュレーションによるデータフロー計算機の性能評価
- 78-10 水平型マイクロプログラミングの最適化について