The Wayback Machine - https://web.archive.org/web/20221028225633/https://baike.sogou.com/kexue/d10187.htm

集束搜索

编辑

在计算机科学中，集束搜索是一种启发式搜索算法，它通过扩展有限集合中最有希望的节点来探索图。集束搜索是最佳优先搜索的优化，降低了对内存的要求。最佳优先搜索是一种图形搜索，它根据一些启发式规则对所有部分解(状态)进行排序。但是在集束搜索中，只保留预定数量的最佳局部解作为候选。[1] 因此，这是一个贪心算法。

“集束搜索”一词是由卡耐基梅隆大学的雷伊·雷蒂于1977年创造的。[2]

1 细节编辑

集束搜索使用广度优先搜索来构建其搜索树。在树的每一层，它生成当前层状态的所有后继，按照启发式成本的递增顺序对它们进行排序。[3] 然而，它只存储预定的数量，  每一级的最佳状态(称为束宽度)。接下来只扩展那些状态。集束宽度越大，修剪的状态越少。在无限集束宽度的情况下，不会修剪任何状态，集束搜索与广度优先搜索相同。集束宽度限制了执行搜索所需的内存。由于目标状态有可能被删减，集束搜索牺牲了完整性(如果存在解决方案，保证算法将以解决方案结束)。集束搜索不是最佳的(也就是说，不能保证它会找到最佳的解决方案)。

通常，集束搜索会返回找到的第一个解决方案。机器翻译的集束搜索是不同的情况：一旦达到配置的最大搜索深度(即翻译长度)，算法将评估在不同深度搜索期间找到的解，并返回最佳解(具有最高概率的解)。

集束宽度可以是固定的，也可以是可变的。一种使用可变束宽度的方法从最小宽度开始。如果没有找到解决方案，束宽度增加并重复该过程。[4]

2 使用编辑

集束搜索最常用于在内存不足以存储整个搜索树的大型系统中保持易处理性。[5]例如，它被用在许多机器翻译系统中。[6] 为了选择最好的翻译，每个部分都经过处理，出现了许多不同的翻译方法。根据句子结构，最好的翻译被保留，其余的被丢弃。然后，译者根据给定的标准评估译文，选择最符合目标的译文。集束搜索的第一次使用是1976年被用在卡内基·梅隆大学的哈佩语音识别系统中。[7]

3 变体编辑

集束搜索是通过将其与深度优先搜索相结合变得完备，从而产生集束堆栈搜索[8] 和深度优先集束搜索，[5] 并且具有有限差异搜索，[9] 从而产生使用有限差异回溯(BROWS)的集束搜索。[5] 产生的搜索算法是任何时候都可以快速找到好的但可能是次优解的算法，类似集束搜索，然后回溯并继续找到改进的解，直到收敛到最优解。

在局部搜索的上下文中，我们将局部集束搜索称为一种特定算法，   它一开始选择随机选择贝塔个生成状态的然后，对于搜索树的每一层，它始终考虑当前所有可能后继者中的新状态，   直到达到目标。[10][11]

因为局部集束搜索通常以局部最大值结束，所以通常的解决方案是再随机选择β个状态   随机状态，概率取决于状态的启发式评估。这种搜索被称为随机集束搜索。[12]

其他变体是可变集束搜索和恢复集束搜索。[11]

参考文献

  • [1]

    ^"FOLDOC - Computing Dictionary". foldoc.org. Retrieved 2016-04-11..

  • [2]

    ^Reddy, D. Raj. "Speech Understanding Systems: A Summary of Results of the Five-Year Research Effort. Department of Computer Science.", 1977..

  • [3]

    ^"BRITISH MUSEUM SEARCH". bradley.bradley.edu. Retrieved 2016-04-11..

  • [4]

    ^Norvig, Peter (1992-01-01). Paradigms of Artificial Intelligence Programming: Case Studies in Common LISP (in 英语). Morgan Kaufmann. ISBN 9781558601918..

  • [5]

    ^Furcy, David. Koenig, Sven. "Limited Discrepancy Beam Search". 2005. "Archived copy" (PDF). Archived from the original (PDF) on 2008-05-16. Retrieved 2007-12-22.CS1 maint: Archived copy as title (link).

  • [6]

    ^Tillmann, Christoph. Ney, Hermann. "Word Reordering and a Dynamic Programming Beam Search Algorithm for Statistical Machine Translation". "Archived copy" (PDF). Archived from the original (PDF) on 2006-06-18. Retrieved 2007-12-22.CS1 maint: Archived copy as title (link).

  • [7]

    ^Lowerre, Bruce. "The Harpy Speech Recognition System", Ph.D. thesis, Carnegie Mellon University, 1976.

  • [8]

    ^Zhou, Rong. Hansen, Eric. "Beam-Stack Search: Integrating Backtracking with Beam Search". 2005. http://www.aaai.org/Library/ICAPS/2005/icaps05-010.php.

  • [9]

    ^CiteSeerX: 10.1.1.34.2426.

  • [10]

    ^Svetlana Lazebnik. "Local search algorithms" (PDF). University of North Carolina at Chapel Hill, Department of Computer Science. p. 15. Archived (PDF) from the original on 2011-07-05..

  • [11]

    ^Pushpak Bhattacharyya. "Beam Search". Indian Institute of Technology Bombay, Department of Computer Science and Engineering (CSE). pp. 39–40. Archived from the original on 2018-11-21..

  • [12]

    ^James Parker (2017-09-28). "Local Search" (PDF). University of Minnesota. p. 17. Archived (PDF) from the original on 2017-10-13..

阅读 93
版本记录

  • 暂无