「おねえさんの問題」の最先端 -YouTube動画と世界記録-
スポンサーリンク
概要
- 論文の詳細を見る
「おねえさんの問題」と呼ばれる格子グラフ上の経路数え上げ問題が,アルゴリズムの専門家のみならず,情報処理関連の研究者・技術者の間でも広く注目を集めている.本稿では,まず「おねえさんの問題」という名称の由来について述べ,この問題を効率よく解くためのデータ構造「ZDD」とKnuth のZDD 構築アルゴリズムについて簡単に解説する.次に,この問題が知られるきっかけになった日本科学未来館における研究成果展示とYouTube 動画の反響について振り返り,最近達成された世界記録の状況について述べる.最後に,この問題が高速に解けることで今後どのような応用が期待できるかを展望する.
- 2013-10-15
著者
関連論文
- BS-5-5 漏洩者の特定と配信停止が可能なマルチキャスト配信方式(BS-5. ネットワークサービスのセキュリティ技術の展開,シンポジウムセッション)
- B-7-4 ネットワークによるフロー切り替えを行うマルチキャスト電子透かし方式の検討(B-7.情報ネットワーク,一般講演)
- B-7-31 トラヒックの平滑化とFECによる講義ノート映像品質の改善(B-7.情報ネットワーク, 通信2)
- Flexcastを用いた講義ノート多地点同報配信システムの検討(ブロードバンドサービス, CDN/P2P/Gridなどのオーバレイネットワーキング技術及び一般)
- FlexcastとJavaAppletに基づくプログラマブルな多地点同報配信アプリケーションの実装法(ブロードバンドサービス, CDN/P2P/Gridなどのオーバレイネットワーキング技術及び一般)
- B-7-73 MulticastVNCを用いた講義ノート配信システムのトラヒック特性評価(B-7. 情報ネットワーク, 通信2)
- ベイジアンネットワークと離散構造処理系(ベイジアンネットワークの最先端)
- 5.メディア系異分野共同研究プロジェクト(北の国から明日のICTに架ける橋,知の創出を支える次世代IT基盤技術-北海道大学グローバルCOEプログラムと北海道内情報通信系研究グループの活動-)
- D-4-18 高速ストリーム処理のための文字列パターン照合手法とそのFPGA設計(D-4. データ工学,一般セッション)
- D-1-7 並列ビット分配にもとづいた効率的な正規表現照合アルゴリズム(D-1.コンピュテーション,一般セッション)
- BDD/ZDDを用いたペントミノパズルの解の列挙
- 非巡回正規表現に対する効率的なパターン照合
- eラーニングと遠隔FPGAの連携による異分野共同研究環境の開発(ネットワーク,FPGA応用及び一般)
- eラーニングと遠隔FPGAの連携による異分野共同研究環境の開発(ネットワーク,FPGA応用及び一般)
- eラーニングと遠隔FPGAの連携による異分野共同研究環境の開発(ネットワーク,FPGA応用及び一般)
- 命題論理に基づく確率モデルのための二部決定グラフと順序符号化を用いた効率的なEMアルゴリズム(一般講演(構造学習・ベイジアンネット・確率推論),機械学習とその応用)
- 6ZK-10 二分決定グラフを用いた数独パズルの解探索と列挙(情報爆発時代におけるストリームデータと実世界情報処理,学生セッション,「情報爆発」時代に向けた新しいIT基盤技術)
- 3ZP-5 ZDDを用いた立体ペントミノパズルの解の列挙(情報爆発時代におけるデータマイニング・アルゴリズム,学生セッション,「情報爆発」時代に向けた新IT基盤技術,情報処理学会創立50周年記念(第72回)全国大会)
- 効率良い正規表現照合のための並列ビット分配にもとづいたハードウェア指向アルゴリズム(アプリケーション2,FPGA応用及び一般)
- 効率良い正規表現照合のための並列ビット分配にもとついたハードウェア指向アルゴリズム(アプリケーション2,FPGA応用及び一般)
- 効率良い正規表現照合のための並列ビット分配にもとづいたハードウェア指向アルゴリズム(アプリケーション2,FPGA応用及び一般)
- 2.情報爆発時代のための新しい超高速アルゴリズム(パートI:情報爆発時代における新しい基盤技術,情報爆発時代におけるわくわくするITの創出を目指して)
- ゼロサプレス型二分決定グラフを用いたトランザクションデータベースの効率的解析手法(データマイニング,データ工学論文)
- F-024 ベイジアンネットワークを表現するZDDからの高速計算プログラムの自動生成とその評価(F分野:人工知能・ゲーム,一般論文)
- 頻出パターンマイニングのためのゼロサプレス型BDDの変数順序付け方法とその評価(データマイニング,データ工学論文)
- F-011 頻出パタンマイニングのためのゼロサプレス型BDDの変数順序付け方法の高速化の検討(F分野:人工知能・ゲーム)
- F_019 データベース解析のためのゼロサプレス型二分決定グラフの簡単化について(F分野:人工知能・ゲーム)
- ゼロサプレス型二分決定グラフによる圧縮と知識発見(テーマ,膨大なデータから学ぶもの)
- ゼロサプレス型二分決定グラフによる圧縮と知識発見(テーマ,膨大なデータから学ぶもの)
- F-013 ゼロサプレス型BDDを用いた無順序n-gram表現法の性能評価(F分野:人工知能・ゲーム)
- F-020 コルモゴロフ複雑性に基づく画像圧縮と分類に関する実験と考察(人工知能・ゲーム,一般論文)
- F-012 頻出パタン集合を表現する二分決定グラフの変数順序改善法に関する実験と考察(F分野:人工知能・ゲーム)
- D-009 ZDDを用いた頻出パタン演算によるWebテキストデータからの知識発見とその評価(D分野:データベース,一般論文)
- F-061 ベイジアンネットワークを表現するZDDの初期変数順序付け方法の改良(人工知能・ゲーム,一般論文)
- D-031 頻出パタン抽出アルゴリズム「LCM over ZDDs」の変数順序付けの影響に関する考察(データベース,一般論文)
- F-050 ベイジアンネットワークを表現するゼロサプレス型BDDの変数順序付けに関する実験と考察(人工知能・ゲーム,一般論文)
- ZDD によるパスの列挙 (計算機科学とアルゴリズムの数理的基礎とその応用)
- ZDDを用いたパスの列挙とその性能評価
- D-4-3 共起成分の含意関係に基づく文献データベースからの共著関係の抽出(D-4. データ工学,一般セッション)
- πDD:順列集合を演算処理する二分決定グラフ
- 劣モジュラ性を用いた特徴集合列挙(離散系と機械学習,テキスト・Webマイニング,一般)
- 逆順の系列集合を表すSeqBDDの構築
- 二分決定グラフ(BDD)を活用したデータマイニング・知識発見技術の最近の話題(「自動化:推論,発見,学習,データマイニング」及び一般)
- データベースの頻出アイテム集合を表すゼロサプレス型BDDの変数順序付けの理論的考察
- VSOP: ゼロサプレス型BDDに基づく「重み付き積和集合」計算プログラム
- AI-1-5 大規模な離散構造データを扱うためのGPU利用法の検討(AI-1.GPUを用いた高速化技術とそのVLSI設計への応用,依頼シンポジウム,ソサイエティ企画)
- BS-1-2 順列集合を操作する効率的なデータ構造とアルゴリズムの研究について(BS-1. 学生による研究室交流会,シンポジウムセッション)
- BS-1-2 順列集合を操作する効率的なデータ構造とアルゴリズムの研究について(BS-1. 学生による研究室交流会,シンポジウムセッション)
- ERATO湊離散構造処理系プロジェクトの概要とシステム設計分野の研究について(FPGA応用)
- 東日本大震災での短縮URLによるサーバ負荷分散とアクセス分析(IPv6ネットワーク,フォトニックネットワーク,新世代・次世代ネットワーク及び一般)
- 高速なパスの列挙アルゴリズムを用いたネットワークの信頼性評価(IPv6ネットワーク,フォトニックネットワーク,新世代・次世代ネットワーク及び一般)
- ERATO湊離散構造処理系プロジェクトの概要と最近の研究状況について(IPv6ネットワーク,フォトニックネットワーク,新世代・次世代ネットワーク及び一般)
- 5.ZDDを用いた新たな列挙手法(広がる列挙の技術-列挙による問題解決アプローチ-)
- DK-2-3 フロンティア法の電力網構成制御への応用(DK-2.第3回ERATO湊離散構造処理系シンポジウム-グラフ列挙索引化アルゴリズムの新展開-,ソサイエティ特別企画,ソサイエティ企画)
- DK-2-3 フロンティア法の電力網構成制御への応用(DK-2.第3回ERATO湊離散構造処理系シンポジウム-グラフ列挙索引化アルゴリズムの新展開-,ソサイエティ特別企画,ソサイエティ企画)
- BDD/ZDDの技法と離散構造処理系(離散構造処理系-知能情報処理を支えるアルゴリズムの技法)
- DK-2-2 フロンティア法の種々のリンクパズル問題への応用(DK-2.第3回ERATO湊離散構造処理系シンポジウム-グラフ列挙索引化アルゴリズムの新展開-,ソサイエティ特別企画,ソサイエティ企画)
- DK-2-1 フロンティア法 : ZDDを用いた極めて高速なグラフ列挙索引化アルゴリズム(DK-2.第3回ERATO湊離散構造処理系シンポジウム-グラフ列挙索引化アルゴリズムの新展開-,ソサイエティ特別企画,ソサイエティ企画)
- DK-2-2 フロンティア法の種々のリンクパズル問題への応用(DK-2.第3回ERATO湊離散構造処理系シンポジウム-グラフ列挙索引化アルゴリズムの新展開-,ソサイエティ特別企画,ソサイエティ企画)
- DK-2-1 フロンティア法 : ZDDを用いた極めて高速なグラフ列挙索引化アルゴリズム(DK-2.第3回ERATO湊離散構造処理系シンポジウム-グラフ列挙索引化アルゴリズムの新展開-,ソサイエティ特別企画,ソサイエティ企画)
- DS-1-13 πDDのConjugacy Class計算への適用とその性能評価(DS-1.COMP学生シンポジウム,シンポジウムセッション)
- DS-1-14 πDDの順列集合演算を用いたパンケーキ整列問題の解析法(DS-1.COMP学生シンポジウム,シンポジウムセッション)
- 種々のリンクパズルへの応用(BDD/ZDDを用いた新しい列挙索引化技法(フロンティア法)とその応用)
- グラフ列挙索引化技法の種々の問題への適用(BDD/ZDDを用いた新しい列挙索引化技法(フロンティア法)とその応用)
- BDD/ZDDを用いたグラフ列挙索引化技法(BDD/ZDDを用いた新しい列挙索引化技法(フロンティア法)とその応用)
- 特集にあたって(BDD/ZDDを用いた新しい列挙索引化技法(フロンティア法)とその応用)
- 順列二分決定グラフを用いたパターン回避順列の列挙索引化
- 最小完全ハッシュ関数を用いたグリッドグラフ上の効率的なパス数え上げ
- 写像枝を用いた系列二分決定グラフ
- 写像枝を用いた系列二分決定グラフの効率化
- ゼロサプレス型二分決定グラフによる圧縮と知識発見
- 組合せ問題の解を列挙索引化するZDD構築アルゴリズムの汎用化
- 系列二分決定グラフを操作するための豊富な演算体系の構築
- 「おねえさんの問題」の最先端 -YouTube動画と世界記録-
- フロンティア法 : BDD/ZDDを用いた高速なグラフ列挙索引化の技法(新世代・次世代ネットワーク,ネットワークとシステムの仮想化,仮想化環境の管理・監視,オーバーレイ,IPv6ネットワーク,フォトニックネットワーク及び一般)
- 再帰的仕様記述を用いた組合せ列挙ZDDの効率的な構築手法(システム設計技術(1),デザインガイア2012-VLSI設計の新しい大地-)
- ERATO湊離散構造処理系プロジェクトの概要と今後の展望について(ブロードバンドアクセス,ホームネットワーク,ネットワークサービス,通信利用アプリケーション,一般)
- ゼロサプレス型二分決定グラフに基くコンパクトかつ高速な索引構造(一般)
- 1-D-4 ZDDを用いた都市の避難所割り当ての列挙(災害対策)
- グラフ列挙索引化技法の種々の問題への適用
- 種々のリンクパズルへの応用