问题标签 [search-tree]

我一直在为即将举行的编程比赛练习，我偶然发现了一个让我完全困惑的问题。然而，我觉得这是一个我现在应该学习的概念，而不是指望它永远不会出现。

基本上，它处理棋盘上的骑士棋子。您有两个输入：起始位置和结束位置。目标是计算并打印骑士到达目标位置的最短路径。

我从来没有处理过最短路径的事情，我什至不知道从哪里开始。我采用什么逻辑来解决这个问题？

PS如果有任何相关性，他们希望您通过允许骑士移动到由骑士可以进行的（可能）八个动作形成的广场的四个角落来补充骑士的正常动作，因为广场的中心是骑士的位置。

我一直在尝试拆开这个基于关键字创建搜索树的应用程序，但我担心它对我来说有点太复杂了。有人介意解释一下吗？

格式已关闭，所以这里有一个pastebin（pastie.org 已关闭？）版本。

任何帮助表示赞赏。

假设我有以下 Haskell 树类型，其中“State”是一个简单的包装器：

我还有一个函数“expand :: Tree a -> Tree a”，它接受一个叶节点，并将其展开为一个分支，或者采用一个分支并原样返回。这种树类型表示 N 元搜索树。

搜索深度优先是一种浪费，因为搜索空间显然是无限的，因为我可以通过在所有树的叶节点上使用 expand 轻松地继续扩展搜索空间，并且有可能意外错过目标状态是巨大的......因此唯一的解决方案是广度优先搜索，在这里实现得相当不错，如果它在那里，它将找到解决方案。

不过，我想要生成的是遍历查找解决方案的树。这是一个问题，因为我只知道如何进行深度优先，这可以通过简单地在第一个子节点上一次又一次地调用“扩展”函数来完成......直到找到目标状态。（除了一个非常不舒服的列表之外，这真的不会产生任何东西。）

谁能给我任何关于如何做到这一点（或整个算法）的提示，或者判断它是否可能具有相当的复杂性？（或者这方面的任何资料，因为我发现很少。）

我引用人工智能：一种现代方法：

深度优先搜索的属性很大程度上取决于使用的是图搜索还是树搜索版本。避免重复状态和冗余路径的图搜索版本在有限状态空间中是完整的，因为它最终会扩展每个节点。另一方面，树搜索版本并不完整 [...]。深度优先树搜索可以在不增加内存成本的情况下进行修改，以便根据从根到当前节点的路径上的状态检查新状态；这避免了有限状态空间中的无限循环，但不能避免冗余路径的扩散。

我不明白图形搜索如何完整而树搜索不是，因为树是一个特定的图形。

此外，我不清楚“无限循环”和“冗余路径”之间的区别......

有人可以向我解释一下吗？

附言。对于那些有这本书的人，它是第 86 页（第 3 版）。

我想知道是否存在可以绘制 Prolog 程序的逐步搜索树的工具？谢谢。

我对以前的 Stack Overflow 帖子有一个问题@ Knight's Shortest Path on Chessboard

我理解'好的，这是一个图形问题，它的稀疏矩阵就像'的回复：

它描述了现有的边缘。但是我仍然不知道这个图的数据结构应该是什么样子（它是一个邻接矩阵吗？上面表示为“稀疏矩阵”，还是其他什么？），以便 Dijkstra 的算法可以很容易地使用它。

http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm。

从算法描述来看，如果图数据结构是一组顶点，并且有可用的邻居顶点信息，看起来很方便。但我们如何实现这一目标？

如何为该图写出示例数据结构？我正在寻求了解如何将它方便地链接到 Dijkstra 的算法。

我正在阅读论文，使 B+-trees 缓存在主内存中具有意识。在第 3.1.2 节中，作者描述了几种在 CSB+ 树节点中搜索的方法。

基本方法是使用传统的 while 循环简单地进行二进制搜索。

统一的方法是通过代码扩展，将 while 循环展开为if-then-else语句，假设所有键都已使用。

作者给出了以下示例，该示例展示了对具有多达 9 个键的节点的搜索展开。节点中的数字表示if测试中使用的键的位置

然后是令人困惑的部分：

如果实际只存在 5 个键，我们可以用恰好3次比较遍历这棵树。另一方面，将最深的子树放在左侧而不是右侧的展开将需要在某些分支上进行4 次比较。

那么为什么需要在以下树中进行更多比较：

此外，

如果我们知道我们只有五个有效键，我们可以硬编码一棵平均使用2.67次比较而不是 3 次比较的树。

2.67是怎么来的？

任何提示将不胜感激。此外，将我指向代码扩展知识的链接会很有帮助。

实际上，我不确定在论文上提出问题是否合适，因为在此处转录时可能遗漏了一些关键信息（问题可能需要重新格式化）。我只是希望有人碰巧读过这篇论文。

谢谢

我正在使用 SWI Prolog 学习 Prolog，我对 Prolog 中2-3 字典的实现如何工作有一些疑问。

我知道2-3 字典的理论是树，其内部节点可以生成 2 或 3 个具有以下属性的子树：

1）所有的物品都存放在叶子里，按照从小到大的顺序排列

2）所有叶子都在同一级别

3）内部节点不包含插入的项目，但包含以下列方式指定子树的最小元素的标签：

• 如果内部节点有 2 个子树，则该内部节点中的标签包含其 RIGHT SUBTREE 的 MINIMAL ELEMENT（因此，如果我正在搜索小于标签的项目 X，则我确定它在左子树中）
• 如果内部节点有 3 个子树，则该内部节点中的标签包含 2 个值：M2 和 M3，其中 M1 是存在于中心子树中的最小值，而 M3 是作为右子树的最小值

