问题标签 [tree-search]

所以我为节点树实现了标准深度优先搜索，其中每个节点都封装了我正在解决的问题的状态，我还添加了下面的方法来检查我不会通过扩展一个节点来重复移动封装了我已经在之前的某个节点中检查过的状态。我的问题是：这种方法是否以某种方式改变了算法的时间或空间复杂度，或者它们仍然是 DFS O(b^m) 和 O(bm) 的典型方法（这里 b - 分支因子和 m - 最大深度）。

这是来自加州伯克利大学的AI 练习考试。

问题提出

考虑上面显示的状态空间图。A 是起始状态，G 是目标状态。每条边的成本都显示在图表上。每条边都可以双向遍历。请注意，启发式 h1 是一致的，但启发式 h2 是不一致的。

对于以下每个图搜索策略（不要回答树搜索），标记它可以返回的列出的路径中的哪一个（如果有）。请注意，对于某些搜索策略，返回的特定路径可能取决于平局行为。

搜索算法是深度优先、广度优先、统一成本、A* 与 h1 和 A* 与 h2。“列出的路径”是 ABDG、ACDG 和 ABCDFG

这是我从图中构建的搜索树（具有各种启发式方法和操作成本）： 该解决方案表明 DFS 将返回 ABDG、ACDG 和 ABCDFG，因为“DFS 可以返回任何路径”

我可以理解，如果决胜局是字母表中较早的字母，DFS 将返回 ABCDE G。如果决胜局是字母表中较晚的字母，DFS 将返回 ACD G。但我不明白在什么情况下情况 DFS 将返回 ABDG 或 ABCDF G。

我还认为 DFS 扩展了最深的节点并以这种方式返回解决方案。它可以返回任何路径解决方案是真的吗？如果是这样，怎么做？

当我运行我的程序时，我得到这个错误：

我将相同的 MCTS 代码用于 3x3 板尺寸，它不会崩溃并快速返回有竞争力的动作。但是当我尝试将它用于 15x15 板尺寸时，游戏在 1235 次迭代后崩溃，并出现上述错误。

我想我已经通过在 1235 次迭代后不允许扩展任何节点来解决问题的症状。这最终确实会带来竞争性举措，尽管这需要很长时间才能发生。

对我来说，根本原因是我试图创建的树的大小，因为相同的代码适用于 3x3 板，但不适用于 15x15 板；包含所有节点对象的树的大小太大了。因此，这只是这种方法的问题，而不是我的编码问题。

我确实认为我可以尝试：在 x 次迭代之后，如果一个节点已被访问 y 次但获胜分数低于 z，则删除该节点。我的想法是，如果经过 x 次迭代，并且被访问 y 次但获胜分数仍然很低，那么这个节点可能会占用树中不必要的空间，因此可以删除。

我的问题是：

有没有更好的方法让我的程序返回移动而不是崩溃，而不仅仅是减少扩展的数量并且不必实施上述检查？（即使最好的移动需要很长时间才能计算出来）。

这是我的一些未经编辑的代码：

已编辑** MCTS 扩展功能：

MCTSPlayer 功能：

新包含在下面**

选择初始节点函数（将继续，直到可能的移动列表大小 == 为 0）：

"+initialNode.childrenList()); //System.out.println("剩余节点可能的移动："+initialNode.getPossibleMovesSize()); } return initialNode; }

选择功能：

childrenLeft函数：

你好，

当我在上面的现有代码块中没有子组件的组件（文本框、收音机等）中搜索时，我可以找到该组件。但是，我找不到带有子组件的组件，例如表格。用if检查可以找到，但是由于不知道它会有多少个子组件，所以只能用一个子元素操作成功。

我的问题是我想搜索整个列表的“关键”参数。即使具有此键的元素是子元素，我也想找到。

Negamax 通常如下所示：

最初的调用是negamax(rootNode, depth, −∞, +∞, 1)最大化玩家调用它。

我以最大化玩家调用它的方式实现了 Negamax，但每个rootNode都是最大化玩家的移动之一：

因为 Negamax 返回一个值，所以我想要一个棋盘状态（移动）。所以我手动做第一级的 Negamax，这样我就可以解析出最好的移动在哪里。但是我应该呼吁什么价值观negamax？为了更具说明性，如果最大化玩家调用negamaxHandler，应该negamaxHandler调用：

或者是其他东西？澄清：

• 最大化玩家通话negamaxHandler
• 每个顶级调用negamaxinnegamaxHandler应该最小化

我正在编写一个人工智能程序来解决以下问题：

在 m*n 网格的不同单元中有 k 个机器人。这个网格的一些细胞是有毒的（机器人知道哪些细胞是有毒的）。在每一步中，这些机器人中的每一个都可以移动到 4 个方向之一（如果目标细胞无毒）或留在原地。我想找到将所有机器人聚集在一个单元格中所需的最小步骤数（哪个单元格都没有关系）。

我想使用搜索算法来解决这个问题（比如 A*），但我真的不知道如何为我的状态建模，更重要的是，如何找到每个节点的子节点。我的意思是我想将一步可以到达的所有可能的网格考虑为某些当前状态的子级，但我不知道在 python 中对此进行建模的好方法是什么，我希望我能得到想法这里...

我有一个基本的递归深度优先搜索程序，可以在大树中搜索未探索的路径。
有没有办法暂停和保存树，这样我就可以稍后恢复搜索，而不是每次结束程序时都重新开始搜索？
我正在使用 python 和一个名为 pycharm 的 python IDE。

在回溯中，即用于解决 n-queens 问题的算法，基本上有两种方法可以进行递归调用：

1. 复制父板以制作子板，通过放置新皇后来修改子板，然后在子板上进行递归调用。
2. 直接修改板子，递归调用，然后撤消修改。

第二种是首选，因为它避免了昂贵的复制。

这种选择也存在于其他算法中，例如游戏中的极小极大。

与模式 1 相比，模式 2 有名称吗？

这个问题涉及人工智能、启发式和博弈论。请提供您的答案的解释。任何帮助将不胜感激