伸展树
引入
伸展树（$splay$ $tree$）也是平衡二叉搜索树的一种形式。相对于$AVL$树，伸展树的实现更为简捷。伸展树无需时刻都严格地保持全树的平衡，但却能够在任何足够长的真实操作序列中，保持分摊意义上的高效率。伸展树也不需要对基本的二叉树节点结构，做任何附加的要求或改动，更不需要记录平衡因子或高度之类的额外信息，故适用范围更广。
……继续阅读 »
yanzexi
1年前 (2023-10-19) 299浏览 0评论
0个赞
引入
引入
人类似乎具有知识，人类的知识能够帮助他们做事。在人工智能中，基于知识的智能体对知识的内部表示进行推理来确定要采取的动作。搜索求解智能体具有知识，但这种知识是非常有限且死板的。它们知道可以采取哪些动作，也知道在某个状态采取某个动作将得到哪种结果，但它们不知道一般事实。问题求解智能体具有的知识对寻找从起点到终点的路径这种问题非常有用，但……继续阅读 »
yanzexi
1年前 (2023-10-19) 252浏览 0评论
0个赞
二叉搜索树的最小绝对差
中序遍历逐行算差：
TreeNode* pre = nullptr;
int result = INT_MAX;
void traversal(TreeNode* cur) {
if (!cur){
return;
}
traversal(cur -> left);
……继续阅读 »
yanzexi
1年前 (2023-10-18) 274浏览 0评论
0个赞
回溯搜索
引入
许多情况下完成约束传播过程后仍存在具有多个可能值的变量。在这种情况下，必须通过搜索来求解问题。首先介绍用于部分赋值的回溯搜索算法，$CSP$的回溯搜索不断选择未赋值变量，然后依次尝试该变量的域中的所有值，试图通过递归调用将每个值扩展为一个解。如果调用成功，则返回解，如果调用失败，则将赋值恢复到前一状态，然后尝试下一个值。如果所有……继续阅读 »
yanzexi
1年前 (2023-10-18) 215浏览 0评论
0个赞
二叉搜索树
基于二叉树模板实现
查找：
bool search(TreeNode* root, int x){
if(!root){
return false;
}
if(x == root -> val){
return true;
}else if(x < root -> val){
……继续阅读 »
yanzexi
1年前 (2023-10-17) 267浏览 0评论
0个赞
定义
引入
之前的搜索部分讨论了通过搜索状态空间进行问题求解的思想：状态空间是一个由节点表示状态，边表示动作的图。领域特定的启发式算法可以估计从给定状态到达目标的代价，但从搜索算法的角度来看，每个状态都是原子的，即不可分割的——一个没有内部结构的黑盒。对于每个问题，需要领域特定的代码来描述状态之间的转移。
&……继续阅读 »
yanzexi
1年前 (2023-10-17) 302浏览 0评论
0个赞
堆
定义
堆应满足结构性和堆序性两个条件，首先，其逻辑结构须等同于完全二叉树，此即所谓的“结构性”。如此，堆节点将与词条一一对应。其次，就优先级而言，堆顶以外的每个节点都不大（小）于其父节点，此即所谓的“堆序性”。堆的结构等同于完全二叉树的堆，n 个词条组成的堆的高度$h = \lfloor log_2n \rfloor = O(logn)$……继续阅读 »
yanzexi
1年前 (2023-10-16) 249浏览 0评论
1个赞
蒙特卡洛树搜索$(MCTS)$
引入
对围棋来说，$\alpha $-$\beta $启发式树搜索有两个主要缺点：首先，围棋的分支因子开始时为 361，这意味着$\alpha $-$\beta $搜索被限制在 4～5 层。其次，很难为围棋定义一个好的评价函数，因为子力价值并不是一个强有力的指标，而且大多数状态直到最后阶段都在不断变化。为了应对这……继续阅读 »
yanzexi
1年前 (2023-10-16) 244浏览 0评论
1个赞
线索二叉树
定义
二叉树虽然是非线性结构,但二叉树的遍历却为二叉树的结点集导出了一个线性序列因而，二叉树的结点存在关于这个线性序列的前驱和后继。对应于前序、中序、后序遍历,除了相应序列的第一个和最后一个，二又树的每个结点都存在前序前驱/后继、中序前驱/后继、后序前驱/后继。
……继续阅读 »
yanzexi
1年前 (2023-10-15) 242浏览 0评论
1个赞
对抗搜索
引入
在竞争环境中，两个或两个以上的智能体具有互相冲突的目标，这引出了对抗搜索问题。通常对博弈的研究专注于如国际象棋、围棋和扑克之类的项目，而不是处理真实世界中的混乱冲突。这些项目的简化特性是一个优势：博弈状态很容易表示，智能体通常仅能执行少数几个动作，而且动作的效果由明确的规则定义。对于体育比赛，描述更加复杂，可能动作的范围更大，而……继续阅读 »
yanzexi
1年前 (2023-10-15) 300浏览 0评论
1个赞
