集束搜索算法及其逻辑和 Python 实现

作者

读者大家好，在本文中，让我们尝试了解人工智能中使用的最有效的算法之一：集束搜索算法。

什么是束搜索算法？

波束搜索算法是最佳优先搜索算法的修改版本。它根据条件概率选择节点。波束搜索方法的每次迭代可以包括根据路径长度排序和选择的多个路径。因此，用于寻找最短或最便宜的路径。

光束搜索如何工作？

称为波束搜索的启发式搜索策略总是扩展每个级别的最佳节点的 W 数量。它逐级前进，总是从每级的顶部 W 个节点开始。束搜索使用广度优先搜索构建搜索树。它在树的每一层生成当前层状态的所有后继者，并按启发式值升序组织它们。

不过，它只考虑每个级别的 W 状态。其他节点被省略。根据节点的启发式成本，选择最佳节点。本文中的 W 指的是波束搜索的宽度。如果 B 是分支因子，则仅选择 W 个节点，因为在任何级别仅考虑 W * B 节点。随着波束宽度减小，消除的状态数量增加。如果 W = 1，则搜索将转换为爬山搜索，其中始终选择最佳后继节点。如果波束宽度不确定，则不会消除任何状态，并且波束搜索与呼吸优先搜索相同。

算法

输入：开始和目标状态

局部变量：OPEN、NODE、SUCC、W_OPEN、FOUND

输出：是或否

方法：

  • 节点=根节点：找到=假：
  • 如果 NODE 是目标节点，则 Found = true，否则查找 NODE 的 SUCC。如果有的话，及其估计成本并存储在 OPEN 列表中：
  • while（发现错误并且无法进一步进行）做
    • 对打开列表进行排序：
    • 从 OPEN 列表中选择顶部的 W 元素并将其放入 W_OPEN 列表中，并清空 OPEN 列表。
    • 对于 W_OPEN 列表中的每个节点
      • { if NODE = goal state then FOUND = true 查找 NODE 的 SUCC。如果有的话，及其估计成本并存储在 OPEN 列表中。}
    • 结束 while 循环
  • 如果 FOUND = true 则返回 Yes，否则返回 No。
  • 停止。

复杂

  • （W是波束宽度，B是任意路径的最大深度）
  • 时间复杂度：取决于启发式函数，其O(W*B)
  • 空间复杂度：由于该算法只存储搜索树中每一层的W个节点，因此其O(W*B)

在职的

下面给出了使用束搜索算法生成的搜索树，假设 W = 2 且 B = 3。在这里，根据其启发值选择彩色节点以进行进一步扩展。

波束算法

用 Python 实现集束搜索算法

这是波束搜索算法在 python 中的简单实现。我们使用Python中的NumPy模块来处理性能中使用的数组数据结构。主函数beam_search()会迭代多次以找到最短路径。该函数中传递的参数是

  • distances – 顶点之间权重值的距离
  • beta – 梁的宽度
from numpy import array
 
 
#main function
#beta here is width of beam and distances can be considered as weights.
def beam_search(distances, beta):
    #initialising some record
    paths_so_far = [[list(), 0]] 
  
     
    #traverse through the neighbouring vertices row by row.
    for idx, tier in enumerate(distances):
        if idx > 0:
            print(f'Paths kept after tier {idx-1}:')
            print(*paths_so_far, sep='\n')
        paths_at_tier = list()
         
 
        for i in range(len(paths_so_far)):
            path, distance = paths_so_far[i]
             
            # Extending the paths
            for j in range(len(tier)):
                path_extended = [path + [j], distance + tier[j]]
                paths_at_tier.append(path_extended)
                 
        paths_ordered = sorted(paths_at_tier, key=lambda element: element[1])
         
        # The best paths are saved
        paths_so_far = paths_ordered[:beta]
        print(f'\nPaths reduced to after tier {idx}: ')
        print(*paths_ordered[beta:], sep='\n')
         
    return paths_so_far
 
 
#Distance matrix
dists = [[1, 4, 6, 8],
         [5, 2, 3, 4]]
dists = array(dists)
 
# Calculating the best paths
best_paths = beam_search(dists, 2)
print('\nThe best paths:')
for beta_path in best_paths:
    print(beta_path)

输出

输出

从输出中，我们可以了解海滩搜索算法中路径选择的方法。第一次迭代（第 0 层）后，两条路径被减少或切断，两条路径被保留以供进一步扩展。这两条保留的路径被进一步迭代（第 1 层），六条路径被切断，两条最适合的路径被保留并声明为最佳路径。

比较

  • 除了鲁棒性之外，波束搜索算法在处理巨大而密集的图时保持资源有限的系统的可扩展性和效率的能力可能是其最突出的特征。
  • 波束搜索的优点是比最佳优先搜索需要更少的内存。这是因为不需要将所有后续节点存储在队列中。相反，它只选择 beta（波束宽度）方面最好的。
  • 然而，它仍然存在“最佳优先搜索”的一些缺点。首先，它是不完整的，这意味着它甚至可能无法提出解决方案。其表现不佳是第二个问题。因此，它返回的答案可能不是最好的答案。

应用——在可能有不止一种合适的解决方案的情况下，例如在机器翻译中，集束搜索算法被广泛使用。

结论

在本文中，我们学习并实现了人工智能项目中常用的集束搜索算法。