我有一个关于光束搜索算法的问题。

假设n = 2(我们将从每个节点扩展的节点数)。因此,在开始时,我们只有根,我们从中扩展了2个节点。现在,从这两个节点开始,我们再扩展两个。因此,目前,我们有4个叶子。我们将继续这样直到找到答案。

这是光束搜索的原理吗?它是否仅扩展每个节点的n = 2,还是始终保留2个叶节点?

我曾经以为n = 2意味着每个节点最多应有2个事件节点,而不是整个树上有2个事件节点。

最佳答案

"standard" beam search algorithm中,在每个步骤中,您当前“了解”的节点总数是有限的-而不是您将从每个节点跟随的节点数。

具体来说,如果使用n = 2,则表示“光束”的大小始终为2。因此,最初,您从一个节点开始,然后发现从该节点可到达的所有节点,但丢弃两个节点之外的所有节点,并使用2个节点完成步骤1。在第2步中,您有两个节点,您将同时展开两个节点,并再次丢弃所有节点,但恰好是2个节点(总计,而不是每个节点!)。在接下来的步骤中,类似地,您将在每个步骤之后保留2个节点。

通常,通过一些启发式函数来选择要保留的节点,该启发式函数会评估哪个节点最接近目标。

请注意,波束搜索算法既不完整(即,如果存在,则可能找不到解决方案),也不是最优的(即,可能找不到最佳解决方案)。看到此问题的最佳方法是见证n = 1时,它基本上可以简化为best-first-search

关于algorithm - 光束搜索算法中的光束大小代表什么?,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/22273119/

10-09 20:40