加权间隔调度问题动态程序 [英] Weighted Interval Scheduling problem & Dynamic program

查看:79
本文介绍了加权间隔调度问题动态程序的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧!

问题描述

我的问题与有关其他讨论.

我正在尝试使用动态程序在递归调用中实现该算法.

I'm trying to implement that algorithm using the dynamic program into a recursive call.

问题说明:

作业 j 从 sj 开始,在 fj 结束,并具有权重或值 vj.

Job j starts at sj, finishes at fj,and has weight or value vj.

如果两个作业不重叠,则它们兼容.

Two jobs compatible if they don't overlap.

目标:找到相互兼容工作的最大权重子集.

Goal: find maximum weight subset of mutually compatible jobs.

书籍提出的解决方案是使用解决方案表来存储所有子问题,这些子问题将在递归迭代调用期间在需要时重用.

The solution proposed by books is to use a solution table to store all suproblems which will be reused when needed during a recursive o iterative call.

解决问题的步骤是:

Input: n, s1,...,sn , f1,...,fn , v1,...,vn

Sort jobs by finish times so that f1 > f2 >... > fn.
Compute p(1), p(2), ..., p(n)
Where p(j) = largest index i < j such that job i is compatible with j.

    for j = 1 to n
       M[j] = empty <-- solution table
    M[j] = 0

    M-Compute-Opt(j) {
       if (M[j] is empty)
          M[j] = max(wj + M-Compute-Opt(p(j)), M-Compute-Opt(j-1))
       return M[j]
    }

这是我的代码(相关部分):

And this is my code (the relevant parts):

全局变量:

typedef struct {
    long start, stop, weight;
} job;

/* job array */
job *jobs;

/* solutions table */
long *solutions;

/* P(j) */
long *P;

-按完成时间对作业进行排序,以便 f1 > f2 >... > fn

-Sort jobs by finish times so that f1 > f2 >... > fn

    int compare(const void * a, const void * b) {

        const job *ad = (job *) a;
        const job *bd = (job *) b;

        return (ad->stop - bd->stop);
    }
//Jobs is filled above by parsing a datafile
qsort(jobs, njobs, sizeof(job), compare);

计算 p(1), p(2), ..., p(n)其中 p(j) = 最大指数 i

Compute p(1), p(2), ..., p(n) Where p(j) = largest index i < j such that job i is compatible with j.

/*bsearch for finding P(J)  */
int jobsearch(int start, int high){

        if (high == -1) return -1;

        int low = 0;
        int best = -1;
        int mid;
        int finish;

        while (low <= high){

            mid = (low + high) /2 ;
            finish = jobs[mid].stop;

            if (finish >= start){
                high = mid-1;
            }else{
                best = mid;
                low = mid + 1;
            }
        }

        return best;
    }

    int best;
        for (i = 0; i < njobs; i++){
            solutions[i] = -1l; //solutions table is initialized as -1
            best = jobsearch(jobs[i].start,i-1);

            if (best != -1)
                P[i] = best;
            else
                P[i] = 0;
        }

M-Compute-Opt(j):

M-Compute-Opt(j):

#define MAX(a, b)  (((a) > (b)) ? (a) : (b))
    /**
     * The recursive function with the dynamic programming reduction
     */
    long computeOpt(long j) {

        if (j == 0)
            return 0;

        if (solutions[j] != -1l) {
            return solutions[j];
        }

        solutions[j] = MAX(jobs[j].weight + computeOpt(P[j]), computeOpt(j - 1));


        return solutions[j];

    }

    long res = computeOpt(njobs-1);
    printf("%ld\n", res);

我针对几个具有大数据(从 10k 到 1m 随机生成的作业集)的测试用例运行我的程序,将我的输出与预期结果进行比较.在某些情况下,它会失败.有时我的输出比预期的结果大一点,有时比预期的结果小一点.我显然错过了一些东西.请注意,在大多数情况下,我的输出是正确的,因此我认为有些特殊情况我无法正确处理

I run my program against several test cases with large data (from 10k to 1m random generated jobs set) comparing my output to the expected result. In some cases it fails. Sometime my output is e bit greater and sometime is a bit lesser than the expected result. I'm missing somethings obviously. Note that in the most of the cases my output is correct so I think there is some specials condition I can't handle properly

我不知道问题出在哪里.

I cant't find out where the problem is.

感谢任何帮助

更新:我将递归函数更改为迭代函数,现在结果对于所有测试文件都是正确的.我再次无法理解为什么递归不起作用

UPDATE: I changed the recursive function into an iterative one and now the result is correct for all test file. Again I can't understand why the recursive one not works

推荐答案

让我们考虑一个微不足道的案例,一项工作.你会打电话

Let's consider trivial case, one job. You'll call

long res = computeOpt(njobs-1); // computeOpt(0)

那么,你有

    if (j == 0)
        return 0;

computeOpt 内.因此,您无法从一份工作中赚取任何收入.

inside computeOpt. So, you can't earn anything from one job.

在一般情况下,由于上面的行,您似乎忽略了第一份工作.if (j <0) 应该会更好.

In general case, you seem to ignore first job due to the line above. if (j < 0) should work better.

PS 在你去10k 到 1m 随机生成的作业集"之前总是测试简单和琐碎的情况.它们更易于验证和调试.

PS Always test simple and trivial cases before you go to "10k to 1m random generated jobs set". They are easier to verify and easier to debug.

这篇关于加权间隔调度问题动态程序的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!

查看全文
登录 关闭
扫码关注1秒登录
发送“验证码”获取 | 15天全站免登陆