深度优先搜索与深度优先搜索贪心最佳优先搜索

Question

我想知道在什么设置下深度优先搜索（DFS）可以等于贪婪最佳优先搜索？可以吗？

Answer 1

贪婪最佳优先搜索算法根据某些标准在当前节点的直接子节点中选择一个最佳节点。

假设标准是

max(node.val)

。在这种情况下，您在每个节点上执行以下操作：

next_node = curr_node.children[0]
for node in curr_node.children:
  if node.val > next_node.val:
    next_node = node
# add next_node to path and continue searching

现在，您可以递归或迭代地实现此操作。

经典的 DFS，无论是递归实现还是迭代实现，都会尝试每条路径，这与贪婪最佳优先搜索不同，后者仅探索紧随直接最佳子级的路径。

如果您将 DFS 更改为首先查看每个直接子级，然后只查找找到的最佳子级，则它将产生与贪婪最佳优先搜索相同的结果。但如果你仔细想想，这已经不再是 DFS 了。这只是我们一开始定义的递归贪婪最佳优先搜索。

Answer 2

使用启发式

h

的贪婪最佳优先搜索相当于 DFS if

1. DFS 得到增强，在选择要扩展的节点时更喜欢具有较低

   h

   值的节点，这与可以选择任何子节点的普通版本不同。
2. 增强 DFS 无需冒泡即可到达目标节点。这意味着存在一个目标节点，这样对于从起始节点到目标节点（让我们表示

   P = {start_node, ..., goal_node}

   ）的路径上的所有节点，

   h(p_{i + 1})

   是

   p_i.

   的后代中的最小值，我们将其称为 GBFS -ADFS 等效标准。

您可以将贪婪最佳优先搜索视为增强的 DFS，而无需冒泡（无需从堆栈中弹出）。另请注意，GBFS 是不完整的（并不总是找到目标节点），而我们的增强 DFS 在给定有限分支因子和有限树高的情况下是完整的。

让我们举一个 GBFS-ADFS 等价成立的例子。

第一个示例

GBFS-ADFS 等价性不成立的示例：

第二个例子