2

私の質問は、この他の議論に関連しています。

動的プログラムを使用してそのアルゴリズムを再帰呼び出しに実装しようとしています。

問題文：

ジョブ j は に開始しsj、 に終了しfj、重みまたは値を持ちますvj。

重複しなければ互換性のある 2 つのジョブ。

目標: 相互に互換性のあるジョブの最大の重みのサブセットを見つけます。

本によって提案された解決策は、再帰的反復呼び出し中に必要なときに再利用されるすべての問題を格納するために解決テーブルを使用することです。

問題を解決する手順は次のとおりです。

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]
    }

そして、これは私のコードです（関連部分）：

グローバル変数:

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

/* job array */
job *jobs;

/* solutions table */
long *solutions;

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

- 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 < j で、ジョブ i は 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-計算-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 のランダムに生成されたジョブ セット) を持ついくつかのテスト ケースに対してプログラムを実行し、出力と期待される結果を比較します。場合によっては失敗します。私の出力は、予想される結果よりも少し大きい場合もあれば、少し小さい場合もあります。私は明らかに何かが欠けています。ほとんどの場合、私の出力は正しいので、適切に処理できない特別な状態があると思います。

問題がどこにあるのかわかりません。

どんな助けでも大歓迎です

更新: 再帰関数を反復関数に変更したところ、すべてのテスト ファイルで結果が正しくなりました。繰り返しますが、再帰的なものが機能しない理由がわかりません

4

1 に答える 1

1

些細なケース、1 つのジョブを考えてみましょう。あなたは電話します

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

次に、あなたは持っています

    if (j == 0)
        return 0;

内部computeOpt。そのため、1つの仕事で何も稼ぐことはできません。

一般に、上記の行のために最初のジョブを無視しているようです。if (j < 0)うまくいくはずです。

PS 「10kから1mのランダムに生成されたジョブセット」に進む前に、常に単純で些細なケースをテストしてください。それらは検証が容易で、デバッグが容易です。

于 2011-01-31T14:28:17.317 に答える