《[计算机软件及应用]最优合并and八数码问题Java.doc》由会员分享，可在线阅读，更多相关《[计算机软件及应用]最优合并and八数码问题Java.doc（58页珍藏版）》请在三一文库上搜索。
1、算法分析与设计实验周最优合并问题 八数码问题 所做任务说明及题目相关知识说明文档编号：NUC-2012-A05A06-01版 本： 作 者： 打印日期： 2013年1月4日拷贝份数：12012中北大学电子与计算机科学技术学院 最优合并问题任务说明：给定k个排好序的序列S1，S2，Sk，用2路合并算法将这k个序列合并成一个序列。假设所采用的2路合并算法合并2个长度分别为m和n的序列需要m+n-1次比较。试设计一个算法确定合并这个序列的最优合并顺序，使所需的总比较次数最少。为了进行比较，还需要确定合并这个序列的最差合并顺序，使所需的总比较次数最多。 题目相关知识说明： 这个程序比较适合用堆，最优用
2、最小堆，最差用最大堆。使用各序列的长度建堆，把堆中两个最小（最大）的元素出堆，计算这两序列合并需要的比较次数（本体采用二路合并算法，两个长度分别为m和n的序列需要m+n-1次比较），该次数入堆， 重复以上步骤，直到堆只剩下一个元素，最后剩下的元素即为题目的解。相关知识：堆可以定义为一颗二叉树，数的节点中包含键（每个节点一个键），并且满足以下两个条件：（1）树的形状要求这棵二叉树为完全二叉树，即树的每层都是满的，除了最后一层最右边的元素有可能缺位。（2）父母优势要求对于最大堆，每个节点的键都要大于或等于它子女的键。对于最小堆来说，每个节点都要小于或等于它子女的键。堆也可以定义为一个数组H1.n,
3、数组的前半部分中，每个位置i上的元素，总是大于等于位置2i和2i+1 中的元素。本题中堆使用数组来实现。2012中北大学电子与计算机科学技术学院 八数码问题任务说明：在33的棋盘上，摆有八个棋子，每个棋子上标有1至8的某一数字。棋盘中留有一个空格。空格周围的棋子可以移到空格中。要求解的问题是：给出一种初始布局（初始状态）和目标面局（目标状态），找到一种移动方法，实现从初始布局到目标布局的转变。题目相关知识说明：状态用二维数组来表示布局比较直观，S（i，j）表示第i行第j列格子上放的棋子数字。空格则用0来表示。输入一种状态作为当前状态，从当前状态出发，采用广度优先搜索策略进行搜索。在搜索过程中，
4、问题的状态用结点描述，需要使用一个队列存储搜索的中间结点，为了在找到目标结点后，能够找到从初始结点到目标结点的路径，需要保留所有搜索过的结点搜索算法中。结点中除了描述状态的数组外，还有一个父结点指针last，它记录了当前结点的父结点编号。在到达目标结点后，通过last指针 可以找出搜索的路径，最后输出路径。移动规则：根据题意空格周围的棋子可以向空格移动。为便于解决问题，显然从另一个角度来看，“空格周围的棋子可以向空格移动”相当于“空格向四周移动”，这样就把四枚棋子的移动转化为一个空格的移动，从而便于问题的处理。设空格位置在（i0，j0），则根据题意有四条移动规则：（1）空格向上移动。If i0
5、-1=1 then s(i0,j0)：=s(i0-1,j0); s(i0-1,j0)：=02012中北大学电子与计算机科学技术学院 （2）空格向下移动。If i0+1=1 then s(i0,j0)：=s(i0,j0-1); s(i0,j0-1)：=0（4）空格向右移动。If j0+1=3 then s(i0,j0)：=s(i0-1,j0); s(i0,j0+1)：=0搜索步骤：（1）把初始状态作为当前状态；（2）从当前状态出发，运用四条移动规则，产生新的状态；（3）判断新的状态是否达到目标状态，如果是，转（5）；（4）把新的状态记录下来，取出下一个中间状态作为当前状态，返回（2）；（5）输出
6、从初始状态到目标状态的路径，结束。常用的搜索策略有广度优先搜索、深度优先搜索和启发式搜索三种策略。前两种搜索策略属于盲目搜索，效率低，而且在很多情况下得不到解！而启发式搜索根据贪婪技术，每一步选择的都是最好的与目标节点最近的节点。对于任意给定的一组数，用0代表空格，则九宫图初始状态为数08的一个排列，记为 n0 n1 n2 n3 n4 n5 n6 n7 n8 使用线性代数的有关理论可以证明，与目标结点逆序数( 这里的逆序数计算不包括0)奇偶性相同的八数码才可通过一定的移动到达目标状态，也即对于任一个目标状态节点，只有(1/2)91=181440个状态有解。相应的剪枝函数：八数码问题中，每个数字
7、可以有9个不同的位置，因此，在任意状态中的每个数字和目标状态中同一数字的相对距离就有9*9种，可以先将这些相对距离算出来，用一个矩阵存储，这样只要知道两个状态中同一个数字的位置，就可查出它们的相对距离，也就是该数字的偏移距离： 本题所采用的剪枝函数是计算每个位置移动到目标状态相应位置所走的步数之和，即曼哈顿距离。通过计算每个节点的启发值大小，即可为每个节点赋予不同的权值，而搜索时则选择所有节点中权值最小的作为当前节点。2012中北大学电子与计算机科学技术学院 01234567800121232341101212323221032143231230121234212101212532121032
8、1623412301273232121018432321210表 1.01方法二：搜索策略：（1） 首先判断目标状态里面空格是否处于九宫格中间;（2） 如果是,进行下一步(3),如果不是,则移动空格到中间位置,并记录移动路径;可知最多只要2步就行;（3） 通过图形可知,外围8位数是一个首位相连的环形.建立前后对应表s1;（4） 判断初始状态空格是否在中间,并按照上每年方法将空格移动到中间;（5） 现有状态根据目标状态建立2,4,6,8位权值表,判断总数是否为10;如果不是,继续下一步,如果是跳到第(9)步;（6） 计算权值,找出最小的那一个.根据目标前后对应表s1找出下一个数字和顺时针距离;（
9、7） 将空格和要插入数对换,根据步骤表找出空格移动方向和距离.（8） 将数字插入到对应位置,即和空格对换;跳到步骤(5);（9） 判断先有状态是否能到达目标状态(奇偶对应)（10） 输出结果;2012中北大学电子与计算机科学技术学院 相关知识： 前后对应表: 将目标状态空格移动到中间,则外围8个数可以看做一个环形,则每一个数都前后对应一个数。如图所示:123804765 表 1.02则能建立前后对应表为：外围数字12345678前对应数字23456781后对应数字81234567 表 1.03根据目标状态输入的不同,该表随之改变权值表: 以2,4,6,8位计算每位权值; 建立10空间二维数组如
10、下246801234567891100010011 表 1.04因为外围是一个环形,所以0位和8位相同,9位和1位相同;如果判断位(2.4.6.8)前面一个满足,则对应前权值为1,否则为0;同样后面也是如此判断;权值计算方法;如表所示:假如1位=1;2位=0;则权值为0位+1位+2位;假如3位=0;4位=0;则权值为:3位+4位;如果5位=1;6位=0;则权值为:4位+5位+6位2012中北大学电子与计算机科学技术学院 即首先判断前后位权值是否为1;如果是则加上旁边一位;同时,判断位也也是下一步要查找方向;假如要移动2位,而权值表为1,则要找前一位;为0则查找后一位;移动步骤表:通过实际操作,
11、发现不管顺时针还是逆时针,总能移动到想要的地方,但是步骤却有较大差别.但是因为总距离的限制,可以很容易找到规律并建立查找表如下:其中第一行为顺时针距离开始移动位置距离;第二行为移动方向;第三行为移动步骤;查找前一个:123456710101010624426 表 1.05查找后一个:123456701010106244260 表 1.062012中北大学电子与计算机科学技术学院 2012中北大学电子与计算机科学技术学院 7最优合并问题 八数码问题 数据结构设计说明文档编号：NUC-2012-A05A06-02版 本： 作 者： 打印日期： 2013年1月4日拷贝份数：12012中北大学电子与计
12、算机科学技术学院 2012中北大学电子与计算机科学技术学院 最优合并问题数据结构：堆是一种灵巧的，部分有序的数据结构。堆可以定义为一颗二叉树，数的节点中包含键（每个节点一个键），并且满足以下两个条件：（1）树的形状要求这棵二叉树为完全二叉树，即树的每层都是满的，除了最后一层最右边的元素有可能缺位。（2）父母优势要求对于最大堆，每个节点的键都要大于或等于它子女的键。对于最小堆来说，每个节点都要小于或等于它子女的键。堆也可以定义为一个数组H1.n,数组的前半部分中，每个位置i上的元素，总是大于等于位置2i和2i+1 中的元素。本题中堆采用数组来实现，对于堆的插入，删除，堆排序等操作都是对数组的操作
13、。八数码问题数据结构：在搜索过程中节点的信息定义成一个Node类，其中Node定义如下：public class Node int data=new int9;Node last;int value；public Node()public Node(int a)for(int i=0;i9;i+)datai=ai;2012中北大学电子与计算机科学技术学院 public int getdata() return data; public boolean equal(int endstatus)for(int i=0;i9;i+)if(this.datai!=endstatusi)return f
14、alse;return true; 其中int data数组表示节点的状态信息，int value表示节点的权值。equal（）函数用来比较两个节点的信息是否相同，相同返回true，不同返回false。搜索过程中的节点用两个优先队列List1和List2来存储。其中优先级是根据节点的权值，权值最小的节点在队列头，权值最大的节点存储在队列的尾部。List1用来存储已搜索出来的路径中的节点，List2用来存储节点扩展出来的节点。优先级队列定义如下：PriorityQueue list1 = new PriorityQueue (max,cmp); PriorityQueue list2=new P
15、riorityQueue (max,cmp); NodeComparator cmp = new NodeComparator(); class NodeComparator implements Comparator public int compare(Node x, Node y) return x.value - y.value; 2012中北大学电子与计算机科学技术学院 NodeComparator 类是对象比较器，用来定义优先队列的优先级。最优合并问题 八数码问题 程序模块及流程设计文档编号：NUC-2012-A05A06-03版 本： 作 者： 打印日期： 2013年1月4日拷贝
16、份数：12012中北大学电子与计算机科学技术学院 2012中北大学电子与计算机科学技术学院 3最优合并问题程序模块：主模块：本模块包括界面图形设计，文件的读入、读出，选择最优或最差合并合并。最小堆初始化及最优合并操作模块：本模块包括对于任意给定一组数（该组数为各序列的长度），建立最小堆 ，同时对最小堆进行操作，找出最优合并所用的次数。最大堆初始化及操作模块：本模块包括对于任意给定的一组数（该组数为各序列长度的值），建立最大堆，同时对最大堆惊醒操作，求解最差合并所用次数。2012中北大学电子与计算机科学技术学院 流程设计：开 始文 件各序列的长度的值读取 最优合并最差合并选择最优、最差合并最差合
17、并处理模块最优合并处理模块存入存入文 件输出最差合并次数输出最优合并次数结 束2012中北大学电子与计算机科学技术学院 图 3.01开 始开 始2012中北大学电子与计算机科学技术学院 图 3.02图 3.03 结 束结 束使用各序列长度建立最大堆堆中是否只有一个元素输出最终结果合并后入堆最大两个元素出堆是输出最终结果合并后入堆最小两个元素出堆否是最小堆中只有 一个元素？使用各序列长度建立最小堆否八数码问题程序模块：节点信息定义模块：本模块定义了表示节点信息的数组和表示节点权值的整型变量以及对节点的操作。搜索模块：本模块定义了搜索目标状态的过程，包括对节点的扩展，判断比较大小等操作。界面设计模
18、块：本模块定义了基本的界面，以及对文件的读取和存储等操作。流程设计：2012中北大学电子与计算机科学技术学院 遍历List2，输出路径结 束图 3.04N是否为目标状态？扩展N节点，对所有的扩展出的节点按其启发值的大小排序，若List2中不存在，则存入失败，退出List2表为空？逆序值得奇偶性相同？将初始状态存入list2表中取List2表中的头节点N初始化初始状态和目标状态，计算初始状态和目标状态的逆序值目标状态不可达，重新输入开 始2012中北大学电子与计算机科学技术学院 结束输出结果判断是否能达到目标状态建立目标状态前后对应表查表并根据表格数据移动图 3.05判断总和是否为10建立现有状
19、态权值表找到最小权值位初始化初始状态和目标状态开 始NY2012中北大学电子与计算机科学技术学院 6最优合并问题 八数码问题 源程序清单及测试说明文档编号：NUC-2012-A05A06-04版 本： 作 者：打印日期： 2013年1月4日拷贝份数：12012中北大学电子与计算机科学技术学院 8最优合并问题核心代码：最优合并：package Combine;public class Minheapprivate int min_heap;public void creat(int a)min_heap=a;/自底向上构造最小堆public void bottomtoup()int temp =
20、 0;int p;int e;boolean heap;/标志当前节点是否满足父母优势for(int i=(min_heap.length-1)/2;i0;i-) e=i;heap=false;while(2*e=(min_heap.length-1)&heap=false)p=2*e;if(p=min_heapp|min_heape=min_heapp+1)if(min_heapp=min_heapp+1)p=p+1;temp=min_heapp;min_heapp=min_heape;min_heape=temp;e=p;2012中北大学电子与计算机科学技术学院 elsetemp=min_
21、heapp;min_heapp=min_heape;min_heape=temp;e=p;elseheap=true;else /只存在一个子女if(min_heape=min_heapp)heap=true;elsetemp=min_heapp;min_heapp=min_heape;min_heape=temp;e=p;System.out.println(最小堆为：);for(int q=0;q1)m1=toptodown(heapsize);2012中北大学电子与计算机科学技术学院 heapsize-;m2=toptodown(heapsize);heapsize-;sub=m1+m2
22、;insert(sub,heapsize);heapsize+;subs=subs+sub;z=subs-(min_heap.length-2);return z;/*根节点出堆，即删除根节点,然后自上向下调整堆，使各元素满足父母优势！*/public int toptodown(int n)/n为当前堆中元素的个数int item=min_heap1;int temp;min_heap1=min_heapn;/最后一个元素换到第一个元素的位置，第一个元素出堆n-;/*从上到下进行调整*/int j;int i=1;j=2*i;while(j=n)if(j=min_heapj)|(min_he
23、api=min_heapj+1)if(min_heapj=min_heapj)temp=min_heapi;min_heapi=min_heapj;min_heapj=temp;elsebreak;i+;j=i*2;return item;/两个最小元素合并完后的次数入堆public int insert(int a,int b)int temp;int heap_size;heap_size=b;heap_size+;min_heapheap_size=a;int j;int i=heap_size;j=i/2;while(j0)if(min_heapi=min_heapj)/父母节点小于等
24、于要插入的值，不交换break;2012中北大学电子与计算机科学技术学院 elsetemp=min_heapi;min_heapi=min_heapj;min_heapj=temp;/父母节点大于要插入的值，交换父母与子女结点i=j;j=j/2;return heap_size;/返回当前堆中元素的个数最差合并：package Combine;public class Maxheap private int max_heap;public void creat(int b)max_heap=b;/构建最大堆public void max_bottomtoup()int k;int j;int
25、temp1=0;boolean heap;for(int s=(max_heap.length-1)/2;s0;s-)k=s;heap=false;while(2*k=(max_heap.length-1)&heap=false)j=2*k;2012中北大学电子与计算机科学技术学院 if(jmax_heap.length-1) /存在两个子女if(max_heapk=max_heapj)|(max_heapk=max_heapj+1) /将子女节点中大的调整到父母节点上if(max_heapj=max_heapj)heap=true;elsetemp1=max_heapj;max_heapj=
26、max_heapk;max_heapk=temp1;k=j;2012中北大学电子与计算机科学技术学院 System.out.println(最大堆为：);for(int n=0;n1)m1=delete(heapsize);heapsize-;m2=delete(heapsize);heapsize-;combine=m1+m2;maxinsert(combine,heapsize);heapsize+;sub=sub+combine;return (sub-(max_heap.length-2);/*最大元素出堆，即根节点出堆，对的规模减一,调整堆使之满足父母优势*/public int d
27、elete(int n)int iem=max_heap1;int temp1;max_heap1=max_heapn;/最后一个元素换到第一个元素的位置，第一个元素出堆n-;/*从上到下进行调整*/int j;int i=1;j=2*i;while(j=n)2012中北大学电子与计算机科学技术学院 if(jn)if(max_heapi=max_heapj)|(max_heapimax_heapj+1)temp1=max_heapi;max_heapi=max_heapj;max_heapj=temp1;elsetemp1=max_heapi;max_heapi=max_heapj+1;max
28、_heapj+1=temp1;i=i+1;j=i*2;else if(j=n)if(max_heapi0)if(max_heapimax_heapj)/父母节点大于等于要插入的值，不交换break;elsetemp=max_heapi;max_heapi=max_heapj;max_heapj=temp;/父母节点小于要插入的值，交换父母与子女结点i=j;j=j/2;return heapsize;蛮力法：package Combine;public class brustforce public void combine(int heap) /合并最优 int A=heap; int n=A
29、.length; int A1=new intn; int B=new intn; for(int i=0;i=n-1;i+) A1i=Ai; for(int b=0;b=n-2;b+) for(int a=0;a=n-2;a+) 2012中北大学电子与计算机科学技术学院 for(int i=0;i=n-2;i+) int temp=Ai+1-Ai; if (temp=0) int temp1=Ai; Ai=Ai+1; Ai+1=temp1; /数组排序 int temp2=Ab+Ab+1; Bb=temp2; Ab=0; Ab+1=temp2; int AA=0; for(int i=0;i
30、=n-2;i+) AA=AA+Bi-1; /最差/ for(int a=0;a=n-2;a+) for(int i=0;i=n-2;i+) int temp=A1i+1-A1i; if (temp=0) int temp1=A1i; A1i=A1i+1; A1i+1=temp1; /数组排序 int AB=A1n-1; for(int i=0;i=n-2;i+) AB=AB+A1n-i-2; Bi=AB; int BB=0; for(int i=0;i=n-2;i+)2012中北大学电子与计算机科学技术学院 BB=BB+Bi-1 ; System.out.println(); System.out.println(最优为：+AA); System.out.println(最差为：+BB); 程序测试部分结果：