|
在搜索过程中学习不可接受的启发式方法
Learning Inadmissible Heuristics during Search |
|
| |
| 课程网址: |
http://videolectures.net/icaps2011_thayer_inadmissible/
|
| 主讲教师: |
Jordan T. Thayer
|
| 开课单位: |
新罕布什尔大学
|
| 开课时间: |
2011-07-21
|
| 课程语种: |
英语
|
| 中文简介: |
次优搜索算法通过牺牲有保证的解决方案最优性来提供更短的求解时间。虽然像A *和IDA *这样的最佳搜索算法需要可接受的启发式算法，但次优搜索算法不需要以这种方式约束其指导。以前的工作探索了使用离线培训将可接受的启发式转换为更有效的不可接受的启发式算法。在本文中，我们证明了这种转换可以在搜索期间在线执行。除了不需要训练实例和广泛的预计算外，在线方法还允许将学习的启发式方法定制为特定的问题实例。我们使用贪心最佳首次搜索和有限次优搜索来评估我们在四个不同基准域中的技术。我们发现，在线学习的启发式技术可以实现更快的搜索和更好的解决方案，同时仅依赖于任何最佳首次搜索中随时可用的信息。
|
| 课程简介: |
Suboptimal search algorithms offer shorter solving times by sacrificing guaranteed solution optimality. While optimal search algorithms like A* and IDA* require admissible heuristics, suboptimal search algorithms need not constrain their guidance in this way. Previous work has explored using off-line training to transform admissible heuristics into more effective inadmissible ones. In this paper we demonstrate that this transformation can be performed on-line, during search. In addition to not requiring training instances and extensive precomputation, an on-line approach allows the learned heuristic to be tailored to a specific problem instance. We evaluate our techniques in four different benchmark domains using both greedy best-first search and bounded suboptimal search. We find that heuristics learned on-line result in both faster search and better solutions while relying only on information readily available in any best-first search.
|
| 关 键 词: |
次优搜索算法; 在线方法; 启发式算法
|
| 课程来源: |
视频讲座网
|
| 最后编审: |
2019-04-17：lxf
|
| 阅读次数: |
94
|
|
图 书 馆