計算の複雑さとしてのエントロピー

TAKAOKA Tadao; NAKAGAWA Yuji

文献

J-GLOBAL ID：201002200834071268 整理番号：10A0950338

計算の複雑さとしてのエントロピー

Entropy as Computational Complexity

出版者サイト {{ this.onShowPLink() }} 複写サービスで全文入手 {{ this.onShowCLink("http://jdream3.com/copy/?sid=JGLOBAL&noSystem=1&documentNoArray=10A0950338&COPY=1") }}
高度な検索・分析はJDreamⅢで {{ this.onShowJLink("http://jdream3.com/lp/jglobal/index.html?docNo=10A0950338&from=J-GLOBAL&jstjournalNo=U0109A") }}

著者 (2件)： ,
資料名：
巻： 18 ページ： 227-241 (J-STAGE) 発行年： 2010年
JST資料番号： U0109A ISSN： 1882-6652 資料種別：逐次刊行物 (A)
記事区分：原著論文発行国：日本 (JPN) 言語：英語 (EN)

与えられた問題のインスタンスが部分的に解決されている場合,その情報を使用して問題を解決するための工数を最小化したい。本研究では,部分的に解決された入力データS(X)=(X1,・・・,Xk)における不確実性に対しエントロピー,H(S)の尺度を導入した。ここで,Xは全データの集合であり,各Xiはすでに解決されているデータである。Xiを繰り返しマージしてkが1になったときに終了する一般的なアルゴリズムを提案した。本研究では,ソート,最短経路,及び最小スパニングツリーの3つのサンプル問題を分析するためにエントロピー尺度を使用した。ソートに対してはXiは昇順に実行され,最小スパニングツリーに対してはXiはサブグラフに対し部分的に得られた最小スパニングツリーとして解釈される。最短パスの場合,Xiは与えられたグラフの非循環部分である。kが小さい場合,グラフはほぼ非環式とみなすことができる。エントロピー尺度H(S)は,pi=Xi/Xを確率尺度とみなすことで定義した,即ち,H(S)=-n(p1logp1+・・・+pklogpk)とし,ここで,n=X1+・・・+Xkである。本論文において,入力データS(X)をOH(S)時間でソートできること,および,mをエッジ数として,O(m H(s))の時間で最小コストのスパニングツリーを完了できることを示した。このようにして,最短経路問題をO(m H(s))の時間で解決した。時間は,一般的なクイックソート及び別の種類のほぼ非循環のグラフに対する最短経路問題の時間境界を与えることにより,最終的に分離プロセスのデュアルエントロピーを定義した。(翻訳著者抄録)

, , , , , , , , ,
, , ,

その他のシステムプログラミング

引用文献 (14件)：

1) Nakagawa, Y.: A Difficulty Estimation Method for Multidimensional Nonlinear 0-1 Knapsack Problem Using Entropy, Trans. Institute of Electronics, Communication and Information, Vol.J87-A, No.3, pp.406-408 (2004).
2) Takaoka, T.: Entropy-Measure of Disorder, Proc. CATS (Computation: Australasian Theory Symposium), pp.77-85 (1998).
3) Takaoka, T.: Partial Solution and Entropy, MFCS 2009, LNCS 5734, pp.700-711 (2009).
4) Estivill-Castro, V. and Wood, D.: A survey of adaptive sorting algorithms, ACM Computing Surveys 24, pp.441-476 (1992).
5) Knuth, D.E.: The Art of Computer Programming, Vol.3, Sorting and Searching, Reading, Mass., Addison-Wesley (1974).

前のページに戻る