.png){kind=icon}
返回
Probably bounded suboptimal heuristic search
.png){kind=icon}
OA
AI
DOI：10.1016/j.artint.2018.08.005.png)
.png){kind=icon}
.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
Finding an optimal solution to a search problem is often desirable, but can be too difficult in many cases. A common approach in such cases is to try to find a solution whose suboptimality is bounded, where a parameter epsilon defines how far from optimal a solution can be while still being acceptable. A scarcely studied alternative is to try to find a solution that is probably optimal, where a parameter delta defines the confidence required in the solution's optimality. This paper explores this option and introduces the concept of a probably bounded-suboptimal search (pBS search) algorithm. Such a search algorithm accepts two parameters, epsilon and delta, and outputs a solution that with probability at least 1 - delta costs at most 1 + epsilon times the optimal solution. A general algorithmic framework for pBS search algorithms is proposed. Several instances of this framework are described and analyzed theoretically and experimentally on a range of search domains. Results show that pBS search algorithms are often faster than a state-of-the-art bounded-suboptimal search algorithm. This shows in practice that finding solutions that satisfy a given suboptimality bound with high probability can be done faster than finding solutions that satisfy the same suboptimality bound with certainty. (C) 2018 Elsevier B.V. All rights reserved.
Keyword:
Artificial intelligence
Heuristic search
AI总结
对已上传原文的论文进行重点信息的提取，主要内容包括：简要概述、研究摘要、背景介绍、关键亮点、图文解析、展望与总结。
期刊
IF:
13.9
论文数:
6.1K
被引数:
1.9W
机构
引用论文
.png){kind=icon}
Does it take older adults longer than younger adults to perceptually segregate a speech target from a background masker?在感知上将语音目标与背景掩蔽器隔离开来是否需要老年人比年轻人更长的时间？
PREAI
分享收藏分享收藏
查看更多内容