ある選択問題の並列比較回数について

スポンサーリンク

概要

• 論文の詳細を見る

• 本稿は,与えられた全順序集合において大きい方から上位の要素を指定された個数だけ見つける選択問題をとりあげ,並列比較計算モデルにおける計算量を調べる.U(n,t)はn個の要素の中から上位のt個の要素を見つけるための(最悪の場合)必要十分な並列比較(ラウンド)の回数とする.まず小さいn(n≤16)に対するU(n,t)の正確な比較回数を示す.この結果は,ゲーム探索のプログラムにより総当たり探索を行うことによる.次に,新しいアルゴリズムを具体的に示すことにより,一般のn,tに対するU(n,t)の新しい上界式を証明する.最後に,本稿の上界式と下界を表す一般式をあわせることにより,無限個のnに対するU(n,t)の正確な値を決定する。

• 一般社団法人情報処理学会の論文
• 2002-06-15

著者

• 野下 浩平

  電気通信大学電気通信学部情報工学科

• 佐滕 信弘

  電気通信大学情報工学科:(現)株式会社アイザック

• 野下 浩平

  電気通信大学情報工学専攻

• 佐藤 信弘

  電気通信大学情報工学科:(現)株式会社アイザック

関連論文

• 生成順序の保存に基づくコピー方式世代管理の一方法
• 並列ゲーム木探索のための分散共有ハッシュ法の評価 (コンピュータグラフィクスの新展開)
• ゲーム木の並列探索のための分散共有ハッシュ機構の設計と実現(並列処理)
• ゲーム木の並列探索のための分散共有ハッシュ機構の設計と実現
• ゲーム木の並列探索のための分散的実行管理機構
• ゲーム木の並列探索のための分散的実行管理機構の設計と実現
• 長い可変長文字列の挿入操作に関する一考察
• ゲームHexにおける必勝手順の検証プログラム
• ゲームHexにおける必勝手順の検証プログラム
• ある選択問題の並列比較回数について
• 並列ゲーム木探索のための分散共有ハッシュ法の評価
• 対局盤面と解説盤面の認識結果の統合による囲碁対局テレビ番組からの対局棋譜生成(文書・文字メディアの認識・理解, 一般)
• 対局盤面と解説盤面の認識結果の統合による囲碁対局テレビ番組からの対局棋譜生成(文書・文字メディアの認識・理解, 一般)
• 対局盤面と解説盤面の認識結果の統合による囲碁対局テレビ番組からの対局棋譜生成
• 対局盤面と解説盤面の認識結果の統合による囲碁対局テレビ番組からの対局棋譜生成
• P. Naur (Ed.) : Revised Report on the Algorithmic Language ALGOL 60(20世紀の名著名論)
• 囲碁対局テレビ番組からの棋譜自動生成システム
• ゲームの解手順の一般化とある詰将棋の数え上げ
• 反復深化探索に基づく協力詰将棋の解法
• 反復深化探索に基く協力詰将棋の解法
• PCクラスタを用いたWWWからの高速画像収集システム
• 非常に手数の長い詰将棋問題を解くアルゴリズムについて
• 詰将棋を解くプログラムの進歩 (「ゲームプログラミング」)
• ゲーム木の並列探索のための分散的実行管理機構
• ゲーム木の並列探索のための分散的実行管理機構
• 最短経路アルゴリズムの平均比較回数について (実験整数論および組合せ理論と計算機)
• On Bounds of the Number of Comparisons to Select the t-th Largest of n Elements (計算機によるパズル・ゲームの研究)
• 詰将棋を速く解く2つのプログラムとその評価
• 生成順序の保存に基づくコピー方式世代管理法
• 生成順序を保存するコピー方式ガーベジコレクションについて
• 基本データ構造とアルゴリズム (データ構造)
• 9. セレクション法 (アルゴリズムの最近の動向)
• バックトラック法の実現について (数学的ソフトウェアの評価)
• TetrahexとTrihexによる'Hexagon'の詰合せ (計算機によるゲーム・パズルの具体化の検討)
• CH. Lindsey,S.G.van der Meulen: Informnal Introduction to ALGOL 68,North-Holland Publishing company,Amsterdam・London.368p.(1971).
• 69-15 計算に必要な時間とテープ量の関係

もっと見る 閉じる

スポンサーリンク