1

假设你有一个包含 n 个变量的线性方程。目标是确定 整数解是不可能的，或者确定整数解的最小系数向量。

换句话说，让ax=bwherex是你想要找到的向量，并且a是一个系数向量。b是一个标量常数。找到x这样的总和x1, ... ,xn最小化，并且所有xis 都是整数。或者，确定不x存在这种情况。从现在开始，我会说这|x|是xi's 的总和。

解决这个问题的有效方法是什么？我觉得这类似于背包问题，但我并不完全确定。

我的解决方案

我试图解决这个问题的方法是对向量​​空间进行广度优先搜索，其中广度将是向量条目的总和。

起初我天真地做了这个，从 开始|x| = 0，但是当n它甚至是中等大时，并且解决方案是不平凡的，生成的向量的数量是巨大的（n ^ |x|对于|x|你经历的每一个）。更糟糕的是，我生成了许多重复项。即使我找到了一种几乎不产生重复的方法，这种方法也太慢了。

接下来，我尝试从一个较高|x|的起点开始，通过在最佳|x|. 我按a降序排序，然后删除所有ai > b. 那么 的下界|x|是b / a[0]。但是，从这一点开始，我很难快速生成所有 size 的向量|x|。从这里开始，我的代码大多是 hacky。

在代码中，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;
}

编辑：我使用 valarray 因为我的编译器不符合 C++ 11，所以我不能使用数组。其他代码建议非常感谢。

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 回答