问题标签 [tree-search]

I try to summarize ALL paths though a tree that expands every level between 1 and 10 times from the root to the lowest children. My function walks recursive to all children but I have the problem that when I try to make a List of the nodes and do this lists in a list, I become a List of a List of a List ... of a List. I think my problem is the combining step And I tried to make a pattern matching method but the method that should compare the lists when it becomes a lists of lists and should make new lists and compare them if it get's just one way( meets a list with the nodes and not a list with lists) doesn't work.

我有一个树状结构。我可以得到几条连接在一起并组成树的线。线由起点和终点组成。这是来自 XML 格式的树的一些示例数据。

这是树的图形表示：

我需要做的是提取这棵树上的叶子和连接点，如图所示：

我想找到一个关于复杂性和时间的优化算法来完成这项任务。

以下内容未能返回正确的子节点，即使它实际上是在树的更深处找到子节点。它似乎在找到孩子后放弃了它，继续搜索树的其余部分。

我使用以下代码对其进行了测试：

但是，控制台会输出false两次，即使它应该是true. 5即使我在树中添加了一个，也找不到带有 键的孩子。

实现目标状态的一种方法是“在最左边的空列中的任何方格中添加一个皇后，这样它就不会受到任何其他皇后的攻击”。这种方法的状态空间为 2057（也想知道如何计算这个？）

如果我使用深度优先搜索算法（我认为这是最合适的算法），时间复杂度是多少？空间复杂度如何？

我很困惑，因为搜索树的早午餐在深入时大大减少。O(8**8) 对于时间复杂度来说看起来太高了，即使在最坏的情况下也是如此。

谢谢

兼容启发式（h）是具有以下条件的启发式：

h(n) <= c(n,a,n') + h(n')

****************************************************

可接受的启发式（h）是具有以下条件的启发式：

0 <= h(n) <= h*(n)

nh*(n) 是节点到节点的实际距离goal

如果启发式是兼容的，如何证明它是可接受的？

非常感谢。

我必须组合计算一项任务的所有可能情况。我想为此制作一棵树。有几个工作，每个工作都有几个子工作。有很多代理可以做这些工作。假设 Job1 Subjob1 可以由 Agent 1 或 2 完成，那么 Job 1 Sub Job2 将由任一代理完成。然后将启动 Job 2。等等。由于节点是不同的，并且子节点的数量也在不同的级别上发生变化，我的问题是：

1. 实现相同的最佳数据结构是什么？

2. 使用您推荐的数据结构遍历树的最佳方法是什么？

请提供具体的 C++/Java 示例或网络资源，而不仅仅是抽象的建议，因为我在编码方面是绿色的。

编辑：

请参阅我想到的树的流程图。

这是我的第一个问题，所以我希望我不会一次扔太多东西。我正在为吸尘器世界问题实施四种不同的算法。到目前为止，我制作了四个不同的工作 .py 文件，但我想我会让它变得更漂亮，因为重复了很多代码，并在一个具有良好类层次结构的文件中实现它们。所以起初我有一个 Node 类，它看起来有点像这样，并且对于每种算法（广度优先、A*、贪婪和随机）都有所不同：

现在我正在尝试使用 super() 函数来定义一个名为 NodeStar 的 Node 子类（用于 A* 实现）：

其中'self.heur'、'self.funH()'和'self.prior'是Node类没有的属性和函数。此代码不起作用。我收到一个错误：

（侧面的概念：）我不知道为什么我必须在 super() 函数中使用参数，即使我在我的计算机上安装了 python 3.4.3（我在 Sublime Text 3 中使用 Anaconda 工作）

我发现问题与 TreeSearch 函数有关，其中在边缘的第一个节点上调用了 expand() 函数。

但我主要关心的是——这是一个好的方向吗？如果是这样，我应该如何使用 super() 函数？例如，如果我需要相同的方法但返回不同的返回值，我能找到 super() 有用吗？或者，在这种情况下，我应该覆盖整个事情吗？或者我是否应该尝试在 Node 类中创建一些布尔属性来更改 Node 的类型，而不是覆盖方法（不会节省很多代码）？

我希望这不会太长。将非常感谢任何想法和想法

我不确定这个问题是否应该放在 stackoverflow 或 cs.stackexchange.com 上，所以如果我应该移动它，请告诉我。

我试图找到蒙特卡洛树搜索（MCTS）的时间复杂度。谷歌搜索没有帮助，所以我想看看我自己计算了多远。

它为n迭代或在时间用完之前执行四个步骤。所以我们会有

O(n*(选择+扩展+模拟+反向传播))

扩展只是将一个子节点添加到当前选定的节点。假设您没有使用单链表或类似的东西来存储树的孩子，这可能会在恒定时间内发生，所以我们可以排除它：

O(n*(选择+模拟+反向传播))

给定分支因子b和t树中的节点总数，我假设选择阶段在 O(b*log _b t) 中运行，因为树的深度是 log _b t，并且在每个深度，我们去超过b个孩子。

所以我们的时间复杂度变成

O(n*(b*log _b t+模拟+反向传播))

反向传播所花费的时间也与树的深度成正比，因此变为：

O(n*(b*log _b t+模拟+b*log _b t))

但现在我不确定如何将模拟阶段添加到此。

我在 Python 中实现了 Bresenham 的线算法，用于识别网格世界的网格单元格列表之间的网格占用（比如 [(1,1), (3,2),(5,6),(8,4 ）在一个 10X10 的网格世界中，有一些被占用的网格），然后应用视线算法检查我是否可以跳过任何顶点列表以减少总距离。

但是我怎样才能为基于图形的搜索做视线？我想知道如何表示树/图形节点，就像我以坐标形式 (x,y) 表示网格单元一样？任何建议/想法都将受到高度赞赏。

im working on minimax algoritm now, i have a problem to compare each node and cant return the best node. once i can compare it, it still choose the bottom of the node, can someone help me to fix my codes ?

here is my codes: