好,下面我们就要看这个八数码问题的单向广搜 就是一般意义上的广搜的一个程序, 这个程序比较,效率是比较低的,那么我们把它 交到POJ上呢它运行了891毫秒,但是POJ上这个题 它的数据是非常弱的,它就一组数据,那在III HDU的 III上面也有相同的一道题目,但是它的数据很强, 你把这个数据在iii去交就会超时,那具体怎么让你的程序在iii上面也能过我们后面还会再讲, 我们先看这个简单的这个广搜, 首先我们需要一个全局变量,goalStatus它是代表目标状态,这一个状态就是一个排序号,是吧, 好我们需要一大堆的标志位,一共有362880这么多状态, 所以我们需要的标志位就是这么362880这么多个,那我们用一个biset来存放这个标志位, 是最合适不过了。这个标志位是用来表示一个状态是不是已经被扩展过, 然后这个MAXS是我们所需要队列的最大的 存储空间,因为这个问题,所有的状态也就是六万多个, 所以我们这个队列哪怕把所有状态都放进去,队列四十万个元素也是不够的, 这个result是移动的结果,就是我们求出来的解就是一个移动序列, 放到这个result里面去,然后接下来这个Node就是我们要塞到队列里面去的 那个东西了。这个Node它一个程序变量status当然就是状态, 就是一个排列的序号,编号,然后这个father就是父节点的指针, 通过 father我们就能够知道刚才是从哪一个状态走到当前这个状态的。 move是代表移动的方式,它记录的是从父节点到本节点 它的移动方式,就是空格移动,就有可能是 u/d/r或者l,这是它的构造函数,下面这就是一个队列, myQueue,一个队列,这个队列是预先分配好空间的数组, 我们这个题目里面不能说真的把元素从队列里面把它删掉, 所以我们必须要用数组而不能用那个sdl的Q或者DQ, 然后这是有一个队头的指针,队尾的这个指针, 呃, 这是一个常数的字符串, 它代表了四种动作,udrl,把它存放在一个数组里面方便取用, 然后这个东西是个数组,它存放了0到20的阶乘,我们 仔细看,我们会发现在前面从排列求序号,求序号排列的时候 都要不停的用到一个数的阶乘, 要用某一个数的阶乘,这个数值,那这个 阶乘我们不能算N的阶乘我们用到的时候就去重新求一遍当然就很累,对吧,我们正确的做法就是事先把各种 阶乘的数字都已经算出来,给他存在数组里面,需要了直接拿它就行了,那为什么只存了 21个阶乘呢?我们在这里存放了0到20的阶乘, 因为21的阶乘,用unsigned int已经放不下了,就不管他了。 实际上我们在这个题目里面最多就用到9的阶乘就完了,对吧, 所以我们算21的阶乘就足够了。这个GetPermutationNumForint函数 它的参数perint是一个整型数组,里面放着一个 从整数0到n-1的排列, 这个排列就是由整数0,1,2,3一直到n len-1, 组成的,那这个函数就会告诉你, perint里面放的这个排列是第几个排列,那我们说到第几个排列的时候我们是从0开始算的, 也就说这个0 1,2,3,4,一直到Len-1这就是第0号排列, 我们这个函数求perint里面放的那个整数的排列是第几个, 当然我们对len就不能超过21,因为我们用到了factorial这个数组它最多只有 算到20的阶乘,那这个程序,这个函数它具体的做法是跟我们前面讲的那个 给定排列求编号的思想是一致的,所以就 不仔细说了。这边还有一个函数模板,叫做GetPermutationNum, 它的作用就是说,这两个东西 你可以认为是一个迭代器,这个是整个排列的长度,它的作用是 给定一个排列求序号,那这个时候,在 s1到s1+len这个左闭右开的区间里面,放的都是第0号排列, 那这个排列它不一定是整数的排列了,也可能是字符串,也 可能是字符的排列,甚至有可能是对象的排列,我们这个区间里面放的东西是什么东西都可以, 只要能每一个元素都不相同,元素之间是能够比出大小来就可以。 那现在我们 就是说给定了一个第0号排列是什么样子的,然后又给了另外一个排列, 让你把另外一个排列它的序号给它求出来,那我们 需要知道第0号排列是什么样否则我就不知道这个 区间里面放的那些元素到底哪个大哪个小了,对吧?所以我们会需要第0号排列iii。 那在做这个GerPermutation的过程中我们会需要把这个 s1和s2所代表的排列要把它转换成0到len-1这个整数 的排列然后我们算出这个序号, 这具体的过程也跳过去不讲了,同学们自己回去看。 下面这个函数模板GenPermutationByNum 从名字上看我们就知道它是要给定一个排列的编号,你把这个排列给算出来 但它具体的用法呢就是s1和s2是两个迭代器,然后在这个左闭右开的区间s1到 s1+len里面放着第0号排列,你得给我第0号排列我才能算出其他编号的排列。 然后这排列的长度是Len,然后告诉你要求第Num号的排列,你求出来的第Num号的排列就放在 从s2开始的地方,那么这个 程序,这个函数它的做法 跟前面说的给定编号求排列思想一致,所以我也不再细讲, 但是这个是一个函数模板,所以 在这个s1到s1+len这个排列里面可以放各种各样东西的排列, 比如说字符的排列,甚至一堆对象的排列都是可以的,你只要把第0号的排列给出来,我就能 求出第Num号的排列。好,然后还有一个重要的函数叫做StrStatusToIntStatus, 这个就是把字符串形式的状态也就是排列转换成整数形式的状态也就是排列的序号, 那在这里是字符串形式的状态,那我们就调用GetPermutationNum 然后进行求得它的序号,那我们在求这个序号的时候,这个序号给出第0号排列, 第0号排列就是012345678,那显然这个排列里面的每一个元素都是一个char,一个字符, 第二个参数就是一个 字符数组里面放着你想要求序号的那个排列,第三个参数9就说明这个排列是9, 然后我们再看这个IntStatusToStrStatus就是把整数形式的状态也就是排列的序号 转换成一个字符串形式的状态,也就说这个序号所对应的那个排列,就是求第N号排列,求出来 的结果我们放到这个字符数组StrStatus里面去,所以 我们在这里就调用GetPermutationByNum,它的第一个参数就是0号排列, 是12345678,然后告诉你排列的长度是9, 然后这个需要求第n号排列,那么你求出来的排列结果放到 这里面去。好,在接下来看另外一个函数叫做NewStatus,这实际上就是做状态转换的函数, 它的参数是一个状态,以及一个移动方式, 它的返回结果是一个新 的状态,就是从NStatus经过cMove这种 移动以后能够产生的新的状态把它算出来, 返回,这个新的状态也是整数形式的,那当然有的移动是不可行的, 比方说空格已经在最右下角了,你还要再向右移动一下,这个移动就不可行,不可行的话我们这个NewStatus返回值就是-1, 好啦,那在这里面呢,首先需要把这个整数形式的Status状态 把它变成字符串形式的这个状态,就是一个排列, 现在我们要用IntStatusToStrStatus算出了 这个整数形式的状态所对应的的字符串形式的那个状态 就是一个排列,接下来我就可以在这个字符串形式的状态上面 来进行cMove这种移动了。 当然我们在这里还需要把这个0的位置给它找出来,就是那个0到底在什么位置, 我要把它给找出来,啊,就返回了这个空格,就是0的位置,然后我们就看 这个移动是怎样的,移动不是有四种吗?就是空格可以向上,向左,向右,向下移, 所以有四种,如果这个移动是u就代表我要把空格向上移, 那如果空格已经在第一行了你肯定就不能向上移,所以我们通过这个空格 就是0这个位置判断一下如果-3小于0就说明它已经在第一行了,那你就不能再往上移了, 那我们就返回-1,如果不在第一行,那我们就可以把空格向上移, 是什么意思啊,那无非就是把上一行的那个数字 给它移到,换到空格的位置来,对吧,那上一行的数字 如果空格的这个下标是ZeroPos的话,那它上一行的这个数字的下标就是 ZeroPos-3,所以我们在这里实际上就是 做一个两个元素的交换,如果这个移动是d就代表空额要向下移, 那我们当然也要判断一下这个空格是不是在最后一行,如果是在最后一行,那就返回-1,否则 否则就向下移啊,那至于向左向右的做法也都是类似的,我们就不管它了。 那么程序执行到return之前,我们就得到了一个szTmp。 这个szTmp就是 从nstatus这个状态经过一个移动以后 生成的一个新的状态,只不过这个新的状态呢,是字符串形式的 那我们这个函数要求返回整数形式的这个状态,就是这个字符串形式的 排列所对应的那个序号,因此我需要再调用strstatus tolntstatus 把这个字符串形式的状态转换成整数形式的状态,就是 排列的序号,那接下来我们就看最重要的这个核心的函数叫做bfs 那就是官渡优先所搜,这个函数就会寻找初始状态 从初始状态nstatus,到目标的这个路径,目标前面已经看到了,就是gostatus,是一个整数 那初始状态也是一个整数,他就代表了一个排列的序号。 那一开始我们就把所有的这个标志位都reset,就全部清零 然后我们让对头的指针 它的数值是零,就等于指向队列数组的 下标为0的元素,然后队尾的这个指针它的值是1。 那如果然后我们现在把这个 第一个元素放到这个对列里面去,这第一个元素是什么 就是初始状态,对吧,然后初始状态是没有那个负节点的所以负节点指针这块我写-1 然后这个0,就意味着 0本来应该是从别的状态移动到当前状态所需要那个 移动的方法,对吧,那我们初始状态也没有好说的移动方法了,直接就是让它是0,反正就没有用的啊 就是字符0把,好,那现在初始状态就被放到队列里面了,然后接下来我们每次都要从队列里面取出一个 元素,进行扩展,一直做到对头的元素就是目标状态我们这个 任务就完成了,那只要队列不为空的话,我就会取出对头元素进行扩展。 队列什么时候是空的啊,只要 队头指针和队尾指针没有指向同一个地方,那队列就不为空。 因为队尾指针指向的是队列最后一个元素的后面。 好,只要队列不为空我就拿出队头的元素, 啊,我们先拿出队头元素的这个状态,对吧? 然后这个nstatus如果等于这个 gostatus,那就说明对头这个元素实际上已经代表目标状态了 这个时候,我们就return true,return true第一位置,这个bfs是成功的,就找到了一个解,那找到解以后 这个具体的每一步的移动过程是怎么样,实际上在这个 对列里面还是有存放的,都记录下来了,我们在那个里面可以从这个对列里面把 每一个移动步骤都给它恢复出来,在这bfs这里,反正我们找到了 目标状态我们就return true,如果我们 队头的这个元素它的status并不是目标状态,那我们就要 把队头元素拿出来进行扩展,对吧,怎么扩展呢 那首先我们就要从队头的这个元素的状态 进行各种移动,算出新的状态,那移动一共有四种,所以我们就用一个循环来尝试四种移动。 那我们这边移动的方式就存放在sz4moves,那这个字符数组一共有4个元素 分别就是u ,l,r,d之类的,对吧,那我们便利这个数组 实际上就是在尝试4种不同的移动方式,那这个 newstatus,nstatus,smy就是说通过第r种 移动,通过第r种移动 能够从nstatus变出一个新的状态,这个新的状态就是newstatus 然后我们看如果是nstatus等于-1,那就说明刚才这个 bi种移动是不可行的,那我们就continue就尝试下一种移动 或者说如果这个newstatus所对应的这个 标志位,如果为错,就说明这个newstatus它已经被扩展了 过了,那我们也不能让它入队列,所以就直接continue,再试下一种移动,看看能产生什么新的状态 好了,如果前两条都通过,那我们就认为这个newstatus确实是一种新的不重复的状态; 那我们就要接着就要把Nstatus给它 额这个放到队列里面,在放到队列之前呢我要设上一个扩展标记,就意味着就是说 newstatus这个状态已经扩展过了,接下来就真的把nnewstatus这个状态给它 放到队列里面去了,放到队列里面的方法就是 myqueue就是queue所指向的那个位置,放在队尾指针所指向的那个位置 然后再把队尾指针给它++,那我们放进去的就是一个新的node,新的节点 这个节点它的状态是nnewstatus,然后它的负节点是谁 负节点当然就是对头,的这个元素对吧,就是对头这个元素 对头这个元素它在myqueue里面的下标就是qhead,在这里所谓负节点的 指针指的就是负节点这个元素在myqueue里面的下标 现在nnewstatus它的负节点是什么,就是 这个myqueue,qhead.status所以负节点指针就是qhead了 那 从负节点是通过哪一步的移动跑到这个newstatus的呢?那当然就是 这个sz4movei,对吧就是这个东西,刚才是通过第r种移动过来的 这就完成了新的节点入队列,那接下来要做的事情就是要把 队头的元素给它删掉,对吧,那我们就简单地把qhead++就行了 这个队头元素还的放在队列里面,在那里面还要去用的,我们不能把它真的给它扔 掉,但是我们把对头的指针++就意味着哎,现在队头变成下一个元素了,就等于是把对头的元素 给它删掉了,那 如果整个循环执行完了,对列都空了,还没有从return ture这里返回 那就说明我们最终没有走到这个目标状态 那也就是说问题无解,就返回一个force,这个就是重要的bfs 那总算讲到这个main了,好累啊,感觉不会再look了 好我们看main里面,一开始要把这个各种数字的阶乘都算出来,我们一直算到了20的阶乘 然后呢我们要这个 取得这个目标状态,这个目标状态是什么,是1,2,3,4,5,6,7,8,9,0 7,8,9,0,这个字符串的形式,它所对应的这个编号,所以我们算出了这个目标状态。 然后我们用这个,呃, 两个字符数组用来读取这个数据 那我们就一行一行的读 ,一行的话里面就是一个 初始状态了嘛! 然后初始状态里面是有x的,就是那个空格的位置是s的,所以我要在那个里面做一些转换 把x给它替换掉,然后呢总之这个时候我们就获得了 字符串形式的初始状态,里面x被替换成了0. 呃,然后呢,我们接下来要判断的就是 这个问题到底有没有解,就是用这个初始状态和 这个目标状态的奇偶性 去判断是否有解,排列的奇偶性去判断是否有解,这个一大段的东西我们就略过去不讲了。 啊,如果这个两个排列的奇偶性是不一样的 那我们就输出unsolvable,只有在两个初始状态 和那个中止状态它们的奇偶性相同的情况下,我们才需要去做进一步的这个求解。 那我们求解的过程就是这个bfs,就是做这个 管道有限搜索,这个时候那个初始状态的字符串形式是放在szline2里面的 我们要把它转换成整数的形式,然后去调用bfs 这个bfs返回ture就意味着我们找到解了, 返回false就说明找不到解,那就会输出一个unsolvable。 那在返回ture的情况下,下面我们就要把找到的解给它输出,那怎么找 怎么去寻找从初始状态到中止状态的那个路径呢 那我们知道在找到解的时候嘛,这个队列的头部 那个元素实际上就已经是那个目标状态了对吧,那我们知道对列里面每一个状态 对列里面的每一个节点,里面除了存放着状态以外,还存放着 负节点的这个指针,以及存放着从负节点移动到当前这个状态所走的那一步到底是什么样的 所以好,现在我们看到,qhead这个位置,队列里面下标为qhead那个元素,实际上就是 目标状态,对吧,那么我们要从这个目标状态 负节点指针就能找到 达到目标状态的前一个状态,然后再沿着一系列的负节点的指针顺藤摸瓜,然后就能够找到了 从目标状态回馈到初始状态的那条路径。 这当然我们再顺着过来就,把这个从初始状态到目标状态的每一步的移动都能够给它输出了。 好,总而言之我们两个不是选择qhead就是目标状态 然后我们 用result这个数组来存放这个移动 一开始移动的步数是0,然后我们用 result数组来存放每一步的移动,它是一个字符的这个数组。 只不过我们存放result里面的是是移动序列的 倒过来的这个情况,比如result0存放的是最后一步 result1存放的是倒数第二步,倒着来的啊。 好,现在我们先找出最后一步动作是什么样的 最后一步动作当然就是移动到这个目标状态的那个动作对吧,我们知道这个 npos它是等于qhead的了,那myqueuenpos这个元素实际上就代表是 对应的是目标状态,对吧,那这个元素里面的这个move就代表的是 移动到目标状态那一个步骤就是一个Nmove,所以我们就把它给记下来了。 那接下来我们要找到到达目标状态之前的那个状态,也就是那个 目标节点的负节点,那目标节点的负节点 它当然也是放在那个对列里面,然后它在对列里面的下标实际上就是 这个目标节点,目标状态里面所对应的这个father 好,那现在我就把目标状态,它的负节点的 在这个myq里面的下标给它拿出来放到npos里面去了 如果这个npos不为0,那就说明刚才这个负节点并不是 初始状态节点,对吧,那我们还要接着倒回去找,一直要找到初始状态节点为止。 如果npos等于0,就说明我们已经回退到初始状态了,那整个过程就可以结束。 好,那现在我们取到了 上一个节点,它的这个在 myq这个数组里面的下标,然后我们就 继续在做循环,在这个循环里面的时候,又取到了到达上一个节点它的 这个一个步骤,然后再取得上一个节点的再上一个节点 总之这个循环,走完以后,我们就回退到了这个初始状态,并且这个 result里面就存放了所有的移动步骤。 只不过这个移动步骤是跟正确的顺序正好相反的,因此我们在输出移动步骤的时候就 倒着输出就对了,倒着输出就对了,那整个问题就 解决了,那我们整个程序的复杂度呢实际上它就是这个 最多也就是状态的数目,也就是大概40万这个样子,36万多