发帖
雷达卡
摘要翻译：
启发式算法在人工智能的各个领域都是减少搜索工作量的重要工具。为了有效，一个启发式必须是高效的计算，以及为搜索算法提供有用的信息。然而，一些著名的启发式算法在减少回溯方面做得很好，它们太重了，以至于在搜索算法中部署它们的收益可能会被它们的开销所抵消。我们以CSP回溯搜索为例，提出了一种合理的元化方法来决定何时部署启发式。特别地，采用了一种信息值方法来自适应地部署求解计数估计启发式来进行值排序。实验结果表明，所提出的机制确实成功地平衡了减少回溯和启发式计算开销之间的折衷，从而显著地减少了总体搜索时间。
---
英文标题：
《Rational Deployment of CSP Heuristics》
---
作者：
David Tolpin, Solomon Eyal Shimony
---
最新提交年份：
2011
---
分类信息：
一级分类：Computer Science 计算机科学
二级分类：Artificial Intelligence 人工智能
分类描述：Covers all areas of AI except Vision, Robotics, Machine Learning, Multiagent Systems, and Computation and Language (Natural Language Processing), which have separate subject areas. In particular, includes Expert Systems, Theorem Proving (although this may overlap with Logic in Computer Science), Knowledge Representation, Planning, and Uncertainty in AI. Roughly includes material in ACM Subject Classes I.2.0, I.2.1, I.2.3, I.2.4, I.2.8, and I.2.11.
涵盖了人工智能的所有领域，除了视觉、机器人、机器学习、多智能体系统以及计算和语言（自然语言处理），这些领域有独立的学科领域。特别地，包括专家系统，定理证明（尽管这可能与计算机科学中的逻辑重叠），知识表示，规划，和人工智能中的不确定性。大致包括ACM学科类I.2.0、I.2.1、I.2.3、I.2.4、I.2.8和I.2.11中的材料。
--
---
英文摘要：
Heuristics are crucial tools in decreasing search effort in varied fields of AI. In order to be effective, a heuristic must be efficient to compute, as well as provide useful information to the search algorithm. However, some well-known heuristics which do well in reducing backtracking are so heavy that the gain of deploying them in a search algorithm might be outweighed by their overhead. We propose a rational metareasoning approach to decide when to deploy heuristics, using CSP backtracking search as a case study. In particular, a value of information approach is taken to adaptive deployment of solution-count estimation heuristics for value ordering. Empirical results show that indeed the proposed mechanism successfully balances the tradeoff between decreasing backtracking and heuristic computational overhead, resulting in a significant overall search time reduction.
---
PDF链接：
https://arxiv.org/pdf/1104.1924
京公网安备 11010802022788号
