现在我们来讲一道非常经典的搜索的题目叫八数码问题。
八数码可以用深搜可以用广搜来做,但是我们先讲广搜的做法。
这个八数码问题来源于一个游戏大家玩过,就是在一个棋盘上面,
它有8个小方块,每个小方块上面有一个数字,数字就是
1到8,那还有一个位置就空出来了,空出来的位置你可以认为它是0,那
其他的数字它可以跟这个0交换位置,就是你可以把这个7移到这,
或者你可以把6移到这,都可以。就可以被别的数字来填充。
那现在我们就通过移动数字我们希望由初始的这个状态,这边
这个对应的数字就是这样,通过一系列移动数字,
把它最后变成这个终止的状态,那么要求一个 步数最少的解。
那我们从这个初始状态出发
我们可以通过移动数字可以到达各种各样的其它状态,
那我们就把这个所有状态的集合我们称之为这个状态空间,那一个问题它的
状态空间有多大,这个问题的复杂度是紧密相关的。
那我们解决这个问题的方法
就是搜索,那假设我们想用广搜
来进行处理的话,那么我们就会从这个初始节点
开始往下进行扩展,广搜的思路是
逐层扩展,先把层次低的节点给它扩展出来,再扩展层次高的,这时候我们第一层就一个节点,
然后第一层就初始状态的节点走一步, 经过用一个数字就能到达的那个状态我们就称为第二层节点,那现在我们看到
第二层的节点一共有两个,一个是右移下来,一个是把7向右移,得到这两个节点,
然后从第二层的节点再往下扩展第三层,在这个
节点往下走我们又把6移上去了又得到一个第三层节点,当然它在前面重复掉了,所以要去掉它,
但是我们在第二层的节点里面把1往左移,往右移,得到一个新的节点,
然后把这个2往下移,
把这个3往下移,就得到一个新的节点,
这个就是扩展的过程。那我们一层层扩展下去,如果
在扩展出的某一层节点里面包含了那个目标状态节点,
那就说明我们已经达到了从开始节点
到目标节点的哪条路径,而且这个路径一定是最短的, 那我们具体做广搜的时候肯定要用队列来保存这个
待扩展的节点,开始里面就有这个初始队列,然后
我们把队首的节点拿出来,然后把它的
把拿出来的这个节点进行扩展,把扩展出来的节点
放到队伍里面去。如果最后我们从这头拿出了那个 目标状态的节点,那问题就解决了。
那广度优先搜索解决这个问题呢,
代码当然就是先初始化队列,然后只要队列不为空,而且还未找到目标节点,
我们就取队首的节点扩展,并且把扩展出的非重复节点放到队尾,
然后在这个题目里面我们一定要记住每个节点的父节点,因为题目并不是只问你
你从开始状态走到那个目标状态1,2,3,4,5,6,7,8,0,需要多少步, 它还要求你把这个
具体走得步数,怎么走的都要复述出来,所以你要记住这个
走的每一步都是怎么走的,当然你要记住这个
当前这个节点从哪一个节点过来,就是每一个节点的父节点我们都要记住,
我们知道广搜的时候我们一定要做判重。就是我们从一个
节点能够扩展出一些节点出来,可是它扩展出来的一些节点
有的可能已经跟前面扩展过的节点,是重复的, 比方说,我们这个第二层的这个节点,我们
把这个数字6向上移,就会得到这个一个节点一个状态,
但是我们会发现,这个状态跟前面那个初始状态根本就是一样的,
那我们当然就不需要这个状态,直接把它扔掉,
不会把这个状态塞到队列里面,所以我们会需要判重,就是我们能有手段知道,给定一个状态
这个状态在前面到底有没有扩展过,我们能够搞清楚这点,
那现在我们这个问题
用广搜来处理的话我们需要在队列里面存上一大堆的状态,
那整个问题的状态数目是相当大的,我们要用队列把它都存起来会很费空间,
那我们就要想点办法节省这个空间,节省队列需要的空间,
然后我们还要想办法就是我们怎么样来快速的判断一个状态是否前面已经扩展过,也就说是否重复,
那这个时候如果我们多用一些存储空间我们就会节省时间,
我们多,这个我们如果愿意多花一点时间,
说不定我们需要的存储空间就会比较少一点,需要做权衡。
那现在第一步要解决的就是我们要把这个状态给存到队列里面,
那一个状态就是这个这些棋盘上数字的一个排列,我们用
什么形式来存放一个状态呢?先看方案一。
方案一是最简单的,谁都能想得出来,每个状态就是一个字符串,
这个棋盘呢,这种格局我们就认为它是字符串,8,2,3,4,1,6,5,7,0,就OK了,
每个状态用一个字符串存储,那每一个状态它就需要9个字节,
这个是非常的浪费的,
和现在的导向。那我们采取方案二,它能够 节省一半空间,还iii方案一。
那我们看到这棋盘上的东西我们可以
把它看做一个数,这块就是0了,
我们可以把它看做一个数,就是我们把每一个状态看做一个九位数,这九位数十进制的,那这个九位数
最大值是多少呢?当然就是876543210,那这个876543210它是小于2的31次方的,
所以说我们用一个int就能够表示出一个状态。
这样我们一个状态,原来我们是用一个字符串的形式表示的,太浪费了,我把它看做一个整数,看做一个int类型的东西,
那么我们只需要4个字节就能够把这个状态给表示出来。
好,那我们在此就已经解决了状态的问题 但是还有新的问题。我们要
对状态进行判重,给定一个状态我想知道这个状态在前面是不是出现过,那怎么办呢?我可以定义
设定一个标志位序列,每一个状态让它对应一个标志位序列中的一位,
那这个标志位为0了,当然就表示这个状态还没有被扩展过,为1就说明它前面已经扩展过,不要在用它了,
我们可以用一个字符数组A来存放这个iii的标志位,
那字符数组每个元素都有8个比特,那就可以存放8个状态的标志位,
那我们一共有876543210位,那
我们数组里面有多少个元素呢?当然就是876543210除以8,不能整除,再加上1, 那就这么多个字节,就是
100M的一个数组,那你如果在iii上面iii,你100M的一个数组
那就会very exceeded,就是超出内存, 就过不了,在其他的一些iii里面就可能也过不了。
那在这种情况下如果某一个状态对应于数X的话,它标志位在哪呢,
那就是数组A的下标
为X/8的元素,在这个元素里面
第x%8这个位,反正这个数组太大了,我们现在得想办法
减少存放标志位的数组的大小, 怎么减少呢?我们想想看,
我们可以把每一个状态的字符串形式看做一个9位的九进制数,为什么可以看做九进制数呢,
因为这些数字里面没有9,最大就是8,所以我们可以把它看做一个九位的
九进制数,那这个时候, 这个最大的九进制数就是九进制的876543210
它相当于十进制的381367044,
那这个时候我们需要的标志位的数目就变成了这么多个,对吧,
那实际上就相当于47M这么大。
那当然比刚才那个方案要节省了一半的空间。
那用这个方案在III上面交上去也就能过了,不会超内存了。
但是呢,我们还是不怎么满意,我们还 希望内存空间要求更低一点,
用这种方法也是一样的,如果你一个状态对应数x,
那它的标志位依然还是跟前面那个方案算法是一样的,一个数
数是不分九进制十进制的,我们说它的大小,数x就是数x,
只不过这个它看到的这个表现就是我们iii九进制,
好我们想点什么办法进一步节省空间呢?
看,我们这个状态的数目实际上一共只有9个阶乘多个, 对吧,因为我们这里面有8个数字,
有9个数字,0到8然后我们数字是不会重复的,
那所有的状态数目就是这个9个数字的排列组合,那当然一共就只有9个阶乘,9阶乘这么多个,那9的阶乘是多大呢?
是这么个数字,是36万多
那一共只有36万多个状态,结果我采取方案二的表示方法
却需要这个,这么大一个数字的这儿么多的标志位,当然是明显很浪费的,对吧
为什么会有这种浪费啊,我们为了要实现状态
和这个标志位的对应关系,那么这对应关系是在这了
我们就可以给一些根本不存在的状态也分配了标志位,比如说对于9个6
这样的一个9进制数,它其实根本不对应我们任何一个状态 可是对这样一个东西,我们也一样在数组里面给它分配了这个标志位
而且我们这个标志位数组里面有大量的标志位实际上都是
不可能对应到任何一个合法的状态的,那也就是说都浪费掉了 好,那我们怎么样来避免这种浪费呢
也就是说一共只有9这个阶层,这么多个状态,那我们
也就只需要这么多个标志位就行了,我不需要多余的标志位,对吧
所以说我们用到了这个方案四,这个时候呢我们可以把每个状态都看做数字0到8的一个排列
那这个排列一共有9的阶层个,对吧
那我们可以给这些排列分大小的,比如最小的一个排列
就是0,1,2,3,4,5,6,7,8,最大的那个排列就是8,7,6,5,4,3,2,1,0。
啊这个排列的大小我们可以认为就是这个排列所对应的那个数,或者它的字不算的这个大小
字不算有字典序嘛,那这样就是说,一共有9个阶层排列,那每一个排列依据其大小就会有一个序号
那么给定一个状态,它对于一个排列
那这个排列呢,我们可以把它的序号给求出来,这个序号就是这个排列在全部排列中的位置
那这个时候一个状态我们就可以用一个
排列的序号来表示了,一个状态对应一个排列,我们算一下这个排列在所有排列里面是第几个
这个它的序号就代表了这个状态 那我们状态总数就是总排列数
那这个时候我们看从这个标志数组a当中就只需要这么多个比特就可以了
那这个时候如果某一个状态它是一个排列对吧,然后它的排列的序号是x
那这个时候,这个状态所对应的标志位,它在哪呢,它就在数组
a x除以8这个元素里面它的第挪8位
这样的话,我们就大大地节省了空间
那在状态如何表示这个问题已经解决以后,我们还需要解决状态转移的问题
就是说我们如何从一个状态经过一步移动,变到另外一个状态 那如果状态它是int形式的话
我们很难在这个int形式的状态下面进行操作说一个int形式状态,比如说把其中的一个数字往下移了
它变成另外一个Int形式的状态,这直接变的话怎么变啊,首先一个int形式的状态在那
你都不知道这个int形式的状态里面那个空格,就是那个0的位置到底在哪,对吧
所以说,我们在进行状态间转移的时候,会需要先把int形式的状态
在排列状态的序号,把它装换成字符串形式的状态
然后我们在字符串形式的状态上就可以进行移动了
因为字符串形式的状态已经在那了,是很明显的对吧,然后变成新的状态,我们无非就是
移动0的位置,可以把0向左向右或者说向上
向左移动三个位置,或者向右移动三个位置,或者左移一个右移一个对吧,总之就是移动0的位置
那移动0的位置以后呢,我们就得到一个新的字符串形式的状态了
然后呢我们要把这个新的字符串形式的状态再转换成int形式的状态,这个int形式的状态就是
排列的序号啊,字符串形式的状态就是排列
那这样我们当然就需要写一个
给定一个排列,这个排列是字符串的形式,我们要求这个排列的序号的函数
我们另外还需要写一个,我给定一个序号,让你求
该序号的排列的这个函数,这是我们都需要做的 那下面我们看
对于整数1,2一直到k的一个排列,假设它是a1,a2,a3,ak啊
现在要求这个排列的序号 那你怎么算呢,这个基本的思想当然就是,我们算一下有多少个排列以我给定的
这个排列要小,假设有N个,那么我们这个排列的序号当然就是N+1
是吧,那好,那我们现在就要找出来,哪些排列它会比我给定的这个排列序号要小呢
那当然我们如果在最右边的,最左边的这一位就是第一个位如果我们不放a1,要放
从1到a1-1这样的数的话 那产生的排列,肯定都比你给定的这个排列要小,对吧,那我
意思说我要先算一个,如果我a1的这个位置,最左边这个位置,也就是第一位
放的是1到a1-1,那在这种情况下,能够产生多少个排列,有多少个排列啊
那当然就是a1-1这是第一位的算法,再乘以k-1的阶乘
k-1的阶乘是什么,就是你确定了这一位的情况下,剩下那些位的排列数目,当然就是k-1的阶乘,对吧
那就是我们现在,把1到a1-1,
这几个数我们都可以放在a1这个位置,然后这种方法以下,就可以
产生出这么多个排列,要比你给定的这个排列要小
接下来如果我a1不变,就是这个东西
但是我把a2变小了,我又可以产生出一些排列,比你给定的这个排列要小
对吧,也就是说这个时候a2我们可以选择1到a2-1都放在
这个位置,而且这个时候呢当然我们要注意啊,这个1到a2-1里面你不能
1到a2-1里面如果它已经出现在a1了,那你就不能再搁在这了,对吧,总而言之吧,我们在
替换某一位的时候,这个左边已经出现过的那些,我们就不能再用了
然后我们再算,1到a2-1放在第二位,会有多少个排列
当然最多是这么多了,对吧,假设1到a2-1前面都没用过,那就会有这么多个排列
然后我们再算算a1,a2不变,然后1到a3-1放到第三位,然后会有多少个排列
然后把这些排列全部加起来
就算出了比别的排列要小的,所有的排列数目 那当然这个排列的序号也就求出来了
那我现在以这个3241,给定的3241这个排列为例,让你求
它的序号,你怎么办呢?那你首先就看,我可以把1和2放在
第一位 这个时候能产生多少个排列呢,当然就是2乘以3的阶乘,这么多排列,有12种
那这12种,都比3241要小,现在我们就是3不变,3还是放在第一位
但是我把第二位这个2可以换成一个更小的,那我可以把1放在第二位
那这个时候,有多少种排列呢,产生出多少种排列呢,当然后面两个数字的组合就是2的阶乘种
在这种情况下有两种排列,然后现在我们2的这个位置也不变,然后我把1
我把这个1放在第三位
这个第三位本来是4
你可以考虑把3和2都放在第三位,但是3和2前面都已经用过了对吧
所以你只能把1放在第三位,这个时候呢,就会产生一种新的排列,有一种
然后再往下就没有什么可以换的了 所以我们把前面这几种全部加起来,一共是15种
这15种排列,都是比3241要小的,所以3241呢就是第16个排列,它的序号就是16
当然你算排列序号的时候有的时候你可以从0开始算,有的时候你也可以说从1开始算,这个在程序里面一般都是从0开始算
那我们怎么样这种求这种给定排列求序号时间复杂度是on平方的
那还要解决的一个问题就是
如果我给定了一个序号,需要你把这个排列给我算出来
排列就是字符串形式的,那比方说
1,2,3,4这四个数,它有一大堆的这个排列,对吧
其中最小的那个就是1,2,3,4,它是第一号
现在我让你把第9号给我找出来,就是第九
第九小的那个排列给我找出来那你怎么办呢,
你不能去吧所有的排列阶乘都算出来然后再排序,那肯定是不行的对吧
所以我们具体的算法就是我们去测试每一位到底应该放什么
比如说第一位,对于第一位我要试试它到底放的是什么,我们假定第一位放的是1
如果第一位是1的话一共会产生3阶乘种排列,对吧 第一位是1的排列一共有3阶乘种这么多,3的阶乘是6,它没有到达9
所以我们第一位是1的话,肯定就到不了第九号了,对吧
第一位是1的那些所有排列,它是到不了第九号的,那所以第一位它至少是2
那我们第一位如果是2的话,
就第一位是1和第一位是2所产生排列一共有3的阶乘加3的阶乘这已经超过9了
就是第一位是1以及第一位是2的排列,加起来一共有
有这个 12种,它超过9了,所以这时候第一位肯定就是2,你不能是3
对吧,如果它第一位是3,它序号肯定就已经大于9了
所以第一位肯定就是2,那我们就已经确定了第一位是2,了是吧,接下来我们就需要确定第二位是什么
这个过程是类似的,我们讲,假定第二位是1 那第二位是1,那排列其实就是21什么什么
那这种形式的排列我们一共能数出2的阶乘个
然后再加上前面第一位是1的情况下排列有3的阶乘个,那我们数出来的排列一共是
3的阶乘加2的阶乘一共是8个,那还不到9,所以我们第二位至少是3.
第二位是3,那排列顺序是2,3 这时候我们一共数到多少呢?前面第一位为1的时候有3!种,
然后这个第一位为2,那第二位为1的情况下
又有2!种,然后以2,3开头的时候
一共还有2!种,这全部加起来已经大于等于9了,
所以说这时候第二位肯定是3,如果你第二位是4的话,它的序号已经是超过9了,
好,那也就是说我们已经确定了第二位,然后再看第三位,第三位我们先试试1,
看看行不行,如果第三位1的话我们能够数出来的这个排列数已经有了3!+2!然后再加上
再加上1种,那这个时候算出来的序号正好是9,所以这时候第三位就是1了,
那第四位跟着出来就是4了,那我们就没法数,
所以这个时候答案就是我们求出来的这个第9号排列就是2,3,1,4,
这个过程时间复杂度就是O(n2)的, 那总结出来就是我们在做搜索题的时候要表示状态,
我们可以采取节省空间的方式来表示状态,
当然我们要用节省空间的方式表示状态的话你在状态转移的时候可能就要多花一些时间去把状态给它
解码出来,比如说,在这个问题里面
就是把整数形式的状态,就是序号变成字符串形式的状态,就是一个
排列,而且还要把字符串形式的状态排列变成它的整数形式的序号, 这部分过程需要花时间,对吧,
那如果我们不是用排列序号的办法,给这个状态编码,而是用
直接用九进制数的方法给这个状态进行编码的话,
那我们从这个整数形式的数,它是个九进制数,把它变成字符串形式
的这样一个,我们要从整数变成一个字符串形式的九进制数, 这个所花的时间是怎么样的呢?是O(n)的,
它的性质上就给你一个int,把它变成
十进制的一个字符串,它的复杂度是一样的,对吧,
就是,比如最后变成留几位,
复杂度就是O(n)的,那我们刚才这个由排列的序号变成
排列,它的复杂度是O(n2)的,那相比之下
我们采用排列序号这种节省空间的存储方式实际上会带来更多点的时间开销,
那也就是说反正我们要权衡时间和空间,
对吧,多花点时间节省空间或者多花一点空间节省时间着看你的需要,
如果状态数目很大我们就要用好的编码来换取空间了,
那刚才举的这个题目我们用九进制十进制数还是
排列,它所花费的状态的这个 花在存储状态上的存储空间是一样的,
但是花在存储标志位上的空间它是不相同的。
那现在我们再回到 这个题目要看看怎么来写程序了。这个程序是挺复杂的。
那这个题目呢在P0J1077它的输入数据就是
9个数,其中有一个实际上就代表空格的这个位置,那当然就3个数字第一行,这三个数字第二行,这样话,
然后它要求你是输出一个结果,这个结果呢是一个移动序列, 当然这个移动序列去移动0
就是空格的位置,就会最终走到我们想要的12345678,就是说输入样例
就表示最终这是0,那移动序列里面u就表示空格,也就这个0向上移,
d就表示使空格向下移,r表示空格向右移,l表示空格向左移,
你最终要输出一个这样的这个序列,这个序列要求它是最广的。
那当然这个也可能会不为1,那在服务器这边会iii,它只要看到你的解
真的是最短的,而且按照这个序列走一遍能够达到想要的结果,
嗯 那在具体讲程序之前我们还要看一下
就是这个八数码的问题。它规定总是有解的。
就是说给你一个初始的状态,它 并不见得总是能够通过移动数字变到这种目标状态。
呃,那怎么证明这个事情呢?
就是说我们可以把这个排列,八数码的一个状态就是一个排列,对吧,
这种排列我们可以分成奇排列和偶排列两种,
现在有一个结论就是从奇排列不能转换成 偶排列,偶排列也不能转换成奇排列,
那也就说如果你的目标状态是一个偶排列的,那你给的初始状态是个奇排列的,
那我们就认为这个问题无解了。
那到底什么叫偶排列什么叫奇排列呢,就如果一个数字0到8的随机排列,
比如说,随机排列, 然后我们可以用f(x),这个X是不等于0的,
用F(X)表示数字X,前面比他小的数的个数,
那么全部数字的F(X)之和SIGMA
F(X) 如果这个SIGMA F(X)是个
奇数,我们就称这个排列为奇排列,如果这个 Y=SIGMA F(X)它是一个偶数,我们就称该排列是个偶排列。
那比方说对于一个排列871526340,怎么算它是奇排列还是偶排列呢?
我们就要看8这个数,它前面有,它的F(X)是多少啊?它的F(X)就是左边比它小的
数的个数,那就是0,然后7左边比它小的个数也是0, 1对应的F(X)也是0,然后到5呢,
前面比它小的数有一个,所以5的这个F(X)是1,然后2,
F(X)是1,3呢它前面有 6,他前面有2,1,5比它小,所以它的F(X)是3,
然后对于3来说,前面有1,2比它小,所以它的F(X)是2.
然后对于4来说,它前面有1,2,3比他小,所以它的F(X)是3,
那0这个东西我们不算它了,对吧,然后我们就把这些全部Y 加起来就是10,所以这个时候这个871526340就是一个偶排列。
那对于871625340呢,这块 我们同样的办法可以算出来等于9,那这个东西就是一个奇排列。
那我们记住这个结论,就是从奇排列我们不能 通过移动0的位置把它变成偶排列,
从偶排列我们也不能通过移动0的位置把它变成奇排列,那么 我们在八数码求解之前
我们就可以先判断一下,初始状态和目标状态排列的奇偶性是否相同,
相同的话我才去想办法找解,如果
不相同的话那就是无解 了。就是相同的话也许有解,不相同肯定无解。说的是这样的。
那下面我们来证明一下这个八数码有解性的判定,实际上我们要
证明的就是如果你移动0的位置它不会改变排列的奇偶性,
原来的排列是这样,0在这,那我们0,如果你把0左边移一下,或者右边移一下,
这肯定不会改变排列的奇偶性,对吧, 因为0我们不算,你把另外一个数放在0左边和右边
不影响整个的奇偶性,那
我们再考虑的就是0.向上移动或者向下移动的情况。那我们假设0是向上移动的,
那肯定就是跟a2交换位置,变成这样了。那现在我们就要考察整个排列的奇偶性
有没有发生变化。实际上就是说这三个元素,a3,a4,a2这三个元素它的F(X)是有可能发生变化的。
那我们只需要分三种情况讨论。三种情况就是a2,
比a3和a4都小,第一种情况,那如果a2比a3和a4都小的话, 那我们看到,把a2换过来,那我们
显然这个a2的奇偶性,a2的F(X)是没有什么变化,
但是a3和a4的F(X)值都各减少了1,
那一共就减少了2,整个排列的奇偶性并没有发生变化。
而第二种情况就是a2它比a3大,但是比a4小,
在这种情况下我们把a2移到a3,a4后面来,
这个时候a3的F(X)值没有什么变化,a4的F(X)值
它少了1,但是a2的F(X)值
它由于前面有个a3,所以加了1,因此整个排列的F(X)值是SIGMA F(X)实际上
是没有变化的,也就是奇偶性是不变的。
那第三种情况就是a2比a3和a4都要大, 那这样的话你把a2弄到这个位置,那
就是a3,a4的F(X)变化,但是a2的F(X)值呢,
加了2,当然整个排列的SIGMA F(X)值也是奇偶性不变的。
所以就证明了八数码问题的有解性判定。
移动一个位置不改变序列的奇偶性,也就是奇排列不能变成偶排列,偶排列