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-5b71603640763329659953/] 这个算法很简单,其复杂度是O(n)的,一般来说,这样的复杂度并不会使我们困惑,但是一般应用幂运算的地方,指数都会非常非常的大,比如1 000 000 000这个级别的,这时候我们会遇到两个问题,第一个就是我们不能再用int来存储整数,必须用高精度整数类型来进行存储,另一个就是在指数是如此变态的数量级之下,我们的计算量会骤然上升,结果也会异常惊人的大。 快速幂算法就是为了解决这个问题而发明的,其实它本身很简单,就是利用二分法,在具体介绍...

队列与BFS搜索

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

素数筛法求素数

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

[STL]排列函数next_permutation()

我们自然知道C++的STL提供了丰富的基本数据结构以及算法支持,但事实上在使用中,我们常常容易忽略它,因为学习STL本身也需要一定的时间成本。STL基于泛型编程(Generic Programming, GP),很多人看到这个术语就打了退堂鼓,之内诸如迭代器之流,也更是云里雾里,不知所云也不想探究之,所以明明很好的工具就在手边,但是却弃之不用,着实可惜。 认识这个函数纯属偶然,今天在POJ上做题,看到了一道题[1]的Discuss中提示使用这个函数会使大大简化题目的难度,那么这个函数究竟就以用来做什么呢? 从标题我们就可以知道,可以这个函数用来获取一组元素的全排列,根据其定义,当你输入一组元素后,函数会将这组元素进行排列,排列结果为这组元素按字典序的下一个排列。这里先解释两个名词:一个是字典序,一个是全排列。 所谓字典序,顾名思义,就是像字典上那样的规则对元素进行排列: 我这里从身旁随手的一本字典翻开一页,单词如下: career careerist carefree careful ca

解析算术表达式[3]扩展与延伸

在之前的文章中,我们已经实现了输入一个四则运算表达式(即只包含加减乘除和括号的表达式)的字符串,然后求出其运算结果的功能。整个过程的算法是非常明确,而且并不复杂,包括转换及求值,算法的时间复杂度为O(N),事实上,如果我们在字符一个个读入的时候同时进行转换求值,也是可以的。在实现了四则运算后,这样的程序几乎就可以作为一个比较“智能”的计算器的后台了(这时候我们输入2+3*4,得到的结果不会再是20,而是会得到正确的结果14),但是这样并不能使我们满足,我们所实现的四则运算,实在太简单,而如果想计算更为复杂的表达式,仅仅通过这四种运算,就显得力不从心了。这篇文章,作为解析算术表达式的最后一篇,我想主要来延伸讨论下面几个问题: 1.四则运算属于左结合的运算符,那么对于右结合的运算符,能否很好的加入进来呢?比如“^”这样的幂指运算符(对于习惯C语系的童鞋来说,a ^ b这样的运算等效于pow(a, b)),至于左结合和右结合的区别,稍后会在下文中谈到。 2.能否加入函数运算,让表达式支持sqrt(a+b)+c