因此，搜索此类字典中是否存在项目非常简单。

插入更复杂，我已经理解它的理论，但我对 Prolog 的解释有一些问题。

这是我的程序（取自 Ivan Bratko 的书：人工智能编程）：

在这个实现中，我有：

• l(X) rappresent 一个存在于我的树中的项目
• n2(T1,M,T2)表示具有 2 个子树 T1 和 T2 的树，其中 M 是 T2 中的最小元素
• n3(T1,M2,T2,M3,T3)** 表示具有 3 个子树的树：T1,T2,T3 其中 M2 是 T2 中的最小元素，M3 是 T3 中的最小元素

第一个疑问与add23和ins谓词之间存在的关系有关，这些：

正如评论中所写，我认为第一个与新树不会向上生长的情况有关（例如，我有一棵有 2 个子树的树并插入了一个新项目，我正在创建一个新的子树它的叶子在所有其他叶子的同一级别（因此内部节点现在将有 2 个标签）对吗？

所以在逻辑上我可以把它读成：如果ins(Tree, X, Tree1)谓词是 TRUE 那么我将 X 添加到 Tree 生成新 Tree1 ，它与旧 Tree 具有相同的高度但包含 X 项（所以它必须有一个内部节点有 3 个孩子）

第二种情况与我有一棵树的情况有关，我必须在一个已经有 3 个子树的节点中插入一个新项目，所以我必须将旧树拆分为 2 棵树，作为根，两者都作为标签 a单个标签取自旧原始节点的 2 个标签。所以我可以将新项目作为叶子和新树的新根插入。

所以在逻辑上我可以把它读成：

如果谓词ins(Tree, X, T1, M2, T2)为 TRUE，则意味着谓词为 TRUE：add23(Tree, X, n2( T1, M2, T2))

在这种情况下，我将具有3 个子树的原始树 Tree 拆分为两个不同的树：T1 和 T2，它们作为根有一个节点，该节点具有从原始树的旧根获取的单个最小标签。

所以碰巧我肯定会有这些树中的一棵有两个子树，而另一棵有一个子树，所以我可以将新插入的项目添加到这个子树中，并将它用作增加的新树的新根高一级。

这样对吗？我不确定这...

在这本书中，我找到了对ins谓词的三种具体情况的解释，我对它的工作原理有很多疑问：

情况1：

这种情况说我原来的树 Tree是：n2(T1, M , T2)并且我将 X 插入到 Tree 中，这是一棵只有2 个子树的树：T1 和 T2。

M是右子树的最小元素

因此，如果gt(M, X)为 TRUE，则意味着 M>X，因此这意味着 X 可能是成为NT1的左子树（为什么？这可能取决于旧的 T1 在它的一个中只有 1 个叶子）子树？），所以最后，原始树变成了n2(NT1, M, T2)

我认为这种情况很简单

案例二：

在这种情况下，我说原始树 Tree是：n2(T1, M , T2)并且我将 X 插入到 Tree 中，这是一棵只有2 个子树的树：T1 和 T2。

M是右子树的最小元素

如果 M>X 为 TRUE，则谓词为 TRUE：ins(T1, X, NT1a, Mb, NT1b)

这意味着我将 T1 拆分为 2 个子树 NT1a 和 NT1b，将第三个子树添加到成为n3(NT1a, Mb, NT1b, M, T2)的原始树中

好的，这很清楚，但我的问题是：在完整的代码中，这个谓词必须满足什么？我在做混乱...

案例 3：

这种情况是原始树 Tree 有 3 个子树，当我必须插入它时，我必须将原始树分成两棵树（n3（T1，M2，T2，M3，T3）和 n2（NT1a，Mb , NT1b)) ，将新项 X 插入这些子树之一，并使用第二个子树的最小元素作为左子树的根作为新树的根（现在高于一个级别）

我的疑问是：在前一种情况下，NewTree是n2(NT1a, Mb, NT1b), M2, n2(T2, M3, T3)

所以 M2（右子树的最小元素）是新的根，因为 M2>X 是真的？

你能给我一些提示来更好地理解这些东西吗？

我想使用 Treap 结构，但我对这种类型的树不太熟悉。

我有两套，我想写一个方法来将它们与 Treap 进行比较。此方法应返回一个值，该值显示两个集合的相似性。（我的工作是检索一个与输入集最相似的集合）

我该怎么做这项工作？

谢谢

我有一个树算法和数据库问题，我想得到答案。

我有几个区域，比如说 20 个。每个区域都有子区域 ~ 20 个。这些父区域分布在地图上。其中一些父区域彼此靠近。

数据库如下所示：[area_id, title, parent_id] - 有些有多个子节点，有一个包含所有区域的根节点。（邻接表模型）

为了在图片中制作这个，我可以这样做：

正如我所说，不同的区域可以彼此靠近（或远离）。我想以某种方式将1 区和 5 区联系在一起，因为我知道它们很近，并且1 区也靠近 4 区​​。现在，问题来了，假设4 区也靠近 5 区.

它看起来像这样：

这使它成为一个无限循环？因为我希望Area 1靠近Area 4，而且Area 4也靠近Area 1。

我想做一个搜索，在这里你可以选择“搜索附近区域”，所以你选择一个区域然后你可以搜索附近的区域。我可以使用一些技巧，关于如何使用数据库和 php 解决这个问题。

我一直在这个论坛上寻找帮助，但我真的不知道这个问题的“名称”，如果有人能指出我正确的方向或直接在这个线程中帮助我，我会很高兴。

谢谢大家，如果还有什么需要知道的，我会尽快回复。