1

n 変数の線形方程式があるとします。目標は、 整数解が不可能であることを判断するか、整数解の最小係数ベクトルを判断することです。

言い換えると、は求めたいベクトルax=bで、 は係数のベクトルです。はスカラー定数です。の合計が最小になり、すべてのs が整数になるように求めます。または、そのようなものが存在しないことを確認してください。これからは、それが の合計だと言います。xabxx1, ... ,xnxix|x|xi

これを解決する効率的な方法は何ですか？これはナップザックの問題に似ているように感じますが、完全にはわかりません。

私の解決策

私がこれを解決しようとした方法は、ベクトル空間で幅優先探索を行うことでした。ここで、幅はベクトル エントリの合計になります。

最初は から始めて単純にこれを行いまし|x| = 0たが、 がn適度に大きく、解が自明でない場合、生成されるベクトルの数は膨大になります (通過するn ^ |x|たびに)。|x|さらに悪いことに、多くの重複を生成していました。重複をほとんど生成しない方法を見つけたとしても、この方法は遅すぎます。

次に、|x|最適な|x|. 降順で並べ替えaてから、すべて削除しai > bました。の下限|x|は ですb / a[0]。ただし、この時点から、 size のすべてのベクトルをすばやく生成するのは困難でした|x|。ここから、私のコードはほとんどハックです。

コードでb = distanceはx = clubs、、、n = numClubs

これは次のようになります。

short getNumStrokes (unsigned short distance, unsigned short numClubs, vector<unsigned short> clubs) {
    if (distance == 0)
        return 0;

    numClubs = pruneClubs(distance, &clubs, numClubs);
    //printClubs (clubs, numClubs);

    valarray<unsigned short> a(numClubs), b(numClubs);
    queue<valarray<unsigned short> > Q; 

    unsigned short floor = distance / clubs[0];

    if (numClubs > 1) {
        for (int i = 0; i < numClubs; i++) {
            a[i] = floor / numClubs;
        }

        Q.push (a);
    }

    // starter vectors
    for (int i = 0; i < numClubs; i++) {
        for (int j = 0; j < numClubs; j++) {
            if (i == j)
                a[j] = distance / clubs[0];
            else
                a[j] = 0;
        }

        if (dot_product (a, clubs) == distance)
            return count_strokes(a);

        // add N starter values
        Q.push (a);
    }

    bool sawZero = false;

    while (! Q.empty ()) {
        a = Q.front(); // take first element from Q
        Q.pop(); // apparently need to do this in 2 operations >_<

        sawZero = false;

        for (unsigned int i = 0; i < numClubs; i++) {
            // only add numbers past right-most non-zero digit
            //if (sawZero || (a[i] != 0 && (i + 1 == numClubs || a[i + 1] == 0))) {
            //    sawZero = true;

                b = a; // deep copy
                b[i] += 1;

                if (dot_product (b, clubs) == distance) {
                    return count_strokes(b);
                } else if (dot_product (b, clubs) < distance) {
                    //printValArray (b, clubs, numClubs);
                    Q.push (b);
                }
            //}
        }
    }

    return -1;
}

編集:コンパイラが C++ 11 に準拠していないため、valarray を使用しているため、配列を使用できません。他のコードの提案は大歓迎です。

4

1 に答える 1

0

あなたの問題は、等式制約付き整数ナップザック問題です:

min |x|
s.t. ax = b
     x integer

アクセスできる場合、CPLEX または GUROBI は一般に、このような問題を非常に簡単に解決できます。

それ以外の場合は、制約セットの削減を検討してください

(例: http://www.optimization-online.org/DB_FILE/2002/11/561.ps )

于 2013-09-26T15:18:12.043 に答える