N^2-1パズルのスケールダウン解法(計算量理論とアルゴリズム論文小特集)
スポンサーリンク
概要
- 論文の詳細を見る
N^2-1パズルの最適解を求める問題は, 探索木を作り最小長さの解を発見する、問題である.この問題クラスは, NP完全に属するので, 高性能の計算機を用いても容易に解を求めることができない.我々は, 従来の方式とは全く異なる準最適解を得るための解法を提案する.我々の方式の特徴は, 探索に頼るのではなく, パズルを1サイズ小さいパズルに置き換えていく過程を機械的に繰り返すことにある.この利点としては, 探索木の生成を必要としないので, 使用するメモリと計算時間が飛躍的に節約できることである.結論として, 我々の方式が, N^2-1パズルに対し多項式時間で準最適解を求めることができることを示すと共に, 近年, 注目されている実時間探索(一定の深さの探索を繰り返しながら, 目標とする状態へ向けて探索していく方法)と比較を行い, そのような探索アルゴリズム等の性能評価に関して良い比較材料を提供できる可能性があることを示す.
- 社団法人電子情報通信学会の論文
- 1998-06-25
著者
関連論文
- 2値化とエッジ抽出による情景画像からの高精度文字列検出(画像認識,コンピュータビジョン)
- 付加情報の一般的な割当(パターン認識)
- ベクトル空間へのグラフの埋め込みによるシルエット画像認識
- 編集距離と多次元尺度構成法によるシルエット画像認識(一般セッション11)
- 編集距離と多次元尺度構成法によるシルエット画像認識(一般セッション4,三次元画像,多視点画像)
- データベースおよびクエリの拡張による文書画像検索の精度向上法 (ヒューマン情報処理)
- 多重解像度画像からの特徴抽出 (小特集 ビジョンコンピューティングにおける確率的情報処理の展開)
- 色情報とエッジ情報を用いた信号機の高速検出
- 3.多重解像度画像からの特徴抽出(ビジョンコンピューティングにおける確率的情報処理の展開)
- ディジタルペン
- 輪郭の伝搬によるCT画像からの歯の半自動形状復元(研究速報)
- 部分空間法と高速フーリエ変換を用いた傾斜文字認識 (ユーザー価値の創造・革新を追求する画像電子関連技術論文特集)
- ペン先画像からの手書き復元(研究速報)
- 認識が与える情報量 : 認識率100%まであと何ビット?(文書・文字メディアの認識・理解, 一般)
- 多項式近似に基づく高速な指定領域でのテンプレートマッチング
- 多項式近似を用いた部分空間法による高速画像探索(パターン認識)
- 多項式を用いた画像探索--多項式を用いた画像の近似と類似度の効率的計算法
- 関数を用いた認識のためのパターン表現法(一般, 顔・ジェスチャーの認識・理解)
- 重み付き最小共通スーパーグラフを用いたシルエット画像認識
- 検出容易な文字パターン生成に関する検討(テーマセッション1,複合現実感のためのパターン認識・理解)
- ペン先カメラ画像からの手書きパターンの抽出(テーマセッション1,複合現実感のためのパターン認識・理解)
- NAT法とエッジ情報を利用した情景画像中の文字列検出(テーマセッション3,複合現実感のためのパターン認識・理解)
- レイアウトに依らない平面文書画像の射影歪み補正(テーマセッション5,複合現実感のためのパターン認識・理解)
- モーフィングによる生成パターンを用いたシルエット図形認識(研究速報)
- データ埋め込みペンに関する基礎的検討
- ガンマ変換を用いた照明変動に頑健な物体検出(研究速報)
- 画像変形モデルを用いた図形の領域分割(一般,膨大なデータから学ぶもの)
- 文字認識のためのパターン認識 (特集 パターン認識の最近の動向)
- 2値化とエッジ抽出による情景画像からの高精度文字列検出
- カメラによる文字認識のためのカテゴリー情報の埋込に関する検討(画像認識,コンピュータビジョン)
- シルエット図形のパーツ分解とカテゴリー分類法(パターン認識)
- AdaBoostアルゴリズムを用いた識別手法の統合(研究速報)
- 色情報を用いた画像探索の高速化--大域的処理の導入とヒストグラム構築コストの考慮による計算量の削減
- 中心軸変換を用いたシルエット図形の構造化(画像認識,コンピュータビジョン)
- 認識が与える情報量 : 認識率100%まであと何ビット?(文書・文字メディアの認識・理解, 一般)
- ヒストグラム構築コストを考慮した高速物体検出(画像・映像処理)
- 大域的枝刈りと回転状走査による物体の高速探索(パターン認識)
- I-021 枝刈り規則の簡素化と回転状走査による高速物体検出(I.画像認識・メディア理解)
- 枝刈り可能量の予測と探索開始点の考慮による色ヒストグラムを用いた画像探索の高速化
- オブジェクト指向設計によるチベット文字認識研究の発展
- 効果的なチベット文字認識システム
- An interface for embedding online information during writing (パターン認識・メディア理解)
- 次元の縮退を利用した頑健な共分散行列の逆行列の推定法(一般セッション,パターン認識・メディア理解のための学習理論とその周辺)
- HITSアルゴリズムに基づく階層性を考慮したウェブコミュニティの抽出(データマイニング)
- トピック語の自動抽出によるウェブページ検索システム
- 孤立文字認識のための変形を許容する高速なテンプレートマッチング(画像認識,コンピュータビジョン)
- リンク構造を用いたウェブコミュニティ抽出法(情報抽出2,夏のデータベースワークショップDBWS 2006)
- リンク構造を用いたウェブコミュニティ抽出法(情報抽出)
- カラー情報と明度情報を利用した情景画像中の文字列の高精度抽出(研究速報)
- 情景画像中文字認識のための変形を許容する高速なテンプレートマッチング(一般セッション3)
- 情景画像中文字認識のための変形を許容する高速なテンプレートマッチング(一般セッション(3),CVのためのパターン認識・学習理論の新展開)
- 21世紀に向けて文字・文書メディアの認識・理解の夢と課題
- 余剰計算資源共有を行うための通信遅延を考慮したネットワークの構築
- 余剰計算資源共有を行うための通信遅延を考慮したネットワークの構築
- D-12-26 オンライン手書き行列の構造認識
- 伸縮変形隠れマルコフモデルと時系列認識への応用
- 伸縮変形隠れマルコフモデルと時系列認識への応用
- 混合非対称正規分布とその最尤推定法
- 混合修正2次識別関数による単仮説検定問題のための教師なし学習法
- 混合修正2次識別関数による単仮説検定問題のための教師なし学習法
- 伸縮変形モデルを用いた手書き文字認識
- 文字の大局的変形に関する一考察
- 多重解像度法を用いた文字認識用伸縮変形モデルの高精度化
- 複数ストローク対応型伸縮変形モデルによる平仮名認識
- データ埋め込みペン実現に向けたデータ抽出精度の検証(テーマセッション2(文字画像処理1),文字・文書の認識・理解)
- 手書きパターンへの情報埋め込みと情報抽出(テーマセッション(2),文字認識・文書理解)
- 手書きパターンへの情報埋め込みと情報抽出(テーマセッション(2), 文字認識・文書理解)
- データベースおよびクエリの拡張による文書画像検索の精度向上法(一般,顔・人物・ジェスチャ・行動)
- データ埋め込みペンの実装(テーマセッション,文字・文書の認識・理解)
- 構造情報に基づく漢字印刷文字認識
- 構造情報に基づく仮名漢字印刷文字認識の高精度化
- 構造情報に基づく英字印刷文字認識
- 文字の構造情報を活用した印刷文字認識方式
- 構造情報に基づく英字印刷文字認識
- 文字の構造情報を活用した印刷文字認識方式
- ペン先カメラ画像と紙面上特徴点を用いた手書きパターンの復元(テーマセッション,文字・文書の認識・理解)
- データベースおよびクエリの拡張による文書画像検索の精度向上法(一般,顔・人物・ジェスチャ・行動)
- 部分空間法と高速フーリエ変換を用いた傾斜文字認識
- 特徴追跡と文書画像検索を用いたカメラペンシステム(テーマセッション(デモ発表特集),文字・文書の認識・理解)
- 8パズルの高速解法
- 付加情報の誤りと誤認識率の関係(一般セッション,パターン認識・メディア理解のための学習理論とその周辺)
- 付加情報を用いるパターン認識における識別境界移動の効果 : 正規分布に従う人工サンプルを用いた場合の実験的検討
- 文書画像の事例ベース傾き補正の改良(テーマセッション1,文字・文書の認識・理解)
- 事例に基づく文書画像の回転角推定(研究速報)
- F-010 多階層のリンクを考慮したWebコミュニティの抽出(F分野:人工知能・ゲーム)
- 国際会議報告:ICPR2000とその周辺
- 余剰計算資源共有を行うための通信遅延を考慮したネットワークの構築
- B-1 オブジェクト指向設計法によるチベット活字文字認識について(専門分野知識)
- オブジェクト指向設計によるチベット文字認識について
- 木版刷チベット文献中の文字特徴抽出
- オブジェクト指向によるチベット活字文献からの文字パターン識別
- Robustness of robot programs generated by genetic programming
- 木版刷チベット文献1音節切出し法について
- 研究紹介 木版刷チベット文献の1音節文字認識のエキスパートシステム
- オブジェクト指向設計を考慮した木版刷チベット文献のイメージ文字認識
- コンピュータによるチベット文献の自動認識
- OCRによる木版刷チベット文献の自動認識について (特集 挑戦 古文書OCR)
- チベット仏教原典の自動認識に関する研究
- ディジタルカメラによる文字・文書の認識・理解
- 標本共分散行列の固有ベクトルを用いた真のマハラノビス距離の推定法(パターン認識)