区間減少ソーティングネットワークの提案
スポンサーリンク
概要
- 論文の詳細を見る
本論文では, 比較区間を減らしていく区間減少ソートというソーティングネットワークを提案し, 0-1原理と最良優先探索を用いる区間減少ソートにおいて最も比較回数が小さくなる場合を計算機上で求める方法について述べる. その結果, nを要素数としたときソーティングネットワークが正しくソートすることを検証する時間がO(1.618...^n)である方法を得た. また, 最良優先探索で効率の良いヒューリスティック評価関数を適応させることにより, 最適な区間減少ソートではバイトニックソートと大差のない比較回数で正しくソートできることが分かった.
- 社団法人情報処理学会の論文
- 1997-03-15
著者
関連論文
- 区間減少ソーティングネットワークの提案
- 自動チューニング機能付き並列数値計算ライブラリ構築の試み : 対称疎行列用の連立一次方程式ソルバを列にして
- 自動チューニング機能付き並列疎行列連立一次方程式ソルバの性能
- AND/OR木探索における証明数・反証数を用いた新しい探索法の提案とその評価