文献

J-GLOBAL ID：201802235071626947   整理番号：18A1589031

AND-ORツリー上の独立分布に対する非深さ優先探索【JST・京大機械翻訳】

Non-depth-first search against independent distributions on an AND-OR tree

著者 (1件)： Suzuki Toshio (Department of Mathematical Sciences, Tokyo Metropolitan University, Minami-Ohsawa, Hachioji, Tokyo 192-0397, Japan)
資料名： Information Processing Letters  (Information Processing Letters)
巻： 139  ページ： 13-17  発行年： 2018年 
JST資料番号： E0513A  ISSN： 0020-0190  資料種別： 逐次刊行物 (A)
記事区分： 短報  発行国： オランダ (NLD)  言語： 英語 (EN)

抄録/ポイント： SuzukiとNiida(2015)は,AND-ORツリー上の独立分布(ID)に関する以下の結果を示した。そこでは,それらは深さ第一アルゴリズムのみを考慮した。(1)正の実数数r<1が与えられ,I(r)が0を持つ根の確率がrであるようなすべてのIDのクラスを示す。もし,I(r)のメンバーの中で,dは最良アルゴリズムのコストの最大値であり,次にdは独立で同一の分布(IID)である。(2)I(r)の代わりにすべてのIDのセットに対して上記のものと同じである。非深さ第一アルゴリズムが考慮される場合,(1)と(2)の対応物は上記の研究で開かれている。Pengら(2017)は,(1)と(2)を多分岐木に拡張した。(2)それらは,値0を持つ根の確率が0も1でもないというIDに関する付加的仮説を与えた。著者らは,Suzuki-Niidaの2つの質問に対する肯定的な答えを与えた。証明の鍵は,IDがIDの間の平衡を達成するならば,dは最初に深さである最適アルゴリズムを持つことである。さらに,著者らは,非深さ第一アルゴリズムが考慮される場合に,Pengらの定理3を拡張した。Copyright 2018 Elsevier B.V., Amsterdam. All rights reserved. Translated from English into Japanese by JST.【JST・京大機械翻訳】

シソーラス用語： 実数 ,  計算量 ,  *アルゴリズム
準シソーラス用語： 最適アルゴリズム ,  *深さ優先探索 , 【Automatic Indexing@JST】

著者キーワード (5件)： 非深さ優先アルゴリズム ,  独立分布 ,  多分岐ツリー ,  計算の複雑さ ,  アルゴリズムの解析

分類 (2件)： 人工知能  (JE08000Z) ,  ゲーム理論  (KA03060T)

タイトルに関連する用語 (2件)： 分布 ,  深さ優先探索