问题标签 [tree-search]

我正在编写一个迭代函数来搜索二叉树的某个值。在我了解如何泛化类之前，这已本地化为带符号的整数。

假设我的类是 BinarySearchTree，它有一个指向树根节点的指针。还假设节点是通过插入函数插入的，并且具有指向两个子节点的指针。这是 Node 结构的一个非常简略的版本：

因此，您可以放心地假设节点的 uninit 指针将为 NULL。

这是我的代码：

朋友拒绝此代码有两个原因：

1) 如果 next 没有子节点，则两者都将评估为零，并且我将过早退出循环（我永远不会检查搜索到的 val 与 next 的值）。

2）如果next有一个孩子，但是你要搜索的数据应该在树的空边，next将被设置为0，它会再次循环，比较next（即0）左右树之类while(0->left())的，导致未定义的行为。

有人告诉我，这两个问题的解决方案都在于循环条件，但我看不出我能做些什么来轻松解决这种情况。Stack Overflow 社区可以提供任何见解吗？

我正在编写一个分布式 Go/Gomoku 机器人。

基本上重点是将树搜索分发到许多计算机上。使用像 DFS 这样的基本树搜索算法，这将非常简单，因为我可以将搜索空间划分为子树。虽然我宁愿有更高效的东西，比如带有 alpha-beta 修剪的 mini-max - 但据我了解，如果没有任何共享内存，它是毫无意义的。所以我有点卡住了。

任何想法我可以使用什么算法高效且易于分发？更重要的是，我在哪里可以找到一些（伪）代码或者实现？

谢谢，

任何节点都可以有任意数量的子节点。为了搜索这棵树，我写了这样的东西

这不太管用...任何输入？

我注意到我遇到的一些“硬”组合问题可以用某种类型的树搜索（如 alpha-beta 剪枝、束搜索或类似算法）进行转换。 然而，对它们进行编程似乎是重复编码相同的东西，而且很容易出错。在我看来应该有一个实现这些算法的库，而我应该被要求写的是

1. 解决方案的编码，即如何从不完整的解决方案中获得更具体的解决方案。这将给出树/图结构。
2. 给定一个部分解决方案，如何获得最大/最小成本，以及可能的成本估算。
3. 初始解决方案/部分解决方案。
4. 也许某种验证解决方案。

很抱歉我没有给出任何具体的代码，但我想我已经解释了这个问题。如果我可以为上述功能编写代码，我是否应该能够轻松地运行许多树/图搜索算法？是否有任何用户友好的库/框架可以轻松支持这一点？我希望它使用 Python 或 C/C++，但很想听听任何建议。

编辑：更准确地说，我说的是知情树搜索算法。

我正在研究一个函数，该函数确定给定 html 元素的内容 - el - 在 lxml ElementTree 中是否是呈现的 HTML 页面中一行的前导内容。为此，我试图找到el左边的最右边的块级元素，然后确定这两者之间是否有内容。

我认为这可以通过以 DFS 的相反顺序遍历来发生，反向遍历从 el 开始。但我也一直在尝试使用 lxml 或 xpath 来查找是否存在更简单的方法来执行此操作。到目前为止，我已经找到了一些方法来查找具有某些标准的给定元素的祖先或左兄弟元素，但我还没有发现任何适用于特定节点右侧（或左侧）的整个树的东西。

有人知道使用 lxml 或 xpath 进行此搜索的更简单方法吗？

例子

在上面我已经为任何元素添加了一个“第一”类，当渲染时，它看起来会呈现一行的前导内容。特别感兴趣的是 id 为“tricky”的元素，因为该元素将呈现一行的第一个内容，即使它的祖先和兄弟姐妹都不是块级元素。“tricky” 将换行，因为它的兄弟姐妹之一（h1）的后代是块级别，并且在 h1 之后没有其他内容。

跟进 在这一点上，我已经用 Python 编写了一个函数，它执行一种向后遍历。它有点复杂，但它似乎工作：

关于人工智能中的 DFS、A* 搜索，图搜索和树搜索版本有什么区别？

T-SQL Tree Search

Select from set of nodes if they are under a parent

I have a very large tree in a MSSQL Db (80000+) records. My client has requested a quick search of the tree via a text LIKE command. The LIKE command returns < 500 records.

Is there some recursive command that will check the tree of each quickly to see if they are under a particular node?

Edit: I thought it was fairly clear however....

I am on SQL Server 2005.

I have recursive calls that are able to go down several levels quickly. however to do the Name search I would have to poll the entire tree which can be several hundred levels deep and is not an option. I was hoping for help designing a query so I can search the entire table first for the name match and filter the records that are not part of the tree in question.

我的理解是 CPU 的简单模型是状态机。

当我查看序言时，它似乎是树搜索（或图形搜索）组合，同时停止运行直到找到它的目标的约束。

有人告诉我，您可以在 prolog 中模拟一个简单的 CPU。

是否可以在 prolog 中像简单的 CPU 一样表示状态机模型？

有一个网站，它做POST，我想知道参数存储在哪里。我需要它来破解它们，在发布之前进行编辑。脚本很大而且很模糊，所以我无法通过阅读源代码找到我需要的对象。

我试图从这个答案window中用 JSON.prune序列化。我用来查找存储我需要的字符串的关键字在 28 兆字节的文本中被找到了近 40 次。即使我找到了子字符串，它也不是很可读。所以也许这不是要走的路。

我需要一些可以告诉我的东西：

• 已在以下位置检测到此子字符串：
  -- 字符串window.bla_bla_bla.deepobject.bla[5].blabla.msg_to_post
  -- 字符串window.bla_bla_bla.deepobject.bla[3].and_here
  -- 字符串window.and_even_here
  -- 等。

我正在尝试使用不同的算法解决问题，而最陡坡爬山 (SAHC) 和最佳优先搜索是我需要实现的其中两种算法。

根据维基百科：

“在最陡峭的爬坡过程中，所有后继者都会被比较，并选择最接近解决方案的人......”

“最陡坡爬山类似于最佳优先搜索，它尝试当前路径的所有可能扩展，而不是只尝试一个。”

SAHC : 比较所有后继者并选择最接近解决方案的。
BestFS：尝试当前路径的所有可能扩展，而不是只尝试一个。

我真的不明白这些有什么不同。有人可以帮我解决这个问题，最好用树来解释一下吗？