微信做明天展现网站要多少钱,司法局网站建设方案,实时seo排名点击软件,广告设计是学什么的贪婪算法
贪婪算法分阶段地工作。在每个阶段#xff0c;可以认为所做决定是最好的#xff0c;而不考虑将来的后果。通常这意味着选择的是某个局部最优。这种“当前能获得的最优就拿”的策略是这类算法的名字来源。当算法终止时候#xff0c;我们希望的到累积的局部最优解就…贪婪算法
贪婪算法分阶段地工作。在每个阶段可以认为所做决定是最好的而不考虑将来的后果。通常这意味着选择的是某个局部最优。这种“当前能获得的最优就拿”的策略是这类算法的名字来源。当算法终止时候我们希望的到累积的局部最优解就等于全局最优如果是这样的那么算法就是正确的否则算法得到的是一个次优解suboptimal solution。如果不需要绝对的最佳答案那么有时候使用简单的贪婪算法生成近似的答案能得到一个时间复杂度更优的解。
案例分析 举几个现实的贪婪算法的例子明显的是货币找零问题。 使用RMB找零钱我们重复的配发最大额货币。于是为了找十七块六毛我们拿出一张10元一张5元2张1元2元货币现在少见了加一个5毛硬币两个一毛硬币。这么做我们能保证使用最少的钞票和硬币这个算法不是对每种货币通用但是RMB是有效的 交通问题 以下会详细讲解两个案例来说明贪婪算法的应用第一个模拟调度问题第二个模拟文件压缩算法他是计算机科学最早的成果之一。
一个简单的调度问题
假设我们计算机系统由任务j1j2j3 …jN已知对应的运行时间分别是t1t2t3…tN而处理器只有一个为了把作业平均完成的时间最小化调度这些作业的最好方式是什么假设我们讨论的都是非预占调度nonpreemptive scheduling一旦开始一个任务就必须吧任务执行完。我们用以下案例简化四个作业已经运行时间如下表格一个可能的调度在图一中表示
任务时间j115j28j33j410上图中j1 用时15个时间单位运行结束j2用时2315j2时间 个时间单位j3,用26j4用36所以平均完成时间是25。但是一个更好的调度完成时间是17.75 如下图中 上图中给出的调度是按照最短的作业先完成来进行的。我们可以证明这种模式总会产生一个最优的调度令调度表中的作业是j1j2j3j4…jn。第一个作业完成时间t_1第二个作业t_1t_2后完成第三个作业依次类推由此可以得到调度的总代价C有如下推论
C t_1 (t_1t_2) (t_1t_2t_3) ......(t_1t_2t_3......t_n)
C nt_1 (n-1)t-2 (n-2)t_3 (n-3)t_4 .... 2t_(n-1) t_(n-1)
C (n-11)t_1 (n-21)t_2 ... (n-(n-1)1)t_(n-1) (n-n1)t_n如上累加∑k1n\sum_{k1}^n∑k1n(n-k1)tk ∑k1n\sum_{k1}^n∑k1n(n1)tk - ∑k1n\sum_{k1}^n∑k1nk*tk如上表达是可以看成调度总时间和∑k1n\sum_{k1}^n∑k1nk*tk 成反比k表示第几个位置执行tk表示指定第k次执行的时间当这个数值越大那么总的时间就越少那么我们将权重越大的往后放就能得到最小值。
多处理器情况
我们可以把问题扩展到多个处理器的情况我们还是这些作业j1j2j3j4…jn。时间t1t2t3…tN另外有处理器P个。假设作业是有序的最短的运行时间最先处理加入P 3.如下表格
任务时间j13j25j36j410j511j614j715j818j920如上图他平均完成时间优化到了最小作业1,47在处理器1 上运行处理器二在2,58 上处理器3 处理其余作业总完成时间是165平均是165/9 18.33解决多处理器情形的算法是按顺序开始作业处理器之间轮换分配罪业不难证明没有那个其他顺序能做到更好。但是还有其他顺序的最优解如下图 如上还是最小的先执行只是我们将是哪个处理器处理的任务换了换而已
将最后完成时间最小化
还需要考虑一个非常类似情况假设我们只关注最后的作业的结束时间在上面的两个例子中他们的完成时间分别是40 与38第二种最后完成时间是更小的我们能找出更小的最后完成时间在上面二个方法中整个序列完成时间更早是更可取的方法我们有如下算法实现
算法分析
首先获取任务并且从小到大排序每次分配统计每个处理器处理需要的总时间每次取出最小的一个任务给定处理器列表中总时间最小的那个也就先处理完的优先分配任务依次处理任务直到任务都处理完结
代码实现
/*** 贪心算法处理器调度问题** author liaojiamin* Date:Created in 16:26 2021/1/12*/
public class ProcessorScheduling {class Task implements ComparableTask {private String taskName;private Integer taskTime;public String getTaskName() {return taskName;}public void setTaskName(String taskName) {this.taskName taskName;}public Integer getTaskTime() {return taskTime;}public void setTaskTime(Integer taskTime) {this.taskTime taskTime;}Overridepublic int compareTo(Task o) {return this.taskTime - o.taskTime;}}/*** 获取需要处理的业务数据*/public Task[] getTask(Integer num) {Task[] tasks new Task[num];Random random new Random();for (int i 0; i num; i) {Task task new Task();task.setTaskName(t i);task.setTaskTime(random.nextInt(10));tasks[i] task;}return tasks;}/*** 对数据进行从小到大排序*/public Task[] sortTask(Task[] tasks) {if (tasks null) {return null;}quickSort(tasks, 0, tasks.length - 1);return tasks;}public Task[] quickSort(Task[] tasks, Integer left, Integer right) {if (left right) {Integer temp swap(tasks, left, right);quickSort(tasks, left, temp - 1);quickSort(tasks, temp 1, right);}return tasks;}/*** 挖坑法快排*/public Integer swap(Task[] tasks, Integer left, Integer right) {if (left right) {Task position tasks[left];while (left right) {while (left right tasks[right].compareTo(position) 0) {right--;}if (left right) {tasks[left] tasks[right];left;}while (left right tasks[left].compareTo(position) 0) {left;}if (left right) {tasks[right] tasks[left];right--;}}tasks[left] position;}return left;}/*** 贪心算法* 给P个处理器分配任务*/public void finishTask(Integer p) {Task[] tasks sortTask(getTask(8));for (int i 0; i tasks.length; i) {System.out.println(tasks[i].getTaskName() : tasks[i].getTaskTime());}//存储每个列表总时长int[] countP new int[p];//存储每个cpu的任务存储位置int[] posicition new int[p];//存储p个cpu的任务列表Task[][] taskResult new Task[p][tasks.length - 1];for (int i 0; i tasks.length; i) {Integer min getMinId(countP);countP[min] tasks[i].getTaskTime();taskResult[min][posicition[min]] tasks[i];posicition[min] 1;}for (Task[] tasks1 : taskResult) {for (Task task : tasks1) {if (task ! null) {System.out.print(task.getTaskName() : task.getTaskTime());System.out.print( );}}System.out.println();}}/*** 获取最小值id*/public int getMinId(int[] countP) {if (countP.length 0) {return 0;}int min countP[0];int minNum 0;for (int i 0; i countP.length; i) {if (min countP[i]) {min countP[i];minNum i;}}return minNum;}public static void main(String[] args) {ProcessorScheduling fi new ProcessorScheduling();fi.finishTask(3);}
}
哈夫曼编码 第二个案例我们来研究一下贪婪算法的文件压缩处理file compression 在现实中文件是非常大的许多大文件是某个程序的输出而在使用评率最大和最小的字符之间存在很大差别例如文件大多包含的空格和newline多qx这些字符少。如果我们在非高效性传输场景下我们更希望文件大小越小越好其实却是是有这样的方案囊使文件街上25%甚至更多 我们一般的策略是让代码的长度从字符到字符是变化不等的同时保证经常出现的字符其代码要短。 如果所有字符都相同频率出现那么无法优化 我们可以用二进制代码来标识字符并且我们用二叉树来标识二进制 标准的ASCII字符集大约也就100个“可打印”字符组成。我们设一个文件质保函字符aeist加上一些空格和newline换行。进一步假设有10个a15个e12个i3个s4个t13个空格以及一个newline如下图中标识 -如上二叉树所有数据只在叶子节点上每个字符通过根节点开始用0 指定左边分支用1 标识右边如a节点 000 占用3个比特位置 e节点001占用3个比特位置i节点010如下表格统计
字符编码频率比特数a0001030e0011545i0101236s01139t100412空格1011339nl11013
如下表格中这个文件我们用二叉树标识可以只永174个比特位就能标识因为有58个字符而每个字符3个比特位。这种数据结构叫做trie树trie如果字符 c_i 在深度 d_i 出出现 f_i 次那么这种编码的值就等于∑i1n\sum_{i1}^n∑i1nd_i*f_i更优的解法如下图 如上二叉树的构成并不是最优解而且我们注意到这个二叉树是一颗满树 full tree:所有的节点要么是树叶要么有两个儿子。一种最优的编码总是有这种性质否则正如我们看到的具有一个儿子的节点可以向上移动一层。如上我们需要解决的基本问题在于找到总价值最小的满二叉树其中所有字符都必须在叶子节点我们需要解决的是如何构造这颗二叉树1952年Huffman给出来一个算法。因此这种编码系统通常称为哈夫曼编码Hufman code
哈夫曼算法
加上字符个数为C。哈夫曼算法Huffman’s algorithm可以如下描述 算法对应由树组成的一个森林。一棵树的权重等于它的树叶出现的评率此处是字符在文件中出现的次数。任意选取两颗权重最小的树T1 T2并任意以T1T2 为子树组成一颗新树将上一步骤过程进行C-1次。 在算法开始存在C课单节点树—每棵树都代表一个字符。在算法结束得到一棵树这棵树就是最优哈夫曼编码树
具体案例分析
如下图的初始森林每棵树的权在根节点处以数字表示。 将两颗权最低的树合并到一起得到以下森林我们将根节点命名成T1命名可以任意此处只是为了以下的表述更加方便我们可以看到我们令s是左儿子这次令其为左儿子还是右儿子是任意的 我们可以观察到哈夫曼算法描述中两个任意性 新树的总权值是那些老树权的和当然也就很容易计算由于建立新树只需得出一个新节点建立左右链接并将权重记录因此建立新树叶简单 经以上步骤我们得到六棵树接着在选取两颗权重最小的树这两颗数是T1 和t然后将他们合并成另一颗新树树根节点是T2权重是8如下图 在将T2 与a 节点合并建立T3权重是108 18如下图 接着继续选取最小权重两个节点这次是i 节点和空格节点将这两棵树合并成根节点T4, 继续合并根节点为e 和T3 的树得到下图 最后将两个剩下的树合并得到最优树根节点是T6. 如上算法可以看出哈夫曼树的一些特性 哈夫曼树必然是满的其次两个权重最小的节点AB必然是最深的节点如果权重最小的节点AB不是最深的节点那么必然存在某个C是最深的节点如果A的权重小于C那么我们可以通过交换他们在树上的位置而改进总权值相同深度上任意两个节点处的字符可以交换而不影响最优性这说明总可以找到一颗最优树他含有两个进程不出现的符号作为兄弟 以上算方分析是贪婪算法的原因在于每一节点我们都进行一次合并而没有进行全局的考虑我们只是每个步骤选取最小权重的树
算法分析
按照上述C个元素按顺序保存在一个优先队列那么我们在队列上进行一次buildHeap2C-2次deleteMin和C-2次insert因此运行时间为O(ClogC)如果使用链表简单实现该队列我们给出一个O(C^2)时间复杂度算法优先队列实现方法的选择取决于C的大小在ASCII字符集典型情况下C是足够小的这使得二次的运行时间是可以接受的这样的应用中实际上所有的运行时间都讲话费在读取输入文件和写入压缩文件所需的磁盘IO上。
算法实现
//哈夫曼树节点定义
/*** author liaojiamin* Date:Created in 11:47 2021/1/13*/
public class HufmanNode implements ComparableHufmanNode{//节点权重private Integer weight;//节点名称private String nodeName;private HufmanNode left;private HufmanNode right;public Integer getWeight() {return weight;}public void setWeight(Integer weight) {this.weight weight;}public String getNodeName() {return nodeName;}public void setNodeName(String nodeName) {this.nodeName nodeName;}public HufmanNode getLeft() {return left;}public void setLeft(HufmanNode left) {this.left left;}public HufmanNode getRight() {return right;}public void setRight(HufmanNode right) {this.right right;}Overridepublic int compareTo(HufmanNode o) {return this.weight - o.weight;}
}
/*** 哈夫曼算法 模拟 文件压缩问题* author liaojiamin* Date:Created in 11:46 2021/1/13*/
public class HufmanCode {/*** 初始化文件字符信息* */public static String getRandomString(int length){String strabcdefghabc;Random randomnew Random();StringBuffer sbnew StringBuffer();for(int i0;ilength;i){int numberrandom.nextInt(10);sb.append(str.charAt(number));}System.out.println(sb);return sb.toString();}/*** 哈夫曼编码问题实现* */public static HufmanNode hufmanCode(){String hufmanBase getRandomString(20);if(hufmanBase null || hufmanBase.length() 0){return null;}MapString, Integer nameToWeight new HashMap();for (int i 0; i hufmanBase.length(); i) {String key String.valueOf(hufmanBase.charAt(i));Integer value nameToWeight.get(key);nameToWeight.put(key, value null ? 1 : value 1);}LinkedListHufmanNode linkedList buildHufmanNode(nameToWeight);quickSort(linkedList, 0, linkedList.size() -1);if(linkedList.size() 1){return linkedList.get(0);}while (!linkedList.isEmpty()){if(linkedList.size() 1){return linkedList.removeFirst();}HufmanNode hufmanNode buildNewNode(linkedList.removeFirst(), linkedList.removeFirst());insertLinkedList(linkedList, hufmanNode);}return linkedList.removeFirst();}/*** 按weight顺序插入哈夫曼节点* */public static void insertLinkedList(LinkedListHufmanNode linkedList, HufmanNode hufmanNode){if (linkedList.size() 0){linkedList.add(hufmanNode);return;}Integer temp linkedList.size() - 1;for (int i 0; i linkedList.size(); i) {if(linkedList.get(i).getWeight() hufmanNode.getWeight()){temp i;}}linkedList.add(temp, hufmanNode);}/*** 构造节点信息* */public static HufmanNode buildNewNode(HufmanNode left, HufmanNode right){HufmanNode hufmanNode new HufmanNode();hufmanNode.setLeft(left);hufmanNode.setRight(right);hufmanNode.setNodeName(node System.currentTimeMillis());hufmanNode.setWeight(left.getWeight() right.getWeight());return hufmanNode;}/*** 快排权重从小到大* */public static void quickSort(LinkedListHufmanNode linkedList, Integer left, Integer right){if(left right){Integer temp swap(linkedList, left, right);quickSort(linkedList, left, temp -1);quickSort(linkedList, temp 1, right);}}/*** 挖坑法实现快排* */public static Integer swap(LinkedListHufmanNode linkedList, Integer left, Integer right){if(left right){HufmanNode position linkedList.get(left);while (left right){while (left right linkedList.get(right).compareTo(position) 0){right --;}if(left right){linkedList.set(left, linkedList.get(right));left ;}while (left right linkedList.get(left).compareTo(position) 0){left ;}if(left right){linkedList.set(right, linkedList.get(left));right--;}}linkedList.set(left, position);}return left;}/*** 构造树节点* */public static LinkedListHufmanNode buildHufmanNode(MapString, Integer nameToWeight){LinkedListHufmanNode linkedList new LinkedList();for (String nodeName : nameToWeight.keySet()) {HufmanNode hufmanNode new HufmanNode();hufmanNode.setNodeName(nodeName);hufmanNode.setWeight(nameToWeight.get(nodeName));linkedList.addFirst(hufmanNode);}return linkedList;}public static void main(String[] args) {HufmanNode hufmanNode hufmanCode();}
}
上一篇数据结构与算法–图论-深度优先搜索及其应用 下一篇数据结构与算法–贪婪算法2
