堆
定义
堆应满足结构性和堆序性两个条件，首先，其逻辑结构须等同于完全二叉树，此即所谓的“结构性”。如此，堆节点将与词条一一对应。其次，就优先级而言，堆顶以外的每个节点都不大（小）于其父节点，此即所谓的“堆序性”。堆的结构等同于完全二叉树的堆，n 个词条组成的堆的高度$h = \lfloor log_2n \rfloor = O(logn)$……继续阅读 »
yanzexi
1年前 (2023-10-16) 250浏览 0评论
1个赞
蒙特卡洛树搜索$(MCTS)$
引入
对围棋来说，$\alpha $-$\beta $启发式树搜索有两个主要缺点：首先，围棋的分支因子开始时为 361，这意味着$\alpha $-$\beta $搜索被限制在 4～5 层。其次，很难为围棋定义一个好的评价函数，因为子力价值并不是一个强有力的指标，而且大多数状态直到最后阶段都在不断变化。为了应对这……继续阅读 »
yanzexi
1年前 (2023-10-16) 245浏览 0评论
1个赞
线索二叉树
定义
二叉树虽然是非线性结构,但二叉树的遍历却为二叉树的结点集导出了一个线性序列因而，二叉树的结点存在关于这个线性序列的前驱和后继。对应于前序、中序、后序遍历,除了相应序列的第一个和最后一个，二又树的每个结点都存在前序前驱/后继、中序前驱/后继、后序前驱/后继。
……继续阅读 »
yanzexi
1年前 (2023-10-15) 242浏览 0评论
1个赞
对抗搜索
引入
在竞争环境中，两个或两个以上的智能体具有互相冲突的目标，这引出了对抗搜索问题。通常对博弈的研究专注于如国际象棋、围棋和扑克之类的项目，而不是处理真实世界中的混乱冲突。这些项目的简化特性是一个优势：博弈状态很容易表示，智能体通常仅能执行少数几个动作，而且动作的效果由明确的规则定义。对于体育比赛，描述更加复杂，可能动作的范围更大，而……继续阅读 »
yanzexi
1年前 (2023-10-15) 300浏览 0评论
1个赞
二叉树遍历的非递归实现
先序遍历
stack<TreeNode*> S;
void per(TreeNode* root){
TreeNode* now = root;
while(true){
while(now){
cout << now -> val << '\t';
……继续阅读 »
yanzexi
1年前 (2023-10-14) 247浏览 0评论
1个赞
非确定性动作的搜索
引入
当环境部分可观测时，智能体并不确定它处于什么状态；当环境是非确定性的时，智能体不知道在执行某个动作后将转移到什么状态。这意味着智能体所思考的不再是“我现在位于$s_1$状态，如果我执行$a$动作，我将会进入$s_2$状态”，而是“我现在位于$s_1$或$s_3$状态，如果我执行$a$动作，我将会进入$s_2$、$s_4……继续阅读 »
yanzexi
1年前 (2023-10-14) 331浏览 0评论
1个赞
树
引入
树中的元素之间并不像顺序表和链表一样，存在天然的直接后继或直接前驱关系。不过只要附加某种约束（比如遍历），也可以在树中的元素之间确定某种线性次序，因此树属于半线性结构（semi-linear structure）。以下是一些易混淆的概念：
分支结点：除叶结点外的其……继续阅读 »
yanzexi
1年前 (2023-10-13) 251浏览 0评论
1个赞
在一个非确定性的世界中，智能体将需要一个条件规划，并根据它所观测到的情况执行不同的动作。
之前的搜索问题关注于找到一条通过搜索空间的路径，但有时只需要关心最终状态，而不是到达状态的路径。局部搜索（$local$ $search$）算法的操作是从一个起始状态搜索到其相邻状态，它……继续阅读 »
yanzexi
1年前 (2023-10-13) 298浏览 0评论
1个赞
$KMP$算法
$next$数组
$next$数组的实质是一个前缀表，其作用是用来回退，它记录了模式串与主串(文本串)不匹配的时候，模式串应该从哪里开始重新匹配。具体来说前缀表记录下标$i$之前（包括$i$）的字符串中，有多大长度的相同前缀后缀，即最长公共前后缀。
文章中字……继续阅读 »
yanzexi
1年前 (2023-10-12) 217浏览 0评论
1个赞
启发式函数对性能的影响
影响与分析
一种描述启发式函数质量的方法是有效分支因子$b^*$。如果针对一个特定问题，$A^*$搜索所生成的总节点数是$n$，而解的深度是$d$，那么$b^*$就是深度为$d$的均衡树要包含$n + 1$个节点所必需的分支因子。因此有:
$$
n+1=1+b^*+\left( b^* \right) ^2+\cdot ……继续阅读 »
yanzexi
1年前 (2023-10-12) 254浏览 0评论
1个赞
