A*算法 – 八数码问题

A*算法 – 八数码问题
上一篇文章我介绍了A*算法,A*用于找到从起始状态到目标状态的一条最短路径,而且根据估价函数的不同,其搜索效率也会有所不同。其实我们只要找到一个估价函数h(s) > 0,那么这个A*算法最后至少要比BFS强。 我们今天来做一个A*算法的实战演练,借此来更透彻的理解A*算法。我们要解决的问题就如题目所述——八数码问题。 八数码问题其实非常容易理解,你我在儿时肯定都玩过这样的游戏。 这是一个九宫格,其中有八个格子有数字,还有一个格子是空位,和空位相邻的数字格子可以和空位相互交换,游戏的最终目的就是让这些数字形成一个有序的局面。假如说我们有左边这样一个初始状态,我们现在就是想找到一种最快捷的方法,使左边的初始状态转换为右边的最终状态。 如果按照BFS的思路,我们每次扩展四个节点,分别是空格上移、下移、左移和右移(当然,大多数节点是无法完全扩展这四个方向的),一层层搜索之后,若发现了目标状态,则从目标状态节点开始向父节点回溯,由此就可以得到一个步数最少的解法了。 在之前的文章中也提到了,BFS是

A*算法 – 介绍

A*算法 – 介绍
这学期学校开了人工智能课程,留了一项小作业,就是使用A*算法解决八数码问题,觉得挺有意思,于是就写下这篇文章来与大家分享。其实我很久很久以前就已经听闻过A*算法的大名了,但是鉴于当时的理解能力不足(懒?),就不了了之了。 记得当年第一次见到A*这个名字的时候,感觉非常的高端洋气,于是在气势上就输给了它,所以大家在继续阅读这篇文章的时候一定要放松,这个算法的确很著名,而且也的确非常的高效,但是它并不复杂,而且非常容易理解。 首先说下A*算法的作用:找到一条从起始状态到最终状态的最短路径。不知道大家看到这个作用有没有联想到什么?具有同样作用的一个算法“BFS广度优先搜索”在我之前的博客中介绍过,如果你不知道,可以点击这里回顾一下这个算法。 BFS通过“一层一层”地扩展节点,以此确保在发现目标状态的时候整个搜索树的深度最低,这是一种非常盲目的搜索方法,因为如果解的深度较深的话,我们有时候不得不搜索过所有的节点才能找到目标,而A*算法则不然,我编一个故事说明BFS和A*算法的区别: 王尼玛同学去食堂吃饭,但

用矩阵幂求解线性递推序列

用矩阵幂求解线性递推序列
在上一篇文章中我们探讨了如何快速求解幂运算的方法,并且最终给出了一个时间复杂度为O(logn)的算法,那么在这一片文章中,我想说一说快速幂运算的一个应用,也就是利用矩阵的快速幂运算求解线性递推序列。 首先我们来了解下什么是线性递推序列,在这里给大家看一个大家一定很熟悉例子,那就是斐波那契数列,它的递推公式是: 从上面这个方程中我们可以看到很明显的递推关系,实际上我们在做运算的时候,如果一步一步的按照递推式计算,将会消耗大量的时间,于是我们求助于其它的方式。 首先,对于一般的k阶线性递推函数y,应当有这样的形式: 若对于这个递推函数,如果对所有不小于k的n有: 直观来看,这个递推函数应该是长成这个样子的: 当给定了从X(0) ~ X(k – 1) 的k个初始值的时候,我们就能利用这个递推公式计算出所整个序列。那么解决问题的关键就落在了递推函数f的身上。 观察递推函数f的形式,我们发现它可以用两个向量乘积的形式来表达: 为了使用这个函数计算的递推序列能够方便的进入下次的跌打运...

快速幂运算

快速幂运算
最近看到的一些题里有利用快速矩阵幂来求快速解递归函数(比如Fibonacci数列),在很久之前看和RSA算法里也涉及到了快速求幂的算法,所以今天就想一块来介绍一下。 在介绍开始之前,先对本文的算法做一个声明,下文所提到的幂运算的指数n,满足条件n >= 0,这一点非常重要。 首先幂运算,大家其实都很好理解,其实就是: 无非就是把一个数自乘n次,所以我们通常计算数字的幂的算法就是: (代码1) [crayon-5a5ea66345fd9279946012/] 这个算法很简单,其复杂度是O(n)的,一般来说,这样的复杂度并不会使我们困惑,但是一般应用幂运算的地方,指数都会非常非常的大,比如1 000 000 000这个级别的,这时候我们会遇到两个问题,第一个就是我们不能再用int来存储整数,必须用高精度整数类型来进行存储,另一个就是在指数是如此变态的数量级之下,我们的计算量会骤然上升,结果也会异常惊人的大。 快速幂算法就是为了解决这个问题而发明的,其实它本身很简单,就是利用二分法,在具体介绍...

队列与BFS搜索

