资源描述：
《最优合并问题》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、1引言1.1问题描述给定k个排好序的序列SI,S2・・・，Sk,用2路合并算法将这k个序列合并成一个序列。假设所采用的2路合并算法合并2个长度分别为m和n的序列需要m+n-l次比较。试设计一个算法确定合并这个序列的最优合并顺序，使所需的总比较次数最少。为了进行比较，还需要确定合并这个序列的最并合并顺序，使所需的总比较次数最多。1.2问题分析两路合并算法是通过反复执行将两个有序子文件合并成一个有序文件的操作，最终将n个长度不等的有序子文件合并成一个有序文件。编写该软件是实现将给定的几个长度不等的有序子文件合并
2、成-个有序的文件，并且求出合并过程中比较的次数。2系统分析2.1实现方法2.1.1蛮力法采用蛮力法，若有n个序列，则有n!种合并方法，实现列举出每种方法，并计算比较次数。2.1.2贪心法木方法采用构造最大堆和最小堆来解决。思路：最差合并顺序一总是最长的两个先合并；最优合并顺序一总是最短的两个先合并。2.1.3贪心法最优合并证明最优合并顺序证明：设有n个权值W二…，⑷｝作为外结点的权值，构造两路合并树的贪心算法将生成-棵具有最小带权路径长度的二叉树。证明:1）对于"1,算法将返回只冇一个外结点的二叉树，这棵树
3、显然是最优的。2）假定外结点的数目为k5时，算法能够生成有k个外结点的最佳二路合并树。3）当En时，假定有n个权值％'叫'-W-,并设贪心算法生成的两路合并树为7；,设0051（7；,）是7；的带权外路径长度。如果它不是最优的，而另一棵同样以此n个权值为外结点的两路径合并树7；是最优的，即cost（兀）〈cost（人）。对于兀，现假定结点P是该树上离根最远的内结点，它有两个孩子叱和匕。如果它们不是最小的两个权值和W］,可以通过交换使得P的孩了为％和W［。于是得到另一棵有n个外结点的两路合并树乙”，必有cos
4、t（7”）Wcost（7；）。对于T「,用权值为％+吗的外结点取代以p为根的子树（见图2）,得到一棵有门-1个外结点的两路合并树匚一“。同样，可以对由贪心法得到的两路合并树7；也进行类似替代，即对由两个外结点％和吗合并形成的了树，用一个权值为％+吗的外结点取代之，从而得到一•棵旷1个外结点的两路合并树Tn_iO二叉树7；」正是对权值集{+y,也，，叫执行上述贪心算法所生成的两路合并树。根据归纳法假设，cost(Tn_x)cost(TH_)"),±
5、于cost(7；,)=cost)+w°+W］和cost（7
6、”）=cost）+w（）+）竹，所以cost（人）Wcost（;又因为cost（7”）Wcost（Z；）,所以cost（£?）Wcost（人），这与假设矛盾，这就证明了贪心算法生成的两路合并树必定是具有最小带权外路径长度的二叉树，因而是最佳两路合并树。root(b)Tn(、VIa)Tn2.2数据结构木方法的数据结构采用堆。堆是一种灵巧的，部分有序的数据结构。堆可以定义为一颗二叉树，数的节点屮包含键（每个节点一个键），并且满足以下两个条件:（1）树的形状要求:这棵二叉树为完全二叉树。（2）父母优势要求：对
7、于最大堆，每个节点的键都要大于或等于它子女的键。对于最小堆来说，每个节点都耍小于或等于它子女的键。本方法中堆采用数组来实现对于堆的插入，删除，堆排序等操作。3总体设计4模块设计及实现4.1主模块木模块包括：界面设计，文件的读入、读出，选择使用蛮力法或贪心法，动态演示。4.2蛮力法模块本模块包括：读取指定有序子序列文件的长度存放到数组小，然后将n!种合并方式的结果存放到文件中，并且计算每种方式的比较次数也存放到文件中。4.3贪心法模块4.3.1最优合并模块本模块包括：读取指定合并有序子序列文件的长度存放到数组
8、屮，建立最小堆，同时对最小堆进行操作，计算出最优合并所用的次数；对于任意给定一组数,该组数为各有序子序列的长度，将其存放到数组中，建立最小堆，同时对最小堆进行操作，计算出最优合并所用的次数。4.3.2最差合并模块本模块包括：读取指定合并有序子序列文件的长度存放到数组屮，建立最大堆，同时对最大堆进行操作，计算出最优合并所用的次数；对于任意给定一组数,该组数为各有序子序列的长度，将其存放到数组中，建立最大堆，同时对最大堆进行操作，计算出最优合并所用的次数。5源程序代码5.1界面设计packagemywind;i
9、mportjava.awt.Dimension;importjava.awt.GridLayout;importjavci.awt.event.ActionEvent;importjava.awt.event.ActionListener;importjava.io.BufferedReader;importjava.io.BufferedWriter;importjava.io.File;importjava.
