二叉搜索树
基于二叉树模板实现
查找：
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) 241浏览 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) 330浏览 0评论
1个赞
树
引入
树中的元素之间并不像顺序表和链表一样，存在天然的直接后继或直接前驱关系。不过只要附加某种约束（比如遍历），也可以在树中的元素之间确定某种线性次序，因此树属于半线性结构（semi-linear structure）。以下是一些易混淆的概念：
分支结点：除叶结点外的其……继续阅读 »
yanzexi
1年前 (2023-10-13) 250浏览 0评论
1个赞
在一个非确定性的世界中，智能体将需要一个条件规划，并根据它所观测到的情况执行不同的动作。
之前的搜索问题关注于找到一条通过搜索空间的路径，但有时只需要关心最终状态，而不是到达状态的路径。局部搜索（$local$ $search$）算法的操作是从一个起始状态搜索到其相邻状态，它……继续阅读 »
yanzexi
1年前 (2023-10-13) 297浏览 0评论
1个赞
