dw网站建设模板wordpress主题上的字怎么移动

当前位置： 首页 > news >正文

dw网站建设模板,wordpress主题上的字怎么移动,绵阳定制网站建设,建设网站需要什么人员八数码问题分析[转] 2008-09-06 16:06 问题简介#xff1a; 所谓八数码问题是指这样一种游戏#xff1a;将分别标有数字1#xff0c;2#xff0c;3#xff0c;…#xff0c;8的八块正方形数码牌任意地放在一块33的数码盘上。放牌时要求不能重叠。于是#xff0c;在33的数…八数码问题分析[转] 2008-09-06 16:06 问题简介         所谓八数码问题是指这样一种游戏将分别标有数字123…8的八块正方形数码牌任意地放在一块3×3的数码盘上。放牌时要求不能重叠。于是在3×3的数码盘上出现了一个空格。现在要求按照每次只能将与空格相邻的数码牌与空格交换的原则将任意摆放的数码盘逐步摆成某种特殊的排列。如下图表示了一个具体的八数码问题求解。 问题分析         首先八数码问题包括一个初始状态(START) 和 目标状态(END)所谓解八数码问题就是在两个状态间寻找一系列可过渡状态START-STATE1-STATE2-…-END。这个状态是否存在就是我们要解决的第一个问题 Q1每一个状态及每一次操作的表示方法         有许多表示方法比如一个3*3的八数码盘可以压缩成一个int值表示但不适用于15 puzzle或大于8 的puzzle问题。如果对空间要求很高应该还可以再压缩。本文采用一个int表示的方法。         表示方法如下由于int的表示范围大于1e9所以我们取一个int的低9位为了方便寻找空格的位置int的个位我们用来放空格的位置1-9。而前8位按照行从上到下列从左到右的顺序依次记录对应位置上的数字。例如         可以表示成 2 3 1 5 8 4 6 7 5 个位的5表示空格在第5位前八位数按顺序记录。坐标转换公式为     num压缩后的int x y求x行y列,1记起1e(n)为 1乘10的n次     int temp(x-1)*3y     if temp num%10 then return (num / 1e(9-temp1)) %10     else return (num / 1e(9-temp) )%10     为了方便本文介绍取目标状态为1 2 3 4 5 6 7 8 9 即–         操作本文用 u r d l 分别表示 空格的向上 向右 向下 向左 四个操作。比如在简介中的图包括两步操作 l d 可能与平时玩这类游戏的习惯不符合但这是为了和ACM例题相统一。     对应地每种操作引起的状态变化如下     r num值          l num值–     u 有点复杂     int t0 9-num%10 1     int t1 num / 1e(t0)     int t2 t1%1000     t1 t1- t2 (t2 % 100) * 10 t2 / 100     t1* 1e(t0)     return (t1 ( (num % t0) - 3))     d return前面同u操作 return返回 (t1 ( (num % t0) 3)) Q2判断是否存在中间状态使START 到达END         用组合数学的方法可以快速地进行判断例如SOJ 2061题 2360题中都是关于此类的问题。但八数码的判断方法比他们简单多了。         本文用的方法是计算排列的逆序数值以2 3 1 5 8 4 6 7 5 为例子5表示的是空格不计算那么求23158467 的逆序值为         0 0 2 (12 13 ) 0 0 1 ( 45 ) 1 ( 68 ) 1 ( 78 ) 5 目标状态1 2 3 4 5 6 7 8 9 的逆序自然就是0。 两个状态之间是否可达可以通过计算两者的逆序值若两者奇偶性相同则可达不然两个状态不可达。 简单证明一下         l 和 r 操作不会影响状态的逆序值因为只会改变个位数空格的位置。         u和d操作是使某个位置的数字 右/左 移两位。 由于数字序列的每一次移动会使逆序值奇偶性改变所以            移动两次后奇偶性不变。         所以 四个操作均不会影响序列的奇偶性。 Q3如何寻找一系列的中间状态及遇到的问题         要寻找这一系列中间状态的方法是搜索但搜索很容易遇到时间和空间上的问题。以下就是搜索的基本原理         由1 3 7 2 4 6 8 5 2 状态可以衍生三个状态假如选择了1 2 3 7 4 6 8 5 5 则又衍生三个状态继续按某策略进行选择一直到衍生出的新状态为目标状态END 为止。 容易看出这样的搜索类似于从树根开始向茎再向叶搜索目标叶子一样的树型状。由于其规模的不断扩大其叶子也愈加茂密最终的规模会大到无法控制。这样在空间上会大大加大搜索难度在时间上也要消耗许多。 在普通搜索中遇到以下问题        a 搜索中易出现循环即访问某一个状态后又来访问该状态。        b 搜索路径不佳便无法得到较好的中间状态集即中间状态集的元素数量过大。        c 搜索过程中访问了过多的无用状态这些状态对最后的结果无帮助。         以上三个问题中a为致命问题应该它可能导致程序死循环b和c是非致命的但若不处理好可能导致性能急剧下降。 Q4怎样避免重复访问一个状态         最直接的方法是记录每一个状态访问否然后再衍生状态时不衍生那些已经访问的状态了。思想是给每个状态标记一个flag若该状态flag true则不衍生若为false则衍生并修改flag为true。 在某些算法描述里称有两个链表一个为活链表待访问一个为死链表访问完。每一次衍生状态时先判断它是否已在两个链表中若存在则不衍生若不存在将其放入活链表。对于被衍生的那个状态放入死链表。         为了记录每一个状态是否被访问过我们需要有足够的空间。八数码问题一共有9!这个数字并不是很大但迎面而来的另一个问题是我们如何快速访问这些状态如果是单纯用链表的话那么在规模相当大查找的状态数目十分多的时候就不能快速找到状态其复杂度为O(n),为了解决这个问题本文将采用哈希函数的方法使复杂度减为O(1)。         这里的哈希函数是用能对许多全排列问题适用的方法。取n!为基数状态第n位的逆序值为哈希值第n位数。对于空格取其9-位置再乘以8!。例如1 3 7 2 4 6 8 5 8 的哈希值等于 0*0! 0*1! 0*2! 2*3! 1*4! 1*5! 0*6! 3*7! (9-8)*8! 55596 9!         具体的原因可以去查查一些数学书其中1 2 3 4 5 6 7 8 9 的哈希值是0 最小8 7 6 5 4 3 2 1 0 的哈希值是9!-1最大而其他值都在0 到 9!-1 中且均唯一。 Q5如何使搜索只求得最佳的解         普通的搜索称为DFS深度优先搜索。除了DFS还有BFS从概念上讲两者只是在扩展时的方向不同DFS向深扩张而BFS向广扩张。在八数码问题的解集树中树的深度就表示了从初始态到目标态的步数DFS一味向深所以很容易找出深度较大的解。         BFS可以保证解的深度最少因为在未将同一深度的状态全部访问完前BFS不会去访问更深的状态因此比较适合八数码问题至少能解决求最佳解的难题。         但是BFS和DFS一样不能解决问题c 因为每个状态都需要扩张所以广搜很容易使待搜状态的数目膨胀。最终影响效率。 Q6该如何减少因广搜所扩张的与目标状态及解无关的状态         前面所说的都是从START状态向END状态搜索那么将END状态与START状态倒一下其实会有另一条搜索路径Q8策略三讨论但简单的交换END与START并不能缩小状态膨胀的规模。我们可以将正向与反向的搜索结合起来这就是双向广度搜索。         双向广搜是指同时从START和END两端搜当某一端所要访问的一个状态是被另一端访问过的时候即找到解搜索结束。它的好处是可以避免广搜后期状态的膨胀。 采用双向广度搜索可以将空间和时间节省一半 Q7决定一个快的检索策略         双向广搜能大大减少时间和空间但在有的情况下我们并不需要空间的节省比如在Q4中已经决定了我们需要使用的空间是9所以不需要节省。这样我们可以把重点放在时间的缩短上。         启发式搜索是在路径搜索问题中很实用的搜索方式通过设计一个好的启发式函数来计算状态的优先级优先考虑优先级高的状态可以提早搜索到达目标态的时间。A是一种启发式搜索的他的启发式函数f ()g () h () 能够应用到八数码问题中来。         g () —– 从起始状态到当前状态的实际代价g()的估计值g () g()         h () —– 从当前状态到目标状态的实际代价h()的估计值h () h() 注意两个限制条件         1h () h() 2任意状态的f ()值必须大于其父状态的f ()值即f ()单调递增。         其中g () 是搜索的深度 h () 则是一个估计函数用以估计当前态到目标态可能的步数。解八数码问题时一般有两种估计函数。比较简单的是difference ( Status a, Status b ) 其返回值是a 和b状态各位置上数字不同的次数。另一种比较经典的是曼哈顿距离   manhattan ( Status a, Status b )其返回的是各个数字从a的位置到b的位置的距离见例子。 例如状态 1 3 7 2 4 6 8 5 2 和状态 1 2 3 4 5 6 7 8 9 的difference 是5不含空格。而他的manhattan 距离是 1 (7d一次) 1 (2u一次) 2 (4l两次) 3 (6r两次u一次) 2 (5u一次l一次) 9 单个数字的manhattan应该小于5因为对角的距离才4若大于4则说明计算有误。         无论是difference还是manhattan估计为越小越接近END所以优先级高。         在计算difference和manhattan时推荐都将空格忽略因为在difference中空格可有可无对整体搜索影响不大。         本文后面的实现将使用manhattan 不计空格的方法。其实每移动一步不计空格相当于移动一个数字。如果每次移动都是完美的即把一个数字归位那么START态到END态的距离就是manhattan。反过来说manhattan是START到END态的至少走的步数。         回到f ()g () h ()其实广度搜索是h ()0的一种启发式搜索的特例而深度搜索是   f ()0 的一般搜索。h ()对于优化搜索速度有很重要的作用。 Q8能否进一步优化检索策略         答案是肯定的。         A搜索策略的优劣就是看h ()的决定好坏。前面列举了两个h ()的函数但光有这两个是不够的。经过实验分析在f ()中g ()决定的是START态到END态中求得的解距离最优解的距离。 而h () 能影响搜索的速度。         所以优化的第一条策略是放大h ()比如让h () 10 manhattan()那么f () g ()10*manhattan()可能提高搜索速度。可惜的是所得的解将不再会是最优的了。         为什么放大h()能加快搜索速度我们可以想象一下h()描述的是本状态到END态的估计距离估计距离越短自然快一点到达END态。而 g ()描述的是目前的深度放大h ()的目的是尽量忽略深度的因素是一种带策略的深搜自然速度会比广搜和深搜都快而因为减少考虑了深度因素所以离最优解就越来越远了。关于h ()放大多少是很有趣的问题有兴趣可以做些实验试试。         第二条是更新待检查的状态由于A*搜索会需要一个待检查的序列。首先在Q4已经提到用哈希避免重复访问同一状态。而在待检查队列中的状态是未完成扩张的状态如果出现了状态相同但其g ()比原g ()出色的情况那么我们更希望的是搜索新状态而不是原状态。这样在待检查队列中出现重复状态时只需更新其g() 就可以了。         第三条是注意实现程序的方法在起初我用sort排序f ()后再找出权值最大的状态而后发现用make_heap要更快。想一想由于需要访问的接点较多待访问队列一大那么自然反复排序对速度会有影响而堆操作则比排序更好。另一点是实现更新待检查队列时的搜索也要用比较好的方法实现。我在JAVA的演示程序中用的PriorityQueue可是结果不是很令人满意。         第四条优化策略是使用IDA*的算法这是A*算法的一种ID名为Iterative deepening是迭代加深的意思。思想是如下 顺便准备一个记录一次循环最小值的tempMAX, h 取 manhattan距离    先估算从START态到END态的h() 记录为MIN将START放入待访问队列    读取队列下一个状态到队列尾则GOTO⑦    若g() MIN GOTO ⑥    若g() h() MIN 是否为真真GOTO ⑥否 GOTO ⑤    扩展该状态并标记此状态已访问。找到END态的话就结束该算法。GOTO ②    temp min(manhattan , temp),GOTO ③    若无扩展过状态MINtemp ID的意思在这里体现从头开始循环GOTO ②         第五条优化策略本身与搜索无关在做题时也没能帮上忙不过从理论上讲是有参考价值的。记得Q6中介绍的从END开始搜起吗如果我们的任务是对多个START 与END进行搜索那么我们可以在每搜索完一次后记录下路径这个路径很重要因为在以后的搜索中如果存在START和END的路径已经被记录过了那么可以直接调出结果。         从END搜起可以方便判断下一次的START是否已经有路径到END了。当前一次搜索完时其已访问状态是可以直接使用的若START不在其中则从待访问的状态链表中按搜索策略找下一个状态等于接着上一次的搜索结果开始找。         之所以没能在速度上帮上忙是因为这个优化策略需要加大g ()的比重否则很容易出现深度相当大的情况由于前一次搜索的策略与下一次的基本无关导致前一次的路径无法预料所以就会出现深度过大的情况。解决方法是加大g ()。 策略五类似给程序加一个缓冲区避免重复计算。如果要做八数码的应用缓冲区会帮上忙的。 Q10怎样记录找到的路径         当找到解的时候我们就需要有类似回退的工作来整理一条解路径由于使用了不是简单的DFS所以不能借助通过函数调用所是使用的程序栈。         我们可以手工加一个模拟栈。在Q4中解决了哈希的问题利用哈希表就能快速访问状态对应的值在这里我们把原来的bool值改为char或其他能表示一次操作至少需要5种状态除了u r l d 外还要能表示状态已访问的值就行了。         在搜索到解时记录下最后一个访问的状态值然后从读取该状态对应的操作开始就像栈操作的退栈一样不停往回搜直到找到搜索起点为止。记录好栈退出来的操作值就是一条路径。 相关链接 应用软件下载 http://www.tomore.com/1/37256.html Eight ACM试题 PKU 1077题易 http://acm.pku.edu.cn/JudgeOnline/showproblem?problem_id1077 ZJU 1217题颇难 http://acm.zju.edu.cn/show_problem.php?pid1217 UVA 652题 http://acm.uva.es/p/v6/652.html 杭州电子科技大学1043题难 http://acm.hziee.edu.cn/showproblem.php?pid1043 中国科技大学 112题非SJ http://acm.ustc.edu.cn/makeproblem.php?probID112 相关题目 SOJ 2061题 http://acm.scu.edu.cn/soj/problem.action?id2061 SOJ 1110题 http://acm.scu.edu.cn/soj/problem.action?id1110 SOJ 2360题 http://acm.scu.edu.cn/soj/problem.action?id2360