著者

柳井 孝介 伊庭 斉志

出版者

一般社団法人情報処理学会

雑誌

情報処理学会研究報告. AL, アルゴリズム研究会報告 (ISSN:09196072)

巻号頁・発行日

vol.100, pp.1-8, 2005-03-17

参考文献数

11

被引用文献数

1

---

本稿ではNo Free Lunch Treorem (NFL)の別証明を与える.NFLは「どんな問題に対しても平均的に効率良く解けるような探索アルゴリズムは存在しない」ということを主張する定理であり, 探索アルゴリズムあるいは最適化法の研究に大きな影響を与えた.本稿では, より簡潔でかつ直観的な証明を与える.我々は評価関数の空間を部分集合に分割し, それぞれの部分集合ごとにパフォーマンスが得られる確率を合計する.関数空間の分割により, 定理のより深い理解が可能となり, またアルゴリズムと問題の関係が明確となる.

著者

伊藤 靖朗 ボルジン ジャシル 中野 浩嗣

出版者

一般社団法人情報処理学会

雑誌

情報処理学会研究報告. AL, アルゴリズム研究会報告 (ISSN:09196072)

巻号頁・発行日

vol.2002, no.70, pp.35-42, 2002-07-25

参考文献数

10

---

本論文では,文脈自由文法に対するCKYパージングを高速に行う入力依存回路によるFPGAへの実装を提案する.文脈自由文法Gと文字列xが与えられたときに,CKYパージングはGがxを導出するか否かを判定する.このCKYパージングは,xの長さがnのときに,O(n^3)時間で導出するかを判定するできることが知られている.任意の文脈自由文法Gが与えられたときに,その文法に対するCKYパージングを行うハードウェアのVelilog HDL記述を生成するハードウェアジェネレータを示す.生成された記述は,FPGAに実装され,任意の文字列xに対して,Gがxを導出するかを判定する.このFPGAは,特定の文法Gに対してのみパージングを行うので,入力依存ハードウェアであり,究極の高速化が可能である.このハードウェアの性能をタイミング解析により評価し,また,アルテラ社のFPGAを用いて動作確認を行った.結果として,ソフトウェアによるCKYパージングより約750倍高速であることがわかった.

著者

浅野 哲夫 セルゲイ ベレグ

出版者

一般社団法人情報処理学会

雑誌

情報処理学会研究報告. AL, アルゴリズム研究会報告 (ISSN:09196072)

巻号頁・発行日

vol.2013, no.20, pp.1-8, 2013-05-10

---

n画素からなる2値画像が与えられたとき,連結成分ごとに異なる整数ラベルを付ける問題に対して新たなアルゴリズムの枠組みを与える.O(n)の作業領域が利用できるならO(n)時間でラベル付けは可能である.ここでの問題は,実行時間を余り増やさずに作業領域を削減できるかである.本文では,省メモリのアルゴリズムを提案する.具体的には,入力画像は読み出し専用メモリで与えられるものとし,O(√n)の作業領域だけを用いてO(n log n)時間でラベル付けを行うアルゴリズムを提案する.さらに,応用についても述べる.

著者

上土井 陽子 若林 真一 吉田 典可

出版者

一般社団法人情報処理学会

雑誌

情報処理学会研究報告. AL, アルゴリズム研究会報告 (ISSN:09196072)

巻号頁・発行日

vol.48, pp.17-22, 1995-11-17

参考文献数

5

---

グラフの最小コストk分割問題は枝に正の重みを持つ無向グラフG=(V,E)の節点集合Vを互いに非連結なk個の節点集合に分割する最小コスト分割を求める問題である.この問題は巡回セールスマン問題やVLSI設計で用いられるクラスタリング問題等の組合せ問題の定式化において用いられる重要な組合せ問題の一つである.Goldschmidtらはグラフの最小コストk分割問題に対し,n=|V|とするとき,O(n^<k^2>の計算時間のアルゴリズムを提案している.本稿では最小コストk分割問題に対する多項式計算時間のアルゴリズムを提案する.提案アルゴリズムでは最大流-最小コストカットアルゴリズムをO(n^<k-1>)回適用する.

著者

玉木 久夫 土屋 裕希

出版者

一般社団法人情報処理学会

雑誌

情報処理学会研究報告. AL, アルゴリズム研究会報告 (ISSN:09196072)

巻号頁・発行日

vol.111, pp.121-128, 2007-03-09

参考文献数

15

---

平面ユークリッド距離巡回セールスマン問題に対する分割統治法アルゴリズムを提案する。このアルゴリズムは、まず与えられた点集合のドローネ三角形分割を求め、その全域閉小路を再帰的に求める。巡回路をハミルトン閉路から全域閉小路に緩和したのは解の存在を保証するためである。部分解の統合においては、部分解に属す辺とその他のドローネ辺をあわせて統合グラフを構成し、その上の最適解を線形刻み分割を用いた動的計画法により求める。このアルゴリズムの実行時間は分割の幅wを固定したとき、O(nlogn)である。