深度优先搜索打开和关闭列表 [英] Depth first search Open and Closed list

问题描述

此刻我真的很困，我要疯了.

I am really stuck at the moment and I am going insane.

用最简单的术语来说，什么时候停止深度优先搜索的打开"和关闭"列表?

In the simplest of terms, when do you stop on Open and Closed lists with a depth first search?

您是否打开并关闭每个节点，直到没有剩余节点为止?

Do you open and close every node until there are no nodes left?

请帮助，因为我要在这里呆着

Please help because I am going doolally here

谢谢

推荐答案

打开列表可帮助您进行深度优先搜索和宽度优先搜索，以正确遍历树.逐步考虑算法.您所在的节点上有许多孩子，并且您将扩展其中一个孩子.扩展后，应该有一种机制可以恢复并继续遍历.打开列表会为您执行该操作，并告诉您实际上是下一个要扩展的节点是什么.并且该算法仅阐明了子级插入列表的顺序.

Open list helps you in both depth first and breadth first searches to traverse your tree properly. Think about algorithms step by step. You are in a node with many children and your are going to expand one of them. After expansion there should be a mechanism to get back and continue your traversal. Open list performs that for you and tells you what is actually the next node to be expand. And the algorithm only clarify the order of child insertion into the list.

和封闭列表通常可以提高算法的速度.它阻止了算法扩展预先访问的节点.也许您到达的节点 A 先前已通过另一个分支进行了扩展.这将使您能够剪切此分支并尝试其他路径.

And Closed list generally improves the speed of algorithm. It prevents the algorithm from expanding pre-visited nodes. Maybe you reach node A that was expanded previously through another branch. This will let you cut this branch and try another path.

启发式方法对于摆脱死胡同很有用.在AI算法中，通常会遇到很多浪费分支的问题.通过执行每个步骤，您可以将路径成本添加到变量中，并且当您要将扩展节点添加到打开列表中时，考虑到这样做将永远帮助您解决这些问题.否则，您将陷入陷阱，算法将挂起.

Heuristics are useful to get away from dead-end. In AI algorithms usually you are facing problems that they have many waste branches. By passing through each step you can add the path cost to a variable and when you want to add expanded nodes to your open list, considering it will help you never go through them. Otherwise, you will get into a trap and algorithm hangs.

让我用一个例子来解释更多:考虑游戏 15个拼图.您将通过算法来解决它，并且您必须检查所有可能的方法.(实际上，您将要制作一棵树).当您沿树中可能的方向移动图块时，可以将其反向移动到下一级别，对吗?因此，您将永远不会走出这种僵局，并且算法会死机.

Let me explain more with an example: Consider the game 15-puzzles. You are going to solve it through an algorithm and you have to check all possible ways. (actually you are going to make a tree). When you move a tile in a direction that would be possible in your tree to move that in reverse direction in the next level, right? So you will never get out of such dead-ends and your algorithm hangs.

这是打开"和关闭"列表的说明.您询问算法何时完成.实际上，您将重复展开并添加到打开列表" ，直到找到目标或打开列表"为空.

This was explanation of Open and Closed lists. You asked about when the algorithm finishes. Actually you will repeat the expand and add to Open list until you find your goal or Open list goes empty.

这篇关于深度优先搜索打开和关闭列表的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！