队列(queue)是一种简单的数据结构,它所遵循的规则是先进先出(First in First out, FIFO),对比LIFO的数据结构“栈”,你可以阅读[这篇文章]。这里所说的队列和我们现实中的队列是一样的,就比如说公交车排队,早到的,排在靠前位置的人自然可以优先上车(假设大家都很文明),利用这种特性,人们可以用来管理各种各样需要按照先后循序的事物,比如银行,因为银行的服务窗口有限,不能同时给所有人提供服务,所以利用计算机提供一个队列系统,给客户一个排队号码,计算机系统可以根据这个排队号码的大小来决定为谁优先提供服务。 按照和栈类似的介绍方法,为了使代码的表意更加明确,我使用C++标准库提供的队列适配器queue来构造队列这种数据结构。 使用queue需要引用头文件: [crayon-5a5ea6634807c075097210/] 初始化一个空的队列: [crayon-5a5ea66348083883528085/] 令一个元素进入队尾: [crayon-5a5ea6634808606

内心的“魔鬼”

警署获准进行一次大规模的逮捕行动,这项行动打破了加利福尼亚的平静周末。共计有九名大学生被逮捕,他们被戴上手铐,在被告知宪法所赋予的权利之后被带到市监狱登记并留下指纹,随后被蒙上眼睛送往斯坦福监狱。在监狱,按照所有收押犯人都必备的流程,犯人被进行裸身搜查,所有的随身财产都被警方收缴,并随后换上了印有背号的囚服。 狱警穿着威严的制服,戴着黑色墨镜,持有警棍、哨子、手铐……这无疑显示出他们在这里,拥有绝对的权威。 在一开始,被逮捕的学生们表现出极大的抗争性,甚至于嘲弄狱警,这当然不是什么明智的做法,狱警很快就开始对这些囚犯进行镇压行动:关禁闭、剥夺其吃饭、睡眠的权利,让他们用手清洗马桶或者脱光他们的衣服,让他们做持续的俯卧撑、跳跃运动……总之,用尽一切手段来对其进行羞辱。而且这种情况愈演愈烈,比如坐在犯人身上让其俯卧撑,进行人身攻击等羞辱。狱警们也很擅长使用心理战术分裂犯人内部,比如给某些顺从他们的囚犯以特权。在狱警对某些囚犯进行虐待的时候,其他囚犯甚至会带有欣赏的意味来观看。有些狱警似乎对这种虐待并不支持,

素数筛法求素数

如今的孩子可能没怎么见过筛子,传统的筛子样式如同[图1],多是用竹子编织而成,其作用就是通过抖动让细小的东西从筛子下部掉落,而较大的颗粒则留在筛子内,筛子上留的孔洞的大小不同,决定其的应用的地方,这种一次性“留精弃粗”的方式给人们的生活带来的很多的便利(现在有些饮用水过滤机就是利用层层筛网,让自来水成为可供饮用的纯净水)。 那么素数筛又是什么呢?顾名思义,所谓素数筛,“筛”的就是“数”。我回想了一下小学最开始学素数(那时候还有一种说法叫做“质数”,但是就语言上来说,我觉得“素数”这种叫法和“合数”比较搭配,类比于“化学元素”和“化合物”来看,叫“素数”非常贴切)的时候,书上给出的“找素数”的方法,并不是试除法,而是筛选法。所谓筛的过程,用[图2]来展示就很形象: 第一层筛网筛掉所有数字中大于2,且为2的倍数的数字; 第二层筛网筛掉所有数字中大于3,且为3的倍数的数字; 第三层筛网筛掉所有数字中大于5,且为5的倍数的数字; …… 层层筛选之后,我们就可以得到一个范围内的素数表[图3...

冷眼旁观,是谁错了?

现在一些报道中我们能看到类似于这样的消息:某人遭遇抢劫,周围数人却无一人上前制止;某人被车撞,肇事者逃逸,围观十余人无一人报警……很多网友评论说,国人良知泯灭,麻木不仁,事不关己高高挂起……真的是这样么? 曾经在美国发生过这样一起案例,引起了人们广泛的讨论: 在纽约皇后区,一名女子被一名持刀男子劫持,在行凶过程中,凶手曾两次被旁观者的说话声以及周围房子突然亮起的灯光吓住,但稍后片刻,便继续行凶。最终这名女子遭到强暴并被刺身亡。而根据调查,当时在场共计有38个居民目睹了这次行凶事件,可直到最后女子死亡,才有一个目击者给向警方报案。当时的新闻媒体也在批判人性冷漠、麻木,可为什么如此众多的人亲眼目睹凶手行凶却没有见义勇为或者哪怕打一个电话给警方呢?社会心理学家为此设计了一些实验,来探究导致这种“麻木”现象的出现的真正原因。 毕布•拉塔内(Bibb Latane)和约翰•达利(John Darley)做了这样一个实验。 研究者把一名大学生单独安置在一个房间内,这个房间内有一个可供联络使用的对讲设备,研究人员...