$KMP$算法
$next$数组
$next$数组的实质是一个前缀表，其作用是用来回退，它记录了模式串与主串(文本串)不匹配的时候，模式串应该从哪里开始重新匹配。具体来说前缀表记录下标$i$之前（包括$i$）的字符串中，有多大长度的相同前缀后缀，即最长公共前后缀。
文章中字……继续阅读 »
yanzexi
1年前 (2023-10-12) 162浏览 0评论
1个赞
启发式函数对性能的影响
影响与分析
一种描述启发式函数质量的方法是有效分支因子$b^*$。如果针对一个特定问题，$A^*$搜索所生成的总节点数是$n$，而解的深度是$d$，那么$b^*$就是深度为$d$的均衡树要包含$n + 1$个节点所必需的分支因子。因此有:
$$
n+1=1+b^*+\left( b^* \right) ^2+\cdot ……继续阅读 »
yanzexi
1年前 (2023-10-12) 187浏览 0评论
1个赞
表达式计算
后缀表达式计算
int op(int a, int b, char Op){
if(Op == '+'){
return a + b;
}
if(Op == '-'){
return a - b;
}
if(Op == '*'){
return a + b;
}
if(Op =……继续阅读 »
yanzexi
1年前 (2023-10-11) 174浏览 0评论
1个赞
满意搜索
不可容许的启发式函数
$A^*$搜索有很多好的性质，但它扩展了大量节点。如果愿意接受次优但“足够好”的解——即满意解，则可以探索更少的节点（花费更少的时间和空间）。
如果允许$A^*$搜索使用不可容许的启发式函数，那么算法就有可能错过最优解，但是可能更准确，从而减……继续阅读 »
yanzexi
1年前 (2023-10-11) 182浏览 0评论
1个赞
有信息搜索（$informed$ $search$）策略——使用关于目标位置的线索——通常比无信息搜索策略更有效地找到解。线索以启发式函数（$heuristic$ $function$）的形式出现，记为 h(n)：
贪心算法 （$greedy$ $best$-$first$ $search$）
说明与性能分析
&nbs……继续阅读 »
yanzexi
1年前 (2023-10-10) 180浏览 0评论
1个赞
$PS：$邓书里的向量实际上就是顺序表、而列表则相当于链表。接下来以殷书为主，王道和邓书作为补充。一些太简单的就懒得记录了。
顺序表
顺序表
顺序表逻辑结构为线性，存储结构为顺序存储；性能分析如下：
$$
\begin{cases}
\frac{n+1}{2}&……继续阅读 »
yanzexi
1年前 (2023-10-09) 183浏览 0评论
1个赞
无信息搜索算法是指在不提供有关某个状态与目标状态的接近程度的任何线索的情况下进行的搜索。
广度优先搜索（$BFS$,$breadth$-$first$ $search$）
定义
当所有动作的代价相同时，正确的策略是采用广度优先搜索，即先扩展根节点，然后扩展根节点的所有后继节……继续阅读 »
yanzexi
1年前 (2023-10-09) 226浏览 0评论
1个赞
问题形式化
引入
回到之前的探讨，我们应该知道人工智能应该是“正确的行为”，而在需要采用的正确动的作不明显时，智能体需要提前规划：考虑一个形成通往目标状态路径的动作序列。这样的智能体被称为问题求解智能体（$problem$-$solving$ $agent$），它所进行的计算过程被称为搜索（$search$）。
&nbs……继续阅读 »
yanzexi
1年前 (2023-10-08) 239浏览 0评论
1个赞
人工智能
什么是人工智能
约翰·麦卡锡：它是制造智能机器，特别是智能计算机程序的科学和工程。它与使用计算机理解人类智能的类似任务有关，但人工智能不必局限于生物学上可观察的方法。
马文·明斯基：“使计算机能够做一些当由人类完成时会被认为需要智力的事情”
人工智能之父们及其贡……继续阅读 »
yanzexi
1年前 (2023-10-07) 231浏览 0评论
1个赞
霍夫丁界
最一般的霍夫丁界
若$r.v.$ $X_1,X_2,…,X_N$相互独立，且$X_i$的均值为$\mu _i$，次高斯参数为$\sigma _i$，则对任意的$\epsilon >0$都有：
$$
Pr\left[ \sum_{i=1}^n{\left( X_i-\mu _i \right)}\ge \epsilon ……继续阅读 »
yanzexi
1年前 (2023-10-06) 274浏览 0评论
1个赞
