Change Dir

先知cd——热爱生活是一切艺术的开始

统计

留言簿(18)

积分与排名

“牛”们的博客

各个公司技术

我的链接

淘宝技术

阅读排行榜

评论排行榜

深入理解动态规划的一系列问题(10)

不知不觉已经写到第10个问题了,动态规划的问题相信大家也发现了一些规律,看到什么样的问题知道动态规划求解呢?基本上所有的问题都类似最短路,定义了一个状态后根据状态列动态规划方程,方程的形式一般是递归式,包含一个子结构的更新过程……接下来就是罗列问题了:第10题是算导中提过的题目,DEADLINE调度问题(其实这个问题还有一个高阶版本)。

deadline问题的描述是:一台处理器可以处理n个作业,表示为a1,a2,…,an。每个作业aj有相等的运行时长(如果不等也作为变量呢?),有效益pj以及截止时间dj。机器是串行的,也就是说一个时刻只能处理一个作业。而且作业是原子的,不可拆分。获得效益pj的前提是aj一定要在dj之前完成。请给出一个算法来达到最优调度,即效益最大化。之前讲到,在看到最优化问题时就直接想DP求解,这个当然是个好习惯,但是这里再介绍一个思路就是优先可以先考虑贪心是否可解,相对列动态规划方程定义状态这些事情,贪心往往更直观更简单(人心不足啊)。

这个问题是可以使用贪心法求解的,贪心算法不是我们这个系列问题的关键,但是也可以简单谈一下贪心:贪心的核心是要确定正确的贪心目标,就是在一系列决策做出时,每个步骤选择的理由是什么,比如这个问题,是按照处理时间排序后贪心?还是按照效益排序后贪心?根据目标是效益最大化,那么就可以做出正确选择了。

当然动态规划比贪心优势的一点就是贪心是个局部策略,不是所有问题都能得到全局最优解,而DP是全局最优的,使用DP总能得到最优决策。针对本题,我们思考如何定义一个状态来列出状态转移方程。就像考虑其他类似组合优化问题时,看到有决策性步骤问题时,我们定义状态是带有步骤标号的,也就是第一章提到的stage decision,每个stage用k表示,到了第i个stage后,剩余的可决策集S作为另一个状态元素,于是我们定义状态(k,S),其中k是stage,S是表示当前状态下剩余可选决策。为了保证S集是可选择的决策集,我们需要对deadline排序,即按照截止时间排序。这样,我们列DPFE如下:f(k,S)=max d∈S{c(d|s)+f(k+1,S-{d})},其中c(d|s)=pd,基本条件是f(k,S)=0,当k=1+N或者S为空时。

以具体数据为例:5个作业标号为{0,1,2,3,4},其中每个作业的效益为{10,15,20,1,5},完成deadline为{1,2,2,3,3},求最优策略的效益。可以看到按照之前贪心解法,按照效益排序后,为20,15,10,5,1,而对应的截止时间也变为2,2,1,3,3,这样最优解就是20+15+5=40。DP的解法如下源码:

   1: package com.jybat.dp;
   2:  
   3: import java.util.Set;
   4: import java.util.SortedSet;
   5: import java.util.TreeSet;
   6:  
   7: //deadline scheduling of unit-time jobs
   8: public class DEADLINE {
   9:  
  10:     private static int[] profit = { 10, 15, 20, 1, 5 };
  11:     private static int[] deadline = { 1, 2, 2, 3, 3 }; // sorted
  12:     private static int N = profit.length; // no.of jobs
  13:  
  14:     private static SortedSet<Integer> setOfAllJobs = new TreeSet<Integer>();
  15:  
  16:     public DEADLINE() {
  17:         for (int i = 0; i < N; i++) {
  18:             setOfAllJobs.add(i);
  19:         }
  20:     }
  21:  
  22:     private static boolean feasible(SortedSet<Integer> jobs, int k, int d) {
  23:         int j = 0;
  24:         for (int i = 0; i < N; i++) {
  25:             if (!(jobs.contains(new Integer(i))) || i == d) {
  26:                 // if i already chosen or next (and is j-th),
  27:                 // does it meet its deadline?
  28:                 if (deadline[i] < ++j) {
  29:                     return false;
  30:                 }
  31:             }
  32:         }
  33:         return true;
  34:     }
  35:  
  36:     private static int cost(SortedSet<Integer> jobs, int k, int d) {
  37:         if (feasible(jobs, k, d)) {
  38:             return profit[d];
  39:         } else {
  40:             return 0;
  41:         }
  42:     }
  43:  
  44:     // jobs not yet chosen at stage k
  45:     public int f(SortedSet<Integer> jobs, int k) {
  46:         if (k > N)
  47:             return 0;
  48:         int max = Integer.MIN_VALUE;
  49:         for (int d : jobs) {
  50:             SortedSet<Integer> nJobs = copySet(jobs);
  51:             nJobs.remove(d);
  52:             int t = cost(jobs, k, d) + f(nJobs, k + 1);
  53:             if (t > max)
  54:                 max = t;
  55:         }
  56:         return max;
  57:     }
  58:  
  59:     private SortedSet<Integer> copySet(SortedSet<Integer> jobs) {
  60:         SortedSet<Integer> nJobs = new TreeSet<Integer>();
  61:         for (int i : jobs) {
  62:             nJobs.add(i);
  63:         }
  64:         return nJobs;
  65:     }
  66:  
  67:     /**
  68:      * @param args
  69:      */
  70:     public static void main(String[] args) {
  71:         DEADLINE d = new DEADLINE();
  72:         System.out.println(d.f(setOfAllJobs, 1));
  73:     }
  74:  
  75: }


posted on 2014-05-12 16:54 changedi 阅读(1755) 评论(1)  编辑  收藏 所属分类: 算法

评论

# re: 深入理解动态规划的一系列问题(10) 2014-05-12 23:45 ME娱乐澳门银座时时彩平台

赞一个  回复  更多评论   


只有注册用户登录后才能发表评论。


网站导